Multiplication: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
(Created page with "== Problem Description== Multiplication is one of the four elementary mathematical operations of arithmetic; with the others being addition; subtraction and division. == Bounds Chart == 1050px == Step Chart == 1050px == Improvement Table == {| class="wikitable" style="text-align:center;" width="100%" !width="20%" | Complexity Classes !! width="40%" | Algorithm Paper Links !! width="40%" | Lo...")
 
No edit summary
Line 1: Line 1:
== Problem Description==
{{DISPLAYTITLE:Multiplication (Multiplication)}}
Multiplication is one of the four elementary mathematical operations of arithmetic;
== Description ==  
with the others being addition; subtraction and division.


== Bounds Chart ==
Multiplication is one of the four elementary mathematical operations of arithmetic; with the others being addition; subtraction and division. Given two $n$-bit integers, compute their product, which should be a $2n$-bit integer.
[[File:MultiplicationBoundsChart.png|1050px]]


== Step Chart ==
== Parameters ==  
[[File:MultiplicationStepChart.png|1050px]]


== Improvement Table ==
<pre>n: length of one of the integers, in bits</pre>
{| class="wikitable" style="text-align:center;" width="100%"  
 
!width="20%" | Complexity Classes !! width="40%" | Algorithm Paper Links !! width="40%" | Lower Bounds Paper Links
== Table of Algorithms ==  
  |-
 
| rowspan="1" | Exp/Factorial
{| class="wikitable sortable" style="text-align:center;" width="100%"
|
 
|
! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference
 
|-
 
| [[Karatsuba Algorithm ( Multiplication)|Karatsuba Algorithm]] || 1962 || $O(n^{1.{5}8})$ || $O(n)$ auxiliary || Exact || Deterministic || [http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dan&paperid=26729&option_lang=eng Time]
|-
| [[Toom-3 ( Multiplication)|Toom-3]] || 1969 || $O(n^{1.{4}6})$ || $O(n)$ auxiliary || Exact || Deterministic || [https://www.ams.org/journals/tran/1969-142-00/S0002-9947-1969-0249212-8/S0002-9947-1969-0249212-8.pdf Time]
|-
| [[Long Multiplication ( Multiplication)|Long Multiplication]] || 1940 || $O(n^{2})$ || $O(n)$ auxiliary || Exact || Deterministic ||  
|-
| [[Schönhage–Strassen algorithm ( Multiplication)|Schönhage–Strassen algorithm]] || 1971 || $O(n logn loglogn)$ || $O(n)$ auxiliary? || Exact || Deterministic || [https://link.springer.com/article/10.1007/BF02242355 Time]
|-
| [[Furer's algorithm ( Multiplication)|Furer's algorithm]] || 2007 || $O(nlogn {2}^{O(log*n)$}) || $O(n)$ auxiliary? || Exact || Deterministic || [https://web.archive.org/web/20130425232048/http://www.cse.psu.edu/~furer/Papers/mult.pdf Time]
|-
|-
| rowspan="1" | Polynomial > 3
| [[De ( Multiplication)|De]] || 2008 || $O(nlogn {2}^{O(log*n)$}) || $O(n)$ auxiliary? || Exact || Deterministic || [https://arxiv.org/abs/0801.1416 Time]
|
|
|-
|-
| rowspan="1" | Cubic
| [[Harvey; Hoeven ( Multiplication)|Harvey; Hoeven]] || 2019 || $O(nlogn)$ || $O(n)$ auxiliary?? || Exact || Deterministic || [https://hal.archives-ouvertes.fr/hal-02070778 Time]
|
|
|-
|-
| rowspan="1" | Quadratic
| [[Harvey; Hoeven; Lecerf ( Multiplication)|Harvey; Hoeven; Lecerf]] || 2015 || $O(nlogn {2}^{({3}log*n)$}) || $O(n)$ auxiliary?? || Exact || Deterministic || [https://arxiv.org/abs/1407.3360 Time]
| [http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dan&paperid=26729&option_lang=eng Karatsuba Algorithm (1962)]
|-
| [[Covanov and Thomé ( Multiplication)|Covanov and Thomé]] || 2015 || $O(nlogn {2}^{O(log*n)$}) || $O(n)$ auxiliary?? || Exact || Deterministic || [https://hal.inria.fr/hal-01108166v1/document Time]
|-
| [[Covanov and Thomé ( Multiplication)|Covanov and Thomé]] || 2016 || $O(nlogn {2}^{({3}log*n)$}) || $O(n)$ auxiliary?? || Exact || Deterministic || [https://arxiv.org/abs/1502.02800 Time]
|-
| [[Harvey; Hoeven; Lecerf ( Multiplication)|Harvey; Hoeven; Lecerf]] || 2018 || $O(nlogn {2}^{({2}log*n)$}) || $O(n)$ auxiliary?? || Exact || Deterministic || [https://arxiv.org/abs/1802.07932 Time]
|-
|}


[https://www.ams.org/journals/tran/1969-142-00/S0002-9947-1969-0249212-8/S0002-9947-1969-0249212-8.pdf Toom-3 (1969)]
== Time Complexity graph ==


[ Long Multiplication (1940)]
[[File:Multiplication - Time.png|1000px]]


[https://link.springer.com/article/10.1007/BF02242355 Schönhage–Strassen algorithm (1971)]
== Space Complexity graph ==


[https://web.archive.org/web/20130425232048/http://www.cse.psu.edu/~furer/Papers/mult.pdf Furer's algorithm (2007)]
[[File:Multiplication - Space.png|1000px]]


[https://arxiv.org/abs/0801.1416 De 2008 (2008)]
== Pareto Decades graph ==


[https://arxiv.org/abs/1407.3360 Harvey; Hoeven; Lecerf (2015)]
[[File:Multiplication - Pareto Frontier.png|1000px]]


[https://hal.inria.fr/hal-01108166v1/document Covanov and Thomé (2015)]
== References/Citation ==


[https://arxiv.org/abs/1502.02800 Covanov and Thomé (2016)]
https://hal.archives-ouvertes.fr/hal-02070778
 
[https://arxiv.org/abs/1802.07932 Harvey; Hoeven; Lecerf (2018)]
|
|-
| rowspan="1" | nlogn
| [https://hal.archives-ouvertes.fr/hal-02070778 Harvey; Hoeven (2019)]
|
|-
| rowspan="1" | Linear
|
|
|-
| rowspan="1" | logn
|
|
|-|}

Revision as of 10:20, 15 February 2023

Description

Multiplication is one of the four elementary mathematical operations of arithmetic; with the others being addition; subtraction and division. Given two $n$-bit integers, compute their product, which should be a $2n$-bit integer.

Parameters

n: length of one of the integers, in bits

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Karatsuba Algorithm 1962 $O(n^{1.{5}8})$ $O(n)$ auxiliary Exact Deterministic Time
Toom-3 1969 $O(n^{1.{4}6})$ $O(n)$ auxiliary Exact Deterministic Time
Long Multiplication 1940 $O(n^{2})$ $O(n)$ auxiliary Exact Deterministic
Schönhage–Strassen algorithm 1971 $O(n logn loglogn)$ $O(n)$ auxiliary? Exact Deterministic Time
Furer's algorithm 2007 $O(nlogn {2}^{O(log*n)$}) $O(n)$ auxiliary? Exact Deterministic Time
De 2008 $O(nlogn {2}^{O(log*n)$}) $O(n)$ auxiliary? Exact Deterministic Time
Harvey; Hoeven 2019 $O(nlogn)$ $O(n)$ auxiliary?? Exact Deterministic Time
Harvey; Hoeven; Lecerf 2015 $O(nlogn {2}^{({3}log*n)$}) $O(n)$ auxiliary?? Exact Deterministic Time
Covanov and Thomé 2015 $O(nlogn {2}^{O(log*n)$}) $O(n)$ auxiliary?? Exact Deterministic Time
Covanov and Thomé 2016 $O(nlogn {2}^{({3}log*n)$}) $O(n)$ auxiliary?? Exact Deterministic Time
Harvey; Hoeven; Lecerf 2018 $O(nlogn {2}^{({2}log*n)$}) $O(n)$ auxiliary?? Exact Deterministic Time

Time Complexity graph

Multiplication - Time.png

Space Complexity graph

Multiplication - Space.png

Pareto Decades graph

Multiplication - Pareto Frontier.png

References/Citation

https://hal.archives-ouvertes.fr/hal-02070778

Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=Multiplication&oldid=43963"