3
$\begingroup$

The multiplication of two integers of size $n$ can be done in time $O(n \cdot \log n \cdot \log\log n)$ using FFT method.

If the two integers have different sizes $n$ and $m$, does a smaller upper bound using $n$ and $m$ exists ?

$\endgroup$
4
  • $\begingroup$ If you replace $n$ in the upper bound you gave with $\max(n, m)$ (or equivalently with $n+m$), you get an upper bound for the different-sizes case, since you can always left-pad the smaller number with zeros; you could even replace it with, say, $n^3m^7$ and this would give you an upper bound. If those aren't satisfying answers, then you're probably looking for the smallest known upper bound. (Which I don't know, sorry.) $\endgroup$ – j_random_hacker Jan 18 '19 at 16:00
  • $\begingroup$ If $m = O(1)$ then the answer is $O(n)$. So there's probably a nontrivial tradeoff. $\endgroup$ – Yuval Filmus Jan 18 '19 at 16:35
  • $\begingroup$ Do the convolutional methods actually require $m=n$? $\endgroup$ – David Richerby Jan 18 '19 at 16:55
  • $\begingroup$ One thing to try, assuming $n\ge m$, is to reduce to $n/m$ products of $m$-bit numbers (followed by the requisite additions). $\endgroup$ – Yuval Filmus Jan 18 '19 at 21:49
1
$\begingroup$

The multiplication of two integers of size $n$ and size $m$ in base-2 with $n\le m$ can be done in time $$O(m\cdot\log n\cdot\log\log n)$$ where the product will be given in base-2 as well.

Here is a sketch of the simple idea to prove the above claim.


Let positive integer $a$ has $n$ digits and positive integer $b$ have $m$ digits in base 2. For simplicity, let $m=kn$ for some integer $k$. $$b=\sum_{i=0}^{k-1}\sum_{j=0}^{n-1}b_{i,j}2^{in+j}=\sum_{i=0}^{k-1}2^{in}b_i$$ where $0\le b_{i,j}\le1$, $b_i=\sum_{j=0}^{n-1}b_{i,j}2^j$. In other words, $b_{k-1}\cdots b_1b_0$ is $b$ in base-$2^n$. So $$ab= \sum_{i=0}^{k-1}2^{in}(ab_i).$$

Since both $a_i$ and $b_i$ have $n$ digits, the product $ab_i$ can be computed in $O(n\cdot\log n\cdot\log\log n)$ (using FFT method). Multiplying by factor $k=\dfrac mn$, we see that all summands in the above equality and hence $ab$ can be computed in $O(m\cdot\log n\cdot\log\log n)$. Note that the computation cost of various bookkeeping and additions is not substantial enough to invalidate that bound.


This idea of splitting the bits of the bigger number by the length of the bits of the smaller number is articulated here first in Yuval's comment. That idea is, apparently, folklore among users experienced in algorithms.

If we have a smaller bound for the multiplication of the integers of the same size, we will get a smaller bound for the multiplication of integers of different sizes accordingly. For example, an algorithm by Harvey and van der Hoeven gives bound $O(n\log n\cdot 2^{2\log ^{*}n})$. So we will have bound $O(m\log n\cdot 2^{2\log ^{*}n})$ accordingly.

$\endgroup$
0
0
$\begingroup$

There is a trivial upper bound O (n * m). If m = o (log n log log n) then this is better than O (n log n log log n).

I think it will be very hard to beat O (max (n*m, n log n log log n)) for m ≤ n.

PS. Wrong, wrong, wrong: Look at apass.jack's answer. Of course if you have say n = 1,000,000 and m = 100,000 then there isn't much savings.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.