CODEWITHSUNDEEP
performancealgorithmbigintegermultiplicationmodular
Tibor Vass
Tibor Vass

Reputation: 167

When is the "Fast Integer Multiplication Using Modular Arithmetic" (2008) algorithm faster than Schönhage-Strassen algorithm?

From Wikipedia:

"Anindya De, Chandan Saha, Piyush Kurur and Ramprasad Saptharishi[11] gave a similar algorithm using modular arithmetic in 2008 achieving the same running time. However, these latter algorithms are only faster than Schönhage–Strassen for impractically large inputs."

I would be very interested in the size of such impractically large integers.

Maybe someone did implement both algorithms in a certain way and could do some benchmarks?

Thanks

Upvotes: 3

Views: 1948

Answers (1)

Mysticial
Mysticial

Reputation: 471439

Fürer's algorithm and it's modular equivalent (DSKS) are very deep research topics and, for now, remain only as academic interest. Nobody actually knows how big the cross-over point is. And in all likeliness it doesn't matter because that cross-over point is likely to be well beyond 64-bit computing limits.

I've implemented Schönhage-Strassen before and I understand how Fürer's algorithm works. So I'm quite familiar with both of them. I can say it's very possible that the cross-over point between Schönhage-Strassen and Fürer's algorithm is so high that a computer capable of holding the parameters will be larger than the size of the observable universe.

That's the problem when you have complexities that differ by less than a logarithm. It takes exponentially large input sizes to compensate even for small differences in the Big-O constant.

In this case, Fürer's algorithm is known to have a very very very large Big-O constant.

Upvotes: 5

Related Questions