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

  • MHB
  • Thread starter mathmari
  • Start date
  • Tags
    Operations
In summary: 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$$
  • #1
mathmari
Gold Member
MHB
5,049
7
Hey! :eek:

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?
 
Technology news on Phys.org
  • #2
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)
 
  • #3
I like Serena said:
Yes, that is correct. (Nod)

(Smile)
I like Serena said:
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?
 
  • #4
mathmari said:
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)
 

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

1. How do you count elementary operations?

Elementary operations are basic arithmetic operations such as addition, subtraction, multiplication, and division. Each time one of these operations is performed, it counts as one elementary operation.

2. Why is it important to know the number of elementary operations for adding two numbers with n digits?

Knowing the number of elementary operations can help determine the efficiency and complexity of an algorithm. This information can be used to compare different algorithms for adding large numbers and choose the most efficient one.

3. Is there a formula for calculating the number of elementary operations for adding two numbers with n digits?

Yes, there is a formula for calculating the number of elementary operations. For adding two numbers with n digits, the number of elementary operations is equal to 2n+1-1. This formula assumes that all digits in the numbers are non-zero.

4. Does the number of elementary operations increase as the number of digits in the numbers increases?

Yes, the number of elementary operations increases as the number of digits in the numbers increases. This is because for each additional digit, an extra elementary operation is needed to perform the addition.

5. Are there any shortcuts or tricks to reduce the number of elementary operations for adding two numbers with n digits?

There are some algorithms and techniques that can reduce the number of elementary operations for adding two numbers with n digits. Examples include Karatsuba's algorithm and using properties of numbers such as commutativity and associativity to rearrange the numbers for more efficient addition.

Similar threads

Replies
1
Views
1K
Replies
17
Views
1K
Replies
1
Views
825
Replies
3
Views
2K
Replies
6
Views
2K
Replies
14
Views
1K
Replies
9
Views
3K
Replies
2
Views
2K
Back
Top