10
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What is the way that "we know" "to multiply two polynomials from degree $n$ in $O(n \log n)$ runtime"? $\hspace{.46 in}$ $\endgroup$ – user12859 Nov 24 '14 at 9:55
8
$\begingroup$

As @DavidRicherby already points out, the confusion arises because different measures of complexity are getting mixed up. But let me elaborate a bit.

Usually, when studying algorithms for polynomial multiplication over arbitrary rings, one is interested in the number of arithmetic operations in the ring that an algorithm uses. In particular, given some (commutative, unitary) ring $R$, and two polynomials $f,g \in R[X]$ of degree less than $n$, the Schönhage-Strassen algorithm needs $O(n \log{n} \log{\log{n}})$ multiplications and additions in $R$ in order to compute $fg \in R[X]$ by, roughly, adjoining $n$-th primitive roots of unity to $R$ to get some larger ring $D \supset R$ and then, using the Fast Fourier Transform over $D$, computing the product in $D$.

If your ring contains an $n$-th root of unity, then this can be sped up to $O(n \log n)$ operations in $R$ by using the Fast Fourier Transform directly over $R$. More specifically, over $\mathbb{Z} \subset \mathbb{C}$, you can do this using $O(n \log n)$ ring operations (ignoring the fact that this would require exact arithmetic over the complex numbers).

The other measure that can be taken into account is the bit complexity of an operation. And this is what we are interested in when multiplying two integers of bit length $n$. Here, the primitive operations are multiplying and adding two digits (with carry). So, when multiplying two polynomials over $\mathbb{Z}$, you actually need to take into account the fact that the numbers that arise during computation cannot be multiplied using a constant number of primitive operations. This and the fact that $\mathbb{Z}$ doesn't have an $n$-th primitive root of unity for $n > 2$ prevents you from appling the $O(n \log n)$ algorithm. You overcome this by considering $f,g$ with coefficients from the ring $\mathbb{Z}/\langle 2^n + 1 \rangle$, since the coefficients of the product polynomial will not exceed this bound. There (when $n$ is a power of two), you have (the congruence class of) $2$ as an $n$-th root of unity, and by recursively calling the algorithm for coefficient multiplications, you can achieve a total of $O(n \log n \log \log n)$ primitive (i.e., bit) operations. This then carries over to integer multiplication.

For an example that nicely highlights the importance of the difference between ring operations and primitive operations, consider two methods for evaluating polynomials: Horner's method and Estrin's method. Horner's method evaluates a polynomial $f = \sum_{i=0}^n f_i X^i$ at some $x \in \mathbb{Z}$ by exploiting the identity $$f(x) = (\ldots (f_n x + f_{n-1})x + \ldots + \ldots) + f_0$$ while Estrin's method splits up $f$ into two parts $$H = \sum_{i=1}^{n/2} f_{n/2+i} X^i$$ and $$L = \sum_{i=0}^{n/2} f_{i} X^i$$ i.e., $H$ contains the terms of degree $>n/2$ and $L$ the terms of degree $\leq n/2$ (assume $n$ is a power of two, for simplicity).

Then, we can calculate $f(x)$ using $$f(x) = H(x)x^{n/2} + L(x)$$ and applying the algorithm recursively.

The former, using $n$ additions and multiplications, is proven to be optimal w.r.t. the number of additions and multiplications (that is, ring operations), the latter needs more (at least $n + \log n$).

But, on the level of bit operations, one can (quite easily) show that in the worst case, Horner's method performs $n/2$ multiplications of numbers of size at least $n/2$, leading to $\Omega(n^2)$ many bit operations (this holds even if we assume that two $n$-bit numbers can be multiplied in time $O(n)$), whereas Estrin's scheme uses $O(n \log^c n) = \tilde{O}(n)$ operations for some $c > 0$, which is, by far, asymptotically faster.

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ I don't think this is the problem. If we think about numbers as polynomials whose "x" is the base, e.g. 2, then typically we can multiply degree-zero polynomials (numbers smaller than the base) in constant time. I'd guess the problem is that the O(n*log n) algorithm uses FFT and asymptotically larger numbers may emerge inside the FFT algorithm. $\endgroup$ – jkff Nov 23 '14 at 16:21

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.