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