Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Toom–Cook_multiplication> ?p ?o }
Showing triples 1 to 50 of
50
with 100 triples per page.
- Toom–Cook_multiplication abstract "Toom–Cook, sometimes known as Toom-3, named after Andrei Toom, who introduced the new algorithm with its low complexity, and Stephen Cook, who cleaned the description of it, is a multiplication algorithm, a method of multiplying two large integers.Given two large integers, a and b, Toom–Cook splits up a and b into k smaller parts each of length l, and performs operations on the parts. As k grows, one may combine many of the multiplication sub-operations, thus reducing the overall complexity of the algorithm. The multiplication sub-operations can then be computed recursively using Toom–Cook multiplication again, and so on. Although the terms \"Toom-3\" and \"Toom–Cook\" are sometimes incorrectly used interchangeably, Toom-3 is only a single instance of the Toom–Cook algorithm, where k = 3.Toom-3 reduces 9 multiplications to 5, and runs in Θ(nlog(5)/log(3)), about Θ(n1.465). In general, Toom-k runs in Θ(c(k) ne), where e = log(2k − 1) / log(k), ne is the time spent on sub-multiplications, and c is the time spent on additions and multiplication by small constants. The Karatsuba algorithm is a special case of Toom–Cook, where the number is split into two smaller ones. It reduces 4 multiplications to 3 and so operates at Θ(nlog(3)/log(2)), which is about Θ(n1.585). Ordinary long multiplication is equivalent to Toom-1, with complexity Θ(n2).Although the exponent e can be set arbitrarily close to 1 by increasing k, the function c unfortunately grows very rapidly. The growth rate for mixed-level Toom-Cook schemes was still an open research problem in 2005. An implementation described by Donald Knuth achieves the time complexity Θ(n 2√2 log n log n).Due to its overhead, Toom–Cook is slower than long multiplication with small numbers, and it is therefore typically used for intermediate-size multiplications, before the asymptotically faster Schönhage–Strassen algorithm (with complexity Θ(n log n log log n)) becomes practical.Toom first described this algorithm in 1963, and Cook published an improved (asymptotically equivalent) algorithm in his PhD thesis in 1966.".
- Toom–Cook_multiplication wikiPageExternalLink toom-cook.
- Toom–Cook_multiplication wikiPageExternalLink Toom-3_002dWay-Multiplication.html.
- Toom–Cook_multiplication wikiPageID "330056".
- Toom–Cook_multiplication wikiPageLength "20875".
- Toom–Cook_multiplication wikiPageOutDegree "20".
- Toom–Cook_multiplication wikiPageRevisionID "707921085".
- Toom–Cook_multiplication wikiPageWikiLink Andrei_Toom.
- Toom–Cook_multiplication wikiPageWikiLink Category:Computer_arithmetic_algorithms.
- Toom–Cook_multiplication wikiPageWikiLink Category:Multiplication.
- Toom–Cook_multiplication wikiPageWikiLink Donald_Knuth.
- Toom–Cook_multiplication wikiPageWikiLink Gaussian_elimination.
- Toom–Cook_multiplication wikiPageWikiLink Karatsuba_algorithm.
- Toom–Cook_multiplication wikiPageWikiLink Multiplication_algorithm.
- Toom–Cook_multiplication wikiPageWikiLink Positional_notation.
- Toom–Cook_multiplication wikiPageWikiLink Schönhage–Strassen_algorithm.
- Toom–Cook_multiplication wikiPageWikiLink Stephen_Cook.
- Toom–Cook_multiplication wikiPageWikiLink The_Art_of_Computer_Programming.
- Toom–Cook_multiplication wikiPageWikiLink Toom–Cook_multiplication.
- Toom–Cook_multiplication wikiPageWikiLinkText "Evaluation".
- Toom–Cook_multiplication wikiPageWikiLinkText "Interpolation".
- Toom–Cook_multiplication wikiPageWikiLinkText "Pointwise multiplication".
- Toom–Cook_multiplication wikiPageWikiLinkText "Recomposition".
- Toom–Cook_multiplication wikiPageWikiLinkText "Splitting".
- Toom–Cook_multiplication wikiPageWikiLinkText "Toom–Cook algorithm".
- Toom–Cook_multiplication wikiPageWikiLinkText "Toom–Cook multiplication".
- Toom–Cook_multiplication wikiPageWikiLinkText "Toom–Cook".
- Toom–Cook_multiplication wikiPageUsesTemplate Template:Math.
- Toom–Cook_multiplication wikiPageUsesTemplate Template:Number-theoretic_algorithms.
- Toom–Cook_multiplication wikiPageUsesTemplate Template:Sqrt.
- Toom–Cook_multiplication subject Category:Computer_arithmetic_algorithms.
- Toom–Cook_multiplication subject Category:Multiplication.
- Toom–Cook_multiplication hypernym Algorithm.
- Toom–Cook_multiplication type Software.
- Toom–Cook_multiplication type Algorithm.
- Toom–Cook_multiplication type Redirect.
- Toom–Cook_multiplication comment "Toom–Cook, sometimes known as Toom-3, named after Andrei Toom, who introduced the new algorithm with its low complexity, and Stephen Cook, who cleaned the description of it, is a multiplication algorithm, a method of multiplying two large integers.Given two large integers, a and b, Toom–Cook splits up a and b into k smaller parts each of length l, and performs operations on the parts.".
- Toom–Cook_multiplication label "Toom–Cook multiplication".
- Toom–Cook_multiplication sameAs Q1522355.
- Toom–Cook_multiplication sameAs Toom-Cook-Algorithmus.
- Toom–Cook_multiplication sameAs Algoritmo_de_Toom-Cook.
- Toom–Cook_multiplication sameAs Algoritmo_de_Toom-Cook.
- Toom–Cook_multiplication sameAs Algorithme_Toom-Cook.
- Toom–Cook_multiplication sameAs Moltiplicazione_Toom-Cook.
- Toom–Cook_multiplication sameAs 톰-쿡_알고리즘.
- Toom–Cook_multiplication sameAs m.01wt2t.
- Toom–Cook_multiplication sameAs การคูณของทูม-คุก.
- Toom–Cook_multiplication sameAs Q1522355.
- Toom–Cook_multiplication wasDerivedFrom Toom–Cook_multiplication?oldid=707921085.
- Toom–Cook_multiplication isPrimaryTopicOf Toom–Cook_multiplication.