Magic speedup

[Elias P. TSIGARIDAS]

Jens Hillenbach wrote:
> Congratulation to the speedup. May I ask what function M is in O(M(n))?
> Jens
> 

The time needed to multiply two integers of (bit) size n

--Elias


> */Torbjorn Granlund <tg at swox.com>/* wrote:
> 
>     I only now regenerated the "Computing billions of pi digits using GMP"
>     page for GMP 4.2, see http://swox.com/gmp/pi-with-gmp.html.
> 
>     The speedups I got for 4.1.4 => 4.2 was surprising. Computing 1e9
>     digits used to take 34300 seconds, now it takes just 8859 seconds on
>     an Opteron. The main sources of speedup should be the x86_64 assembly
>     and Paul Zimmermann's 2003 FFT improvements. But still a speedup of
>     almost 4x is much, much more than I had expected.
> 
>     The numbers still suffers from that division in GMP is O(M(n)log(n))
>     instead of just O(M(n)). The divisions in Chudnovsky's algorithm are
>     exact, and since we plan O(M(n)) exact division for a future GMP
>     version, things will improve further in the future.
> 
>     --
>     Torbjörn
>     _______________________________________________
>     gmp-discuss mailing list
>     gmp-discuss at swox.com
>     https://gmplib.org/mailman/listinfo/gmp-discuss
> 
> 
> ------------------------------------------------------------------------
> Yahoo! Messenger with Voice. Make PC-to-Phone Calls
> <http://us.rd.yahoo.com/mail_us/taglines/postman1/*http://us.rd.yahoo.com/evt=39663/*http://voice.yahoo.com>
> to the US (and 30+ countries) for 2¢/min or less.
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> gmp-discuss mailing list
> gmp-discuss at swox.com
> https://gmplib.org/mailman/listinfo/gmp-discuss