Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Schönhage–Strassen_algorithm> ?p ?o }
Showing triples 1 to 64 of
64
with 100 triples 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) for two n-digit numbers. 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 wikiPageLength "20281".
- Schönhage–Strassen_algorithm wikiPageOutDegree "39".
- Schönhage–Strassen_algorithm wikiPageRevisionID "676855428".
- Schönhage–Strassen_algorithm wikiPageWikiLink Approximations_of_π.
- Schönhage–Strassen_algorithm wikiPageWikiLink Arnold_Schönhage.
- Schönhage–Strassen_algorithm wikiPageWikiLink Big_O_notation.
- Schönhage–Strassen_algorithm wikiPageWikiLink Category:Computer_arithmetic_algorithms.
- Schönhage–Strassen_algorithm wikiPageWikiLink Category:Multiplication.
- Schönhage–Strassen_algorithm wikiPageWikiLink Circular_convolution.
- Schönhage–Strassen_algorithm wikiPageWikiLink Context_of_computational_complexity.
- Schönhage–Strassen_algorithm wikiPageWikiLink Convolution_theorem.
- Schönhage–Strassen_algorithm wikiPageWikiLink Cooley–Tukey_FFT_algorithm.
- Schönhage–Strassen_algorithm wikiPageWikiLink Discrete_Fourier_transform.
- Schönhage–Strassen_algorithm wikiPageWikiLink Discrete_Fourier_transform_(general).
- Schönhage–Strassen_algorithm wikiPageWikiLink Donald_Knuth.
- Schönhage–Strassen_algorithm wikiPageWikiLink Fast_Fourier_transform.
- Schönhage–Strassen_algorithm wikiPageWikiLink Fxc3xbcrers_algorithm.
- Schönhage–Strassen_algorithm wikiPageWikiLink GNU_Multiple_Precision_Arithmetic_Library.
- Schönhage–Strassen_algorithm wikiPageWikiLink Great_Internet_Mersenne_Prime_Search.
- Schönhage–Strassen_algorithm wikiPageWikiLink Integer.
- Schönhage–Strassen_algorithm wikiPageWikiLink Karatsuba_algorithm.
- Schönhage–Strassen_algorithm wikiPageWikiLink Kronecker_substitution.
- Schönhage–Strassen_algorithm wikiPageWikiLink Lenstra_elliptic_curve_factorization.
- Schönhage–Strassen_algorithm wikiPageWikiLink Locality_of_reference.
- Schönhage–Strassen_algorithm wikiPageWikiLink Multiplication_algorithm.
- Schönhage–Strassen_algorithm wikiPageWikiLink Negacyclic_convolution.
- Schönhage–Strassen_algorithm wikiPageWikiLink Order_(group_theory).
- Schönhage–Strassen_algorithm wikiPageWikiLink Philosophy_of_mathematics.
- Schönhage–Strassen_algorithm wikiPageWikiLink Positional_notation.
- Schönhage–Strassen_algorithm wikiPageWikiLink Ring_(mathematics).
- Schönhage–Strassen_algorithm wikiPageWikiLink Root_of_unity.
- Schönhage–Strassen_algorithm wikiPageWikiLink Toom–Cook_multiplication.
- Schönhage–Strassen_algorithm wikiPageWikiLink Volker_Strassen.
- Schönhage–Strassen_algorithm wikiPageWikiLink File:Integer_multiplication_by_FFT.svg.
- Schönhage–Strassen_algorithm wikiPageWikiLinkText "FFT-based multiplication".
- Schönhage–Strassen_algorithm wikiPageWikiLinkText "Schönhage–Strassen algorithm".
- Schönhage–Strassen_algorithm wikiPageWikiLinkText "Schönhage–Strassen multiplication".
- Schönhage–Strassen_algorithm wikiPageWikiLinkText "Schönhage–Strassen".
- Schönhage–Strassen_algorithm wikiPageUsesTemplate Template:Number-theoretic_algorithms.
- Schönhage–Strassen_algorithm wikiPageUsesTemplate Template:Reflist.
- Schönhage–Strassen_algorithm subject Category:Computer_arithmetic_algorithms.
- Schönhage–Strassen_algorithm subject Category:Multiplication.
- Schönhage–Strassen_algorithm type Algorithm.
- Schönhage–Strassen_algorithm type Diacritic.
- Schönhage–Strassen_algorithm type Redirect.
- 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) for two n-digit numbers.".
- Schönhage–Strassen_algorithm label "Schönhage–Strassen algorithm".
- Schönhage–Strassen_algorithm sameAs Q1938391.
- Schönhage–Strassen_algorithm sameAs Schönhage-Strassen-Algorithmus.
- Schönhage–Strassen_algorithm sameAs Schönhagen–Strassenin_algoritmi.
- 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 쇤하게-슈트라센_알고리즘.
- Schönhage–Strassen_algorithm sameAs Algoritmo_Schönhage-Strassen.
- Schönhage–Strassen_algorithm sameAs m.04w65t.
- Schönhage–Strassen_algorithm sameAs Метод_умножения_Шёнхаге_—_Штрассена.
- Schönhage–Strassen_algorithm sameAs ขั้นตอนวิธี_Schonhage-Strassen.
- Schönhage–Strassen_algorithm sameAs Q1938391.
- Schönhage–Strassen_algorithm wasDerivedFrom Schönhage–Strassen_algorithm?oldid=676855428.
- Schönhage–Strassen_algorithm depiction Integer_multiplication_by_FFT.svg.
- Schönhage–Strassen_algorithm isPrimaryTopicOf Schönhage–Strassen_algorithm.