Multiplication

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

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 11 of 11 algorithms


Harvey; Hoeven	2019	$O(n \log n)$	$O(n)$ auxiliary
Harvey; Hoeven; Lecerf	2018	$O(n \log n 2^{2 \log^*n})$	$O(n)$ auxiliary
Covanov and Thomé	2016	$O(n \log n 2^{3 \log^*n})$	$O(n)$ auxiliary
Harvey; Hoeven; Lecerf	2015	$O(n \log n 2^{3 \log^*n})$	$O(n)$ auxiliary
Covanov and Thomé	2015	$O(n \log n 2^{O(\log^*n)})$	$O(n)$ auxiliary
De	2008	$O(n \log n 2^{O(\log^*n)})$	$O(n)$ auxiliary
Furer's algorithm	2007	$O(n \log n 2^{O(\log^*n)})$	$O(n)$ auxiliary
Schönhage–Strassen algorithm	1971	$O(n \log n \log\log n)$	$O(n)$ auxiliary
Toom-3	1969	$O(n^{1.46})$	$O(n)$
Karatsuba Algorithm	1962	$O(n^{1.58})$	$O(n)$
Long Multiplication	1940	$O(n^2)$	$O(n)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms