num-bigint
num-bigint copied to clipboard
rust-num
Algorithm improvements for very large numbers
Implement better multiplication for large numbers.
Multiplication currently uses Toom-3, which is O(n^1.47) for n BigDigits. This can be improved to O(n log n) using the Fast Fourier Transform (on complex numbers with sufficient precision) or Number Theoretic Transform (using modular arithmetic with multiple primes), or slightly worse O(n log n log log n) using the Schönhage–Strassen algorithm. I am leaning towards the latter because it's only slightly slower asymptotically, but simpler, so I suspect it might actually be faster for all practical sizes.
It will probably make sense to split algorithms into separate modules.
It would be great to improve the scalability, as long as it's done in a way that doesn't hurt the performance of relatively-small numbers. For example, the current multiplication scales from basic long multiplication to Karatsuba to Toom-3, since constant factors can overwhelm Big-O algorithm scaling. Of course, there may well be possible improvements in small numbers too!
Refactoring the modules is also fine, but please try to do it in incremental steps for ease of review. If you give me a huge PR at once, I'll be less able to deal with it in a timely manner.
No doubt it needs to find a suitable threshold to protect small numbers. And It may be a good practice to look at the implementation in GMP.
I did an optimization of big int division in Go before, now doing FFT with Go. I'm happy to help if you need.
O(NlogN ) FFT is difficult for integers, as the loss of accuracy cannot be avoided. Number Theoretic Transform is also very difficult, because you can't easily find the right prime number. I think Schönhage–Strassen is a good choice. Here is the link if anyone need. https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm
For NTT the way I would do it is do modulo 3 or 4 small (BigDigit-size) primes at the same time, the primes determined at compile time, and then reconstruct the answers using the Chinese Remainder Theorem. This would be O(n log n) and I bet could be competitive in practice. I might try implementing that as an experiment, but I agree that starting with Schönhage–Strassen is cleaner / simpler.
I have no doubt about the correctness of the theory. Of course if you can do it that would be wonderful. Would be very grateful if you could recommend some theoretical material such as link or paper.
if you do not mind I want try to make an implementation using Schönhage–Strassen, as that is what I am doing in Go.
Is this still up to date ? I'm currently working on Schönage-Strassen in GMP so I was thinking of implementing it in rust. Are you still interested or is someone already working on it ? (I'm thinking of it not giving promises of anything thought)
Note that GPL code from GMP cannot be used in this MIT/Apache-2 project, not even with a language translation along the way. The algorithm itself should be fine, but don't use GMP as a reference.