MHB Answer: How Many Elementary Operations for Adding Two Numbers with $n$ Digits?

[mathmari]

Hey!

With the term "elementary operation" we mean to add two digits of the decimal system and to write the result and the carries. How many elementary operations do we need for the addition of two numbers with $n$ digits?
(we consider that the addition of two digits together with the carry that comes from previous operations is one elementary operation)

If we add two numbers with $n$ digits, we add at each step two digits, one of each number, and possibly a carry. That means that we need $n$ elementary operations.

Is this correct?

How could we show that the addition of any two numbers with $n$ digits each one of them, cannot be done with less than $n$ steps/elementary operations?

 

[I like Serena]

Hey! (Smile)

Yes, that is correct. (Nod)

To add two n-digit numbers, each digit will have to be processed.
So we need at least n operations. (Wasntme)

 

[mathmari]

Yes, that is correct. (Nod)

(Smile)

To add two n-digit numbers, each digit will have to be processed.
So we need at least n operations. (Wasntme)

I see... What about the multiplication? In this case we have to count separately the number of elementary additions and elementary multiplications (i.e., multiplications of two digits and writing the carries).
Can the multiplication of two $n$-digit numbers be done in less than $n$ elementary multiplications?
(we have to notice that the answer is not obvious as in the case of the addition. It can be done in about $cn \ln n$ elementary multiplications, for a constant $c$. This can be achieved using the Fast Fourier Transform. It is not known if this bound is optimal.) To multiplicate two $n$-digit numbers, do we not have to execute $n^2$ elementary multiplications and $2n-1$ elementary additions?

Could you explain to me how the Fast Fourier Transform is related to the multiplications of two numbers?

 

[I like Serena]

To multiplicate two $n$-digit numbers, do we not have to execute $n^2$ elementary multiplications and $2n-1$ elementary additions?

The straight forward way to multiply requires indeed $n^2$ elementary multiplications.
After that, I think it takes $n^2-1$ elementary additions though. (Wasntme)

Could you explain to me how the Fast Fourier Transform is related to the multiplications of two numbers?

Well, this is the first time I hear about it.
Let me see... (Thinking)

If we multiply $\sum a_i 10^i$ with $\sum b_j 10^j$, we get:
$$\sum_i a_i 10^i \cdot \sum_j b_j 10^j
= \sum_i\sum_j (a_i 10^i) \cdot (b_j 10^j)
= \sum_m\sum_i (a_i 10^i) \cdot (b_{m-i} 10^{m-i})
= \sum_m c_m
$$
This is the sum of a sequence of convolutions, meaning we can apply the convolution theorem:
$$
c_m = \mathscr F^{-1}\{\mathscr F\{a_m10^m\} \cdot \mathscr F\{b_m10^m\}\}
$$

Since the FFT takes $O(n\log n)$ operations, evaluating all $c_m$ also takes $O(n\log n)$ operations.
After that they only need to be summed.

To be honest, I'm still not clear how it would work exactly, but I suspect it works something like this. (Wasntme)