[Math] How many number of multiplication/addition operations are there in a multiplication of two numbers of equal length

algorithmsarithmetic

BACKGROUND:

Note: The following question arose in my mind when watching this lecture (watch at 5:30 minutes if you will).

Assumption: Just for the sake of this question, let's assume that the term "basic operation" means an addition or a multiplication operation between two single-digit numbers.

Now we have to calculate the number of basic operations involved in the multiplication of any two numbers, provided that both the numbers have the same length (i.e. the number of digits).

Let's say "n" represents the length of the numbers.

Let the numbers be 1234 and 5678. The following image shows the multiplication:

enter image description here

As you can see, each row (i.e. each partial product of the first number with a digit of the second number) involves 4 multiplication operations, and 4 addition operations (think of the carries). Depending on the number of carries (and thus depending on the original numbers), in the case of any two numbers, in each row, it could be at least 0 additions (no carry) and at most 4 additions (a carry from each digit-to-digit multiplication).

In other words, each row involves less-than-or-equal-to "2n" operations. As there are n rows, so the basic operations in all the rows are n(2n), or 2n2.

QUESTION:

Now comes that one final addition (shown in black pen in the image). From the video lecture

The final addition requires a comparable number of operations.
Roughly, say, another at-most 2n2 operations.

The question is

  1. What is meant by "comparable" number of operations?

  2. How did they find this "at-most 2n2" operations?

Best Answer

2) How did they find this "at-most $2n^2$" operations?

Lets consider the final addition part. For final addition, we are basically adding 4 numbers (results of multiplication by each digit). We can represent them like below (dashes and blank spaces replaced by 0's)

r1:0022712
r2:0170340
r3:1135600
r4:5678000

Now addition of $r_1$ and $r_2$ takes 7 basic opeartions.
Similarly addition of result of $(r_1+r_2)$ and $r_3$ takes 7 basic operations.
Similarly addition of result of $(r_1+r_2+r_3)$ and $r_4$ takes 7 basic operations.

A total of 21 operations for final addition. Here we are multiplying two small numbers. But if we would have multiplied $9999 \cdot 9999$ then final addition would be of 24 operations, i.e.
$$ r_1 - 00089991 + r_2 - 00899910 + r_3 - 08999100 + r_4 - 89991000 $$ 24 operations $= 2 n^2 - 2 n$ with $n = 4$ in our case.

(24 operations without considering carry overs. I am not sure if carry overs were also counted as additional opeartions by Tim Roughgarden)

Reference : https://people.mpi-inf.mpg.de/~mehlhorn/ftp/chapter2A-en.pdf

Related Question