Strange behavior related to value / reference

Terry Reedy tjreedy at udel.edu
Wed Oct 28 04:45:03 CET 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