Strange behavior related to value / reference
Terry Reedy
tjreedy at udel.edu
Tue Oct 27 23:45:03 EDT 2009
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
More information about the Python-list
mailing list