3 ms·
It seems rather weird to use an explicit cache for the dynamic programming exponentiation. When computing x^n, n is either even or odd. If it's even, then the
by morei 8y ago
It seems rather weird to use an explicit cache for the dynamic programming exponentiation.
When computing x^n, n is either even or odd. If it's even, then the result is (x^(n/2))^2, else it's odd and the result is x * (x^(n/2))^2. i.e.
def pow(x, n):
if x == 1:
return x
if (n & 1) == 1:
return x * square(pow(x,n//2))
else:
return square(pow(x,n//2))
Does ~ the minimum number of multiplies, no LRU cache required.
- Someone 8y agoFor those wondering about that ~: https://en.wikipedia.org/wiki/Addition_chain https://en.wikipedia.org/wiki/Addition_chain: ”There is no known algorithm which can calculate a minimal addition chain for a given number with any guarantees of reasonable timing or small memory usage. However, several techniques to calculate relatively short chains exist. One very well known technique to calculate relatively short addition chains is the binary method, similar to exponentiation by squaring.”
- morei 8y agoThat's why I said "~ the minimum" :) In particular, it does at most the same number of multiplies as the LRU cache version in the OP