2 ms·
>In our case, the problem is no longer to calculate Fibonacci numbers – the problem is now to find a way to multiply large integers together efficiently. As far
by vortico 8y ago
>In our case, the problem is no longer to calculate Fibonacci numbers – the problem is now to find a way to multiply large integers together efficiently. As far as I can tell, GMP is already state-of-the-art when it comes to that, and tends to come out ahead on most benchmarks.
And actually, the best known method of multiplying large integers is achieved with an FFT over the integers mod 2^n (which is what GMP does). So then your task is changed yet again to optimizing a modular FFT algorithm...
- remcob 8y agoMultiplication in decimal systems is inefficient. FFT multiplication works by converting the numbers to and from a more efficient representation where multiplication is O(n) and embarrassingly parallel (convolution vs pointwise multiplication). If I'm not mistaken addition is also trivial in this representation, and since no other operations are required, the entire computation can be done in the FFT space. This definitely works in a residue number system, where a chinese remainder transform is used instead of an FFT. (CRT and FFT are algebraically related) In short, you can create a massive parallel cluster of computers computing parts of the result without interaction, and then in the end combine the results using a single huge pass of FFT.