How to improve this functional python fast exponentiation routine?

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.

-
A bit of a naive question but why don't you just rewrite the definition of Function exp-by-squaring(x,n) from Wikipedia in proper python ? It seems fine as far as I can tell. –  Josay Feb 1 '13 at 10:16
@Josay because I want to make one myself. –  Cris Stringfellow Feb 26 '13 at 18:48

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

while b :
yield b & 1
b >>= 1

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

def fast_exp(b, exp) :

-
I like that. Both these answers are awesome. Showing the beautiful ways of looking at it from two different and complimentary perspectives. Coolness. –  Cris Stringfellow Feb 1 '13 at 17:17
I chose this as the answer because although we have a tail recursion version, as asked, and this generator expression as asked, I really liked the use of compress and the idea of selectors -- which was new for me. –  Cris Stringfellow Feb 26 '13 at 18:49

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).

-
Oh I like that, that's really neat and clean. Exposes the algorithm logic perfectly. –  Cris Stringfellow Feb 1 '13 at 17:16
Why do we consider times=1 as the default case instead of times=0 ? –  Josay Feb 3 '13 at 10:15
Because using this logic times=0 is an edge case (but you're right, it should be dealt with). –  cmh Feb 3 '13 at 17:01
@cmh What does ML stand for? –  Cris Stringfellow Feb 26 '13 at 18:52
@CrisStringfellow fr.wikipedia.org/wiki/ML_(langage) –  Josay Feb 26 '13 at 20:57

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

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