ダブリング

$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のところだけ前処理結果から選び出して合成すれば良い
  • 二進展開の長さは対数オーダー