The Schonhage-Strassen algorithm is an asymptotically fast multiplication algorithm for large integers, published by Arnold Schonhage and Volker Strassen in 1971, which works by recursively applying the fast Fourier transform over the integers modulo two to the power n plus one. It was the asymptotically fastest known multiplication method from 1971 until 2007 and remains asymptotically faster than older methods such as the Karatsuba algorithm and Toom-Cook multiplication, outperforming them in practice for numbers beyond roughly ten thousand to one hundred thousand decimal digits.
Facts
Time Complexity
Time Complexity (category)Linearithmic Time -- O(n log n) 1 Classification
Design Technique Connections
Credited To
Source Schönhage-Strassen algorithm (Wikipedia)
In Field
Source Schönhage-Strassen algorithm (Wikipedia)
Invented By
Volker Strassen co-developed this fast integer multiplication algorithm with Arnold Schonhage in 1971, using fast Fourier transforms.
Uses Design Technique
Sources
1. Schonhage-Strassen Algorithm (Wikipedia)
Wikipedia infobox: time complexity linearithmic
linearithmic
Wikipedia: design technique divide-and-conquer
divide-and-conquer
View the SourceSchönhage-Strassen algorithm (Wikipedia)
Credited To: Volker Strassen, Lead section
The Schönhage-Strassen algorithm is an asymptotically fast multiplication algorithm for large integers, published by Arnold Schönhage and Volker Strassen in 1971.
- In Field: Algorithms and Complexity Theory, Lead paragraph
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.