わかったこと Multiplicationの時間計算量 桁どうしの掛け算を行うときの時間計算量は、 で与えられる。 naiveなアルゴリズム: Karatsuba: DivisionはNewton Method + Multiplicationによって行われる を求めたいとき、と考え、 を先に求める。 を求めたいと…