Home Original page

Strange behavior related to value

Dave Angel davea at ieee.org
Wed Oct 28 08:07:21 EDT 2009 
Mark Dickinson wrote:
> On Oct 28, 8:24 am, Lambda <stephenh... at 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
More information about the Python-list mailing list