Mark Dickinson wrote:
On Oct 28, 8:24 am, Lambda <stephenh...@gmail.com> wrote:
Thank you!
Following is my final code:
Looks good, but are you sure about that word 'final'? ;-)
def matrix_power(m, n):
"""
Raise 2x2 matrix m to nth power.
"""
if n =0: return [[1, 0], [0, 1]]
x =atrix_power(m, n / 2)
I suggest using n // 2 instead of n / 2 here: n // 2 always
does integer divsion (aka 'floor division' in Python), while
the behaviour of n/2 depends on whether you're using Python
2.x or 3.1, and (in 2.x) on whether anyone's put a 'from
__future__ import division' at the top of the file.
square =atrix_mul(x, x)
if n % 2 =0:
return square
else:
return matrix_mul(m, square)
def matrix_mul(a, b):
result =row[:] for row in a]
result[0][0] =[0][0] * b[0][0] + a[0][1] * b[1][0]
result[0][1] =[0][0] * b[0][1] + a[0][1] * b[1][1]
result[1][0] =[1][0] * b[0][0] + a[1][1] * b[1][0]
result[1][1] =[1][0] * b[0][1] + a[1][1] * b[1][1]
return result
It's slightly more natural to build the list up as you go,
instead of creating a list of the right size and assigning
to its entries. E.g.,
def matrix_mul(a, b):
row0 =a[0][0]*b[0][0] + a[0][1]*b[1][0],
a[0][0]*b[0][1] + a[0][1]*b[1][1]]
row1 =similar>
return [row0, row1]
Better still, use for loops to loop over the elements and
accumulate the sums, and then your code won't need rewriting
when you want to use it to take the power of 3-by-3 matrices.
And then check out the builtin 'sum' function, and consider
replacing some or all of the for loops with list
comprehensions (depending on personal taste)...
Not-so-final'ly yours,
exp = 600
mat = [ [3, 0], [0, 3]]
print mat, exp, matrix_power(mat, exp)
mat = [ [3.0, 0], [0, 3.0]]
print mat, exp, matrix_power(mat, exp); print power(mat, exp)
[[3, 0], [0, 3]] 600
[[18739277038847939886754019920358123424308469030992781557966909983211910963157763678726120154469030856807730587971859910379069087693119051085139566217370635083384943613868029545256897117998608156843699465093293765833141309526696357142600866935689483770877815014461194837692223879905132001L,
0L], [0L,
18739277038847939886754019920358123424308469030992781557966909983211910963157763678726120154469030856807730587971859910379069087693119051085139566217370635083384943613868029545256897117998608156843699465093293765833141309526696357142600866935689483770877815014461194837692223879905132001L]]
[[3.0, 0], [0, 3.0]] 600 [[1.8739277038847955e+286, 0.0], [0.0,
1.8739277038847955e+286]]
[[1.8739277038847965e+286, 0.0], [0.0, 1.8739277038847965e+286]]
Mark
That square/multiply technique brought back fond memories. I used it
when I did the microcode for floating point arithmetic in 1975 or so.
Exponentiation used logs in the general case, but for integers below 100
used this technique. (At the time, the hardware instruction set was
capable of multiplying only single digit numbers, the rest was loops in
my microcode)
Probably I should also mention that, if the values had been floats
instead of integers, the square/multiply technique generally improves
accuracy, not just speed. While repeatedly multiplying int/long values
will eventually get the same answer, the quantization errors if they're
floats do add up faster. If we use the matrix
mat = [ [3, 0], [0, 3]] n = 600
The first bunch of digits of the upper left corner are:
1873927703884793988675401...
If we give mat floating values, and run it again:
1.8739277038847955e+286
and if we use simple loop, multiplying 600 times, we get:
1.8739277038847965e+286
DaveA
--
http://mail.python.org/mailman/listinfo/python-list
