Schönhagen–Strassenin algoritmi
(Ohjattu sivulta Schönhagen-Strassenin algoritmi)
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[muokkaa | muokkaa wikitekstiä]
- Computing 7 (1971), 281-292
- Donald Knuth: The Art of Computer Programming, Volume 2, 3rd ed., pp. 306–311, ISBN 0-201-89684-2.