Paul Rubin <no.email@nospam.invalid> writes: > Steven D'Aprano <steve+comp.lang.pyt...@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.
Yes, plus the time for memory allocation. Since the code uses "r *= ...", space is reallocated when the result doesn't fit. The new size is probably proportional to the current (insufficient) size. This means that overall, you'll need fewer reallocations, because allocations are made in bigger chunks. -- Alain. -- https://mail.python.org/mailman/listinfo/python-list
