How to improve this functional python fast exponentiation routine?
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 &amp; 1
        b &gt;&gt;= 1

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

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