hisyatokaku’s blog

CS 6.006 Lecture 12 Square Roots, Newton's Method を見る

CS 6.006 Lecture

わかったこと

Multiplicationの時間計算量

$n$ 桁どうしの掛け算を行うときの時間計算量は、 $O(n^\alpha)$ で与えられる。

naiveなアルゴリズム: $\alpha=2$
Karatsuba: $\alpha=log3=1.584$

DivisionはNewton Method + Multiplicationによって行われる

$\frac{a}{b}$ を求めたいとき、 $\frac{1}{b}*a$ と考え、 $\frac{1}{b}$ を先に求める。
$\frac{1}{b}$ を求めたいとき、 $R=2^{k}$ として、 $\lfloor{\frac{R}{b}}\rfloor$ を求める。 $\frac{R}{b}$ の結果は整数となり、扱いやすい(?)上に、 $R=2^{k}$ であればビットシフトだけで割り算ができるからである。
$\lfloor{\frac{R}{b}}\rfloor$ を求めたいとき、 $f(x)=\frac{1}{x}-\frac{b}{R}$ となる関数を考え、 $f(x)=0$ になる点を探すことで $\frac{R}{b}$ を求める。 Newton法である。このようにすると複数のMultiplicationとRによるビットシフトだけで計算が可能になる。

参照→Lecture Notes | Introduction to Algorithms | Electrical Engineering and Computer Science | MIT OpenCourseWare

$f(x)=\frac{1}{x}-\frac{a}{b}$ を直接考えれば？と思ったが、これだとaによる割り算が必要になるので、Rによるビットシフトが行えるという点が大事なのだと思う。

関連して調べたこと

pythonの整数の扱い

pythonでは多倍長整数として扱われる。32bitにおさまらなくなったら、余分にメモリを確保して、まとめて一つの数字として扱えるようになっている。 pythonの思想である、プログラマはロジックに集中するべきという思想に基づくらしい。

多倍長整数の演算は、整数を格納した複数の32bitメモリをひとつなぎにして、下位の桁から計算し、carryがあった場合に上位の桁に渡すことを繰り返すようになっている。このスライドが参考になった。リンク