Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Schönhage–Strassen_algorithm> ?p ?o. }
Showing items 1 to 22 of
22
with 100 items per page.
- Schönhage–Strassen_algorithm abstract "The Schönhage–Strassen algorithm is an asymptotically fast multiplication algorithm for large integers. It was developed by Arnold Schönhage and Volker Strassen in 1971. The run-time bit complexity is, in Big O notation, O(N log N log log N). The algorithm uses recursive Fast Fourier transforms in rings with 22n + 1 elements, a specific type of number theoretic transform.The Schönhage–Strassen algorithm was the asymptotically fastest multiplication method known from 1971 until 2007, when a new method, Fürer's algorithm, was announced with lower asymptotic complexity; however, Fürer's algorithm currently only achieves an advantage for astronomically large values and is not used in practice.In practice the Schönhage–Strassen algorithm starts to outperform older methods such as Karatsuba and Toom–Cook multiplication for numbers beyond 2215 to 2217 (10,000 to 40,000 decimal digits). The GNU Multi-Precision Library uses it for values of at least 1728 to 7808 64-bit words (33,000 to 150,000 decimal digits), depending on architecture. There is a Java implementation of Schönhage–Strassen which uses it above 74,000 decimal digits.Applications of the Schönhage–Strassen algorithm include mathematical empiricism, such as the Great Internet Mersenne Prime Search and computing approximations of π, as well as practical applications such as Kronecker substitution, in which multiplication of polynomials with integer coefficients can be efficiently reduced to large integer multiplication; this is used in practice by GMP-ECM for Lenstra elliptic curve factorization.".
- Schönhage–Strassen_algorithm thumbnail Integer_multiplication_by_FFT.svg?width=300.
- Schönhage–Strassen_algorithm wikiPageID "1354446".
- Schönhage–Strassen_algorithm wikiPageRevisionID "590119870".
- Schönhage–Strassen_algorithm subject Category:Computer_arithmetic_algorithms.
- Schönhage–Strassen_algorithm subject Category:Multiplication.
- Schönhage–Strassen_algorithm comment "The Schönhage–Strassen algorithm is an asymptotically fast multiplication algorithm for large integers. It was developed by Arnold Schönhage and Volker Strassen in 1971. The run-time bit complexity is, in Big O notation, O(N log N log log N).".
- Schönhage–Strassen_algorithm label "Algorithme de Schönhage-Strassen".
- Schönhage–Strassen_algorithm label "Algoritmo Schönhage-Strassen".
- Schönhage–Strassen_algorithm label "Algoritmo di Schönhage-Strassen".
- Schönhage–Strassen_algorithm label "Schönhage-Strassen-Algorithmus".
- Schönhage–Strassen_algorithm label "Schönhage–Strassen algorithm".
- Schönhage–Strassen_algorithm label "Метод умножения Шёнхаге — Штрассена".
- Schönhage–Strassen_algorithm sameAs Sch%C3%B6nhage%E2%80%93Strassen_algorithm.
- Schönhage–Strassen_algorithm sameAs Schönhage-Strassen-Algorithmus.
- Schönhage–Strassen_algorithm sameAs Algorithme_de_Schönhage-Strassen.
- Schönhage–Strassen_algorithm sameAs Algoritmo_di_Schönhage-Strassen.
- Schönhage–Strassen_algorithm sameAs Algoritmo_Schönhage-Strassen.
- Schönhage–Strassen_algorithm sameAs Q1938391.
- Schönhage–Strassen_algorithm sameAs Q1938391.
- Schönhage–Strassen_algorithm wasDerivedFrom Schönhage–Strassen_algorithm?oldid=590119870.
- Schönhage–Strassen_algorithm depiction Integer_multiplication_by_FFT.svg.
