Schönhagen–Strassenin algoritmi
From Wikipedia, the free encyclopedia
Schönhagen–Strassenin algoritmi on matematiikassa asymptoottisesti nopea menetelmä suurten kokonaislukujen kertolaskuun. Sen kehittivät Arnold Schönhage (s. 1934) ja Volker Strassen (s. 1936). Algoritmin asymptoottinen suoritusaika on O(N log N log log N). Algoritmi käyttää nopeaa Fourier'n muunnosta ja algebrasta tuttuja renkaita.
Lähteet
- Computing 7 (1971), 281-292
- Donald Knuth: The Art of Computer Programming, Volume 2, 3rd ed., pp. 306–311, ISBN 0-201-89684-2.
Wikiwand - on
Seamless Wikipedia browsing. On steroids.