# Multiplication (Multiplication)

## 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)$ Exact Deterministic Time
Toom-3 1969 $O(n^{1.{4}6})$ $O(n)$ Exact Deterministic Time
Long Multiplication 1940 $O(n^{2})$ $O(n)$ Exact Deterministic
Schönhage–Strassen algorithm 1971 $O(n \log n \log\log n)$ $O(n)$ auxiliary? Exact Deterministic Time
Furer's algorithm 2007 $O(n \log n {2}^{O(\log*n)})$ $O(n)$ auxiliary? Exact Deterministic Time
De 2008 $O(n \log n {2}^{O(\log*n)})$ $O(n)$ auxiliary? Exact Deterministic Time
Harvey; Hoeven 2019 $O(n \log n)$ $O(n)$ auxiliary?? Exact Deterministic Time
Harvey; Hoeven; Lecerf 2015 $O(n \log n {2}^{({3} \log*n)})$ $O(n)$ auxiliary?? Exact Deterministic Time
Covanov and Thomé 2015 $O(n \log n {2}^{O(\log*n)})$ $O(n)$ auxiliary?? Exact Deterministic Time
Covanov and Thomé 2016 $O(n \log n {2}^{({3} \log*n)})$ $O(n)$ auxiliary?? Exact Deterministic Time
Harvey; Hoeven; Lecerf 2018 $O(n \log n {2}^{({2} \log*n)})$ $O(n)$ auxiliary?? Exact Deterministic Time