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

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.

Answer 2

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 3

This is way too late, but anyone out there looking for the answer, here it is:

int powMem(int base,int exp){
    //initializes once and for all
    static map<int,int> memo;

    //base case to stop the recursion
    if(exp <= 1) return base;

    //check if the value is already calculated before. If yes just return it.
    if(memo.find(exp) != memo.end())
        return memo[exp];

    //else just find it and then store it in memo for further use.
    int x = powMem(base,exp/2);
    memo[exp] = x*x;

    //return the answer
    return memo[exp];
}

This uses the memo array - a map , to be exact - to store the already calculated values.