patternMinor
Multiplication in $O(n\cdot \log n)$
Viewed 0 times
logcdotmultiplication
Problem
I was looking in here, and I noticed the best runtime for multiplication of two $n$-bits numbers is $O(n\cdot \log n \cdot 2^{O(\log^* n)}$, but I can easily notice an algorithm that runs in $O(n\cdot \log n)$.
After all, we know how to multiply two polynomials from degree $n$ in $O(n \log n)$ runtime. But multiplying polynomials is the same as multiplying two $n$-bits numbers. So we have an algorithm to multiply two $n$-bits numbers in $O(n \log n )$. Now the only problem that might occur is the carry, but in each phase we can fix that in $O(n)$ time, simply moving on the rightest bit and its left-neighbour, until the end. That is, our runtime shall remain $O(n \cdot \log n)$.
So did I make a new (and pretty obvious) discovery? Or is the wikipedia page out of date? Or perhaps I have some mistake?
After all, we know how to multiply two polynomials from degree $n$ in $O(n \log n)$ runtime. But multiplying polynomials is the same as multiplying two $n$-bits numbers. So we have an algorithm to multiply two $n$-bits numbers in $O(n \log n )$. Now the only problem that might occur is the carry, but in each phase we can fix that in $O(n)$ time, simply moving on the rightest bit and its left-neighbour, until the end. That is, our runtime shall remain $O(n \cdot \log n)$.
So did I make a new (and pretty obvious) discovery? Or is the wikipedia page out of date? Or perhaps I have some mistake?
Solution
Saying that you can multiply two polynomials of degree $n$ in time $O(n\log n)$ implies that, in particular, you can multiply degree-zero polynomials, i.e., constants, in constant time. Clearly, therefore, the claims "multiplying $n$-bit numbers takes time $O(2^{\log^*n}n\log n)$" and "multiplying degree-$n$ polynomials takes time $O(n\log n)$" are relative to different models of computation so are not directly comparable.
Context
StackExchange Computer Science Q#33424, answer score: 9
Revisions (0)
No revisions yet.