Primorial and faster binomial.

[bodrato at mail.dm.unipi.it]

Ciao!

Il Ven, 20 Aprile 2012 8:42 am, bodrato at mail.dm.unipi.it ha scritto:
> Il Gio, 19 Aprile 2012 2:23 pm, Torbjorn Granlund ha scritto:
>> bodrato at mail.dm.unipi.it writes:

>>   The current code uses the basecase below an hard-coded threshold on K,
>>   and anytime K < N/16. Tuning, and a deeper analysis are needed.
>
>> Have you measured the worst-case factor between the time of this
>> approach and the best function?  Perhaps it is tiny.

A quick test, on shell.gmplib.org, gives:

$ tune/speed -c -s8192000 mpz_bin_uiui.512000 mpz_bin_uiui.512001

        mpz_bin_uiui.512000 mpz_bin_uiui.512001
8192000   25308604743.08 #169856731.27

The bigger K (using prime-based) is more than 140 times faster than the
smaller one (using bc). With a bigger N, the worst-case factor is expected
to increase... I underline: a deeper analysis is needed.

-- 
http://bodrato.it/software/