Tail-recursive pow() algorithm with memoization?

Question

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 memoize the results of all calculations - only those with exponents 1..exp/2 and exp.

Answer 1

You'll get better performance if you use the successive squaring technique described in SICP section 1.2.4 Exponentiation. It doesn't use memoization, but the general approach is O(log n) instead of O(n), so you should still see an improvement.

I talk about the solution to the iterative process from exercise 1.16 here.

Answer 2

I don't think you're recording the correct thing in your cache, the mapping changed when you call it with different arguments.

I think you need to have a cache of (base,exp) -> pow(base,exp).

I understand what ctr is for, and why only half of what you expect is recorded.

Consider calc_tailrec_mem(2,4): First level, pow(2,1) is recorded as 2, the next level = calc_tailrec_mem(2,3,...), and pow(2,2) is recorded. The next level is calc_tailrec_mem(2,2,...), but that is already saved in the cache, so the recursion stops.

The function is very confusing because it's caching something completely different from what it's supposed to be calculating, due to the acculumator and ctr.