I was told that the fastest possible algorithm for integer multiplication is $O\left(n{\log}(n)\right)$. Why would this so?
Can you please show why the fastest multiplication algorithm would have such a time complexity?
0
$\begingroup$
$\endgroup$
-
1$\begingroup$ Where did you get this lower bound information? Are you sure it represents the theoretical lower bound for all possible algorithms? $\endgroup$ – cody Jul 8 '17 at 16:28
-
$\begingroup$ What exactly are you multiplying? $\endgroup$ – Juho Jul 8 '17 at 16:31
-
1$\begingroup$ Where did you get that idea from (your claim about the running time of multiplication)? See en.wikipedia.org/wiki/…, en.wikipedia.org/wiki/Multiplication_algorithm, en.wikipedia.org/wiki/Multiplication_algorithm#Lower_bounds, en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm, en.wikipedia.org/wiki/F%C3%BCrer%27s_algorithm. $\endgroup$ – D.W.♦ Jul 8 '17 at 17:37
-
1$\begingroup$ @TobiAlafin, no, these algoritms take time bigger than $O(n\log n)$. Also, it's a conjecture that multiplication can't be done faster in that time. The only known bound is $\Omega(n)$. $\endgroup$ – rus9384 Jul 8 '17 at 18:53
-
1$\begingroup$ While it is conjectured that integer multiplication is $\Omega(n\log n)$, there are no non-trivial lower bounds known. $\endgroup$ – Yuval Filmus Jul 8 '17 at 22:07
1
$\begingroup$
$\endgroup$
Multiplication of n-bit integers can be done in $O (n \log n)$ if you are a bit careless in calculating the complexity, for example using convolution and FFT. You need $O (n \log n)$ floating point operations, but as n grows larger, you need to increase (very slowly) the precision of the floating-point operations, which will increase the complexity a little bit.
It is very well possible that no algorithm can be faster than $O (n \log n)$. It is a bit more possible that we will never find such an algorithm. However, I'm not aware of anything coming even close to a proof.
Proofs for lower bounds that turn out to be actually achieved are usually either very simple or nonexistent. For example the proof that sorting n items using comparisons takes $O(n \log n)$ is quite simple. When someone writes "multiplication cannot be done faster than $O(n \log n)$", that most likely means "I have not the slightest idea how this could be done".
-
1$\begingroup$ In which computation model can you multiply integers in $O(n\log n)$? $\endgroup$ – Yuval Filmus Jul 8 '17 at 22:08
