Tail-recursive pow() algorithm with memoization?
- by Dan
I'm looking for an algorithm to compute pow() that's tail-recursive and uses memoization to speed up repeated calculations.
Performance isn't an issue; this is mostly an intellectual exercise - I spent a train ride coming up with all the different pow() implementations I could, but was unable to come up with one that I was happy with that had these two properties.
My best shot was the following:
def calc_tailrec_mem(base, exp, cache_line={}, acc=1, ctr=0):
if exp == 0:
return 1
elif exp == 1:
return acc * base
elif exp in cache_line:
val = acc * cache_line[exp]
cache_line[exp + ctr] = val
return val
else:
cache_line[ctr] = acc
return calc_tailrec_mem(base, exp-1, cache_line, acc * base, ctr + 1)
It works, but it doesn't memorize the results of all calculations - only those with exponents 1..exp/2 and exp.
