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 :
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 :
- Each item in the list only depends on the previous one
- 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.