Fast Multiplication

I'm a sucker for large arithmetic. My master's thesis was based on using the number theoretic transform (NTT) to calculate pi. Today on Terence's blog [1] I saw him mention the Schönhage-Strassen algorithm, which is a specific kind of NTT. Reading about that algorithm took me back for a bit, talking about rings and primitive roots of unity and whatnot. What's interesting is that for astronomically large numbers there's actually a faster algorithm called Fürer's algorithm.

Just remember, though, 640 K of memory was considered a lot not so far in our history :).

[1] I make no claims in being able to follow Tao's blog. His posts are way, way over my head. Today I just got lucky :).

* Posted at 10.02.2008 12:27:47 PM CST | Link *

Blog History