doubling
Given $ f(x), I want to find $ f^n(x) fast
If the width of the definition and value range of f is D and the maximum value of n is N, we can pre-process O(D log N) and main process O(log N)
pretreatment
Since $ f^{2k}(x) = f^k(f^k(x)), we obtain $ f^{2k} by O(D) when $ f^k is known
Since k=1 is known, we obtain in O(D log N) for k such that [$ k=2^m < N
main processing
We can pick out only the 1's in binary expansion of n from the preprocessing results and synthesize them. The length of the binary expansion is of logarithmic order
---
This page is auto-translated from /nishio/ダブリング. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.