Matches in DBpedia 2016-04 for { <http://wikidata.dbpedia.org/resource/Q1522355> ?p ?o }
Showing triples 1 to 19 of
19
with 100 triples per page.
- Q1522355 subject Q7011883.
- Q1522355 subject Q9406976.
- Q1522355 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.".
- Q1522355 wikiPageExternalLink toom-cook.
- Q1522355 wikiPageExternalLink Toom-3_002dWay-Multiplication.html.
- Q1522355 wikiPageWikiLink Q130762.
- Q1522355 wikiPageWikiLink Q1522355.
- Q1522355 wikiPageWikiLink Q17457.
- Q1522355 wikiPageWikiLink Q1747853.
- Q1522355 wikiPageWikiLink Q1938391.
- Q1522355 wikiPageWikiLink Q2658.
- Q1522355 wikiPageWikiLink Q4755976.
- Q1522355 wikiPageWikiLink Q62870.
- Q1522355 wikiPageWikiLink Q629940.
- Q1522355 wikiPageWikiLink Q7011883.
- Q1522355 wikiPageWikiLink Q82438.
- Q1522355 wikiPageWikiLink Q9406976.
- Q1522355 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.".
- Q1522355 label "Toom–Cook multiplication".