Throw the cat among the pigeons

[Dave Angel]

On 05/06/2015 09:55 AM, Chris Angelico wrote:
> On Wed, May 6, 2015 at 11:12 PM, Dave Angel <davea at davea.name> wrote:
>> I had guessed that the order of multiplication would make a big difference,
>> once the product started getting bigger than the machine word size.
>>
>> Reason I thought that is that if you multiply starting at the top value (and
>> end with multiplying by 2) you're spending more of the time multiplying
>> big-ints.
>>
>> That's why I made sure that both Cecil's and my implementations were
>> counting up, so that wouldn't be a distinction.
>>
>> I'm still puzzled, as it seems your results imply that big-int*int is faster
>> than int*int where the product is also int.
>
> Are you using Python 2 or Python 3 for your testing? In Py3, there's
> no type difference, and barely no performance difference as you cross
> the word-size boundary. (Bigger numbers are a bit slower to work with,
> but not hugely.)
>

Both Cecil and I are using 3.x  I'm using 3.4 in particular.  And I know 
int covers both big-int and int32.  that's why I called it big-int, 
rather than long.

I was, however, mistaken.  it's not that threshold that we're crossing 
here, but another one, for MUCH larger numbers.  factorial of 100000 and 
of 200000 have 456473 and 97350 digits, respectively.  In binary, that 
would be about 190k bytes and 404k bytes, respectively.

I was seeing factorial of 200000 taking about 4.5 times as long as 
factorial of 100000.  All the other increments seemed fairly proportional.

I'll bet the difference is something like the memory allocator using a 
different algorithm for blocks above 256k.  Or the cache logic hitting a 
threshold.

If it's caching, of course the threshold will differ wildly between 
machine architectures.

If it's the memory allocator, that could easily vary between Python 
versions as well.




-- 
DaveA