Long Multiplication is not commutative.

Christian Tismer tismer at tismer.com
Thu Apr 6 23:33:05 CEST 2000


Yikes!

No, it is computatively commutative, just not in terms
of computation time. :-))

The following factorial loops differ by a remarkable
factor of 1.8, and we can gain this speed by changing
long_mult to always put the lower multiplicand into the left.

This was reported to me by Lenny Kneler, who thought he had
found a Stackless bug, but he was actually testing long math. :-)

This buddy...

>>> def ifact3(n) :
...  p = 1L
...  for i in range(1,n+1) :
...    p = i*p
...  return p

performs better by a factor of 1.8 than this one:

>>> def ifact1(n) :
...  p = 1L
...  for i in range(1,n+1) :
...    p = p*i
...  return p

The analysis of this behavior is quite simple if you look at the
implementation of long_mult. If the left operand is big and the
right is small, there are much more carry operations performed,
together with more loop overhead.
Swapping the multiplicands would be a 5 line patch.
Should I submit it?

ciao - chris

-- 
Christian Tismer             :^)   <mailto:tismer at appliedbiometrics.com>
Applied Biometrics GmbH      :     Have a break! Take a ride on Python's
Kaunstr. 26                  :    *Starship* http://starship.python.net
14163 Berlin                 :     PGP key -> http://wwwkeys.pgp.net
PGP Fingerprint       E182 71C7 1A9D 66E9 9D15  D3CC D4D7 93E2 1FAE F6DF
     where do you want to jump today?   http://www.stackless.com




More information about the Python-list mailing list