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.

  • \$\begingroup\$ 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. \$\endgroup\$
    – SylvainD
    Commented Feb 1, 2013 at 10:16
  • \$\begingroup\$ @Josay because I want to make one myself. \$\endgroup\$ Commented Feb 26, 2013 at 18:48

3 Answers 3


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)
  • \$\begingroup\$ I like that. Both these answers are awesome. Showing the beautiful ways of looking at it from two different and complimentary perspectives. Coolness. \$\endgroup\$ Commented Feb 1, 2013 at 17:17
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Feb 26, 2013 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)
        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).

  • \$\begingroup\$ Oh I like that, that's really neat and clean. Exposes the algorithm logic perfectly. \$\endgroup\$ Commented Feb 1, 2013 at 17:16
  • \$\begingroup\$ Why do we consider times=1 as the default case instead of times=0 ? \$\endgroup\$
    – SylvainD
    Commented Feb 3, 2013 at 10:15
  • \$\begingroup\$ Because using this logic times=0 is an edge case (but you're right, it should be dealt with). \$\endgroup\$
    – cmh
    Commented Feb 3, 2013 at 17:01
  • \$\begingroup\$ @cmh What does ML stand for? \$\endgroup\$ Commented Feb 26, 2013 at 18:52
  • 1
    \$\begingroup\$ @CrisStringfellow fr.wikipedia.org/wiki/ML_(langage) \$\endgroup\$
    – SylvainD
    Commented Feb 26, 2013 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

    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/


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.