Throw the cat among the pigeons

[Ian Kelly]

On Wed, May 6, 2015 at 9:12 AM, Paul Rubin <no.email at nospam.invalid> wrote:
> 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.

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.