Throw the cat among the pigeons
Paul Rubin
no.email at nospam.invalid
Wed May 6 11:12:50 EDT 2015
Steven D'Aprano <steve+comp.lang.python at pearwood.info> writes:
> Multiplying upwards seems to be more expensive than multiplying
> downwards... I can only guess that it has something to do with the way
> multiplication is implemented, or perhaps the memory management
> involved, or something. Who the hell knows?
It seems pretty natural if multiplication uses the obvious
quadratic-time pencil and paper algorithm. The cost of multiplying m*n
is basically w(m)*w(n) where w(x) is the width of x in machine words.
So for factorial where m is the counter and n is the running product,
w(m) is always 1 while w(n) is basically log2(n!). From
from math import log
def xfac(seq):
cost = logfac = 0.0
for i in seq:
logfac += log(i,2)
cost += logfac
return cost
def upward(n): return xfac(xrange(1,n+1))
def downward(n): return xfac(xrange(n,1,-1))
print upward(40000),downward(40000)
I get: 10499542692.6 11652843833.5
A lower number for upward than downward. The difference isn't as large
as your timings, but I think it still gives some explanation of the
effect.
More information about the Python-list
mailing list