How to improve this functional python fast exponentiation routine?

Question

I have the following python functions for exponentiation by squaring :

def rep_square(b,exp):
        return reduce(lambda sq,i: sq + [sq[-1]*sq[-1]],xrange(len(radix(exp,2))),[b])

def exponentiate(b,exp):
        return reduce(lambda res,(sq,p): res*sq if p == 1 else res,zip(rep_square(b,exp),radix(exp,2)),1)

They work. Calling print exponentiate(2,10), exponentiate(3,37) yields :

1024 450283905890997363

as is proper. But I am not happy with them because they need to calculate a list of squares. This seems to be a problem that could be resolved by functional programming because :

1. Each item in the list only depends on the previous one
2. Repeated squaring is recursive

Despite people mentioning that recursion is a good thing to employ in functional programming, and that lists are not good friends -- I am not sure how to turn this recursive list of squares into a recursive generator of the values that would avoid a list. I know I could use a stateful generator with yield but I like something that can be written in one line.

Is there a way to do this with tail recursion? Is there a way to make this into a generator expression?

The only thing I have thought of is this particularly ugly and also broken recursive generator :

def rep_square(n,times):
    if times <= 0:
        yield n,n*n
    yield n*n,list(rep_square(n*n,times-1))

It never returns.

Answer 1

You haven't said anything against itertools, so here's how I'd do it with generators:

from itertools import compress
from operator import mul

def radix(b) :
    while b :
        yield b & 1
        b >>= 1

def squares(b) :
    while True :
        yield b
        b *= b

def fast_exp(b, exp) :
    return reduce(mul, compress(squares(b), radix(exp)), 1)

Answer 2

A tail recursive version could look something like this:

def rep_square_helper(x, times, res):
    if times == 1:
        return res * x
    if times % 2:
        return rep_square_helper(x * x, times // 2, res * x)
    else:
        return rep_square_helper(x * x, times // 2, res)

def rep_square(n, times):
    return rep_square_helper(n, times, 1)

Note that in python there is no real advantage to using tail recursion (as opposed to, say, ML where the compiler can reuse stack frames).

Answer 3

One of the things I do not like that much about python is the possibility and trend to crunch everything in one line for whatever reasons (no, do not compare with perl).

For me, a more readable version:

def binary_exponent(base, exponent):
    """\
    Binary Exponentiation

    Instead of computing the exponentiation in the traditional way,
    convert the exponent to its reverse binary representation.

    Each time a 1-bit is encountered, we multiply the running total by
    the base, then square the base.
    """
    # Convert n to base 2, then reverse it. bin(6)=0b110, from second index, reverse
    exponent = bin(exponent)[2:][::-1]

    result = 1
    for i in xrange(len(exponent)):
        if exponent[i] is '1':
            result *= base
        base *= base
    return result

source (slightly modified): http://blog.madpython.com/2010/08/07/algorithms-in-python-binary-exponentiation/