Lambda wrote:
I defined a function to raise a 2x2 matrix to nth power:
There is a much faster way to raise x to a count power n than the
definitional but naive method of multipling 1 by x n times. It is based
on the binary representation of n.
Example: x**29 = x**(16+8+4+1) = x**16 * x**8 * x**4 * x * 1
So square x 4 times and do 4 more multiplies (total 8) instead of 28!
General algorithm is something like (untested):
def expo(x, n): # assume n is a count
if n%2: res = x
else: res = 1 # or the identity for type(x)
base = x
n //= 2 # if n < 2, we are done
while n:
base *= base # or appropriate mul function
if n%2: res *= base # ditto
n //= 2
return res
Terry Jan Reedy
--
http://mail.python.org/mailman/listinfo/python-list
