ダブリング
$ f(x)が与えられて $ f^n(x) を高速に求めたい
fの定義域・値域の広さをD、nの最大値をNとするなら前処理O(D log N)で本処理O(log N)にできる
前処理
$ f^{2k}(x) = f^k(f^k(x))なので$ f^kが既知のの時O(D)で$ f^{2k}が得られる
k=1は既知なので、$ k=2^m < NであるようなkについてO(D log N)で得られる
本処理
nの二進展開で1のところだけ前処理結果から選び出して合成すれば良い 二進展開の長さは対数オーダー