Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

There is a nice picture of the "best" for different ranges of sizes of numbers to be multiplied at

http://gmplib.org/devel/log.i7.1024.png

More context and explanation can be found at: http://gmplib.org/devel/

BTW, I like Bernstein's survey of different multiplication algorithms at

https://cr.yp.to/papers/m3.pdf

(there is a unifying theme about using ring isomorphisms to explain many of the "standard" routines.)



PS: if you're interested in multiplying "ludicrously large numbers", Harvey and van der Hoeven had a nice breakthrough and got multiplication down to "FFT speed" (n*log(n)), see

https://hal.science/hal-02070778v2/document

A pop-sci description can be found at

https://theconversation.com/weve-found-a-quicker-way-to-mult...




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: