On Wed, May 6, 2015 at 9:12 AM, Paul Rubin <no.email@nospam.invalid> wrote: > 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.
That was my initial thought as well, but the problem is that this actually predicts the *opposite* of what is being reported: upward should be less expensive, not more. -- https://mail.python.org/mailman/listinfo/python-list