Matches in DBpedia 2016-04 for { <http://wikidata.dbpedia.org/resource/Q1938391> ?p ?o }
Showing triples 1 to 37 of
37
with 100 triples per page.
- Q1938391 subject Q7011883.
- Q1938391 subject Q9406976.
- Q1938391 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.".
- Q1938391 thumbnail Integer_multiplication_by_FFT.svg?width=300.
- Q1938391 wikiPageWikiLink Q1006032.
- Q1938391 wikiPageWikiLink Q1130396.
- Q1938391 wikiPageWikiLink Q1205818.
- Q1938391 wikiPageWikiLink Q12503.
- Q1938391 wikiPageWikiLink Q130762.
- Q1938391 wikiPageWikiLink Q1522355.
- Q1938391 wikiPageWikiLink Q161172.
- Q1938391 wikiPageWikiLink Q17457.
- Q1938391 wikiPageWikiLink Q1747853.
- Q1938391 wikiPageWikiLink Q180536.
- Q1938391 wikiPageWikiLink Q1868547.
- Q1938391 wikiPageWikiLink Q245450.
- Q1938391 wikiPageWikiLink Q2638931.
- Q1938391 wikiPageWikiLink Q2662711.
- Q1938391 wikiPageWikiLink Q269878.
- Q1938391 wikiPageWikiLink Q2835790.
- Q1938391 wikiPageWikiLink Q2878.
- Q1938391 wikiPageWikiLink Q4423896.
- Q1938391 wikiPageWikiLink Q5167446.
- Q1938391 wikiPageWikiLink Q585175.
- Q1938391 wikiPageWikiLink Q589491.
- Q1938391 wikiPageWikiLink Q623950.
- Q1938391 wikiPageWikiLink Q629940.
- Q1938391 wikiPageWikiLink Q6438897.
- Q1938391 wikiPageWikiLink Q65212.
- Q1938391 wikiPageWikiLink Q6987082.
- Q1938391 wikiPageWikiLink Q7011883.
- Q1938391 wikiPageWikiLink Q756747.
- Q1938391 wikiPageWikiLink Q78106.
- Q1938391 wikiPageWikiLink Q9406976.
- Q1938391 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.".
- Q1938391 label "Schönhage–Strassen algorithm".
- Q1938391 depiction Integer_multiplication_by_FFT.svg.