Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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.

share|improve this question
    
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

3 Answers 3

up vote 1 down vote accepted

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)
share|improve this answer
    
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).

share|improve this answer
    
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
1  
@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

    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/

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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