二分探索を使った平方根


二分探索を使った平方根・立方根を求める関数です.

仕様

  • 入力:整数
  • 出力:入力の平方根・立方根を整数に丸めたもの
  • 収束:保障されている
  • 精度:整数部分までは必ず正しい
  • 計算量:入力n\displaystyleに対し,
  • *平方根:o(\log_{4}n+\frac{1}{2}\log_2n)\displaystyle
  • *立法根:o(\log_{8}n+\frac{1}{3}\log_2n)\displaystyle

ニュートン法と比べると,収束が保証されている点で優れている.

ソース

参考文献