Primorial and faster binomial.

bodrato at bodrato at
Fri Apr 20 10:17:15 CEST 2012


Il Ven, 20 Aprile 2012 8:42 am, bodrato at ha scritto:
> Il Gio, 19 Aprile 2012 2:23 pm, Torbjorn Granlund ha scritto:
>> bodrato at 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, 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.


More information about the gmp-devel mailing list