Throw the cat among the pigeons

[Alain Ketterlin]

Paul Rubin <no.email at nospam.invalid> writes:

> 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.

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.