MHB Multiplication of two n-bit numbers

[mathmari]

Hey!

I am looking at the divide-and-conquer technique for the multiplication of two $n-$bit numbers.First of all, why does the traditional method of the multiplication of two $n-$bit numbers require $O(n^2)$ bit operations?? (Wondering)

The divide-and-conquer approach is the following:

Let $x$ and $y$ be two $n-$bit numbers. (For simplicity we assume that $n$ is a power of $2$.)

We partition $x$ and $y$ into two halves as followed:

View attachment 3595

If we treat each half as an $(n/2)-$bit number, then we can express the product as follows:

$$xy=(a2^{n/2}+b)(c2^{n/2}+d)=ac2^n+(ad+bc)2^{n/2}+bd \ \ \ \ \ (*)$$

Equation $(*)$ computes the product of $x$ and $y$ by four multiplications of $(n/2)-$bit numbers plus some additions and shifts (multiplications by powers of $2$).

Could you explain me the partition of $x$ and $y$?? (Wondering)

Also, why do we write the product as in $(*)$ ?? (Wondering)

 

[I like Serena]

Hey!

I am looking at the divide-and-conquer technique for the multiplication of two $n-$bit numbers.First of all, why does the traditional method of the multiplication of two $n-$bit numbers require $O(n^2)$ bit operations?? (Wondering)

The divide-and-conquer approach is the following:

Let $x$ and $y$ be two $n-$bit numbers. (For simplicity we assume that $n$ is a power of $2$.)

We partition $x$ and $y$ into two halves as followed:

https://www.physicsforums.com/attachments/3595

If we treat each half as an $(n/2)-$bit number, then we can express the product as follows:

$$xy=(a2^{n/2}+b)(c2^{n/2}+d)=ac2^n+(ad+bc)2^{n/2}+bd \ \ \ \ \ (*)$$

Equation $(*)$ computes the product of $x$ and $y$ by four multiplications of $(n/2)-$bit numbers plus some additions and shifts (multiplications by powers of $2$).

Could you explain me the partition of $x$ and $y$?? (Wondering)

Also, why do we write the product as in $(*)$ ?? (Wondering)

Hi! (Mmm)

Suppose we create a similar example using normal digits.

Suppose we want to calculate $1234 \cdot 5678$.

A straightforward way to calculate it, is by calculating:
$$1234 \cdot 5678 = \underbrace{5678 + 5678 + ... + 5678}_{1234\text{ terms}}$$
which takes $1234-1=1233$ additions.
This is not very efficient. (Worried)
Alternatively, we can split up the numbers:
$$1234 \cdot 5678 =(12\cdot 100 + 34) \cdot (56 \cdot 100 + 78)
= 10000 (12 \cdot 56) + 100 (12\cdot 78 + 34 \cdot 56) + 34\cdot 78$$
Note that multiplying by 10 doesn't really count - we can just add zeroes at the end, so that is easy. It's called a shift operation. (Thinking)

That leaves us with 4 multiplications, that we can again evaluate by additions.
It would take$12 + 12 + 34 + 34 + 3 -3 = 92$ additions and $3$ shift operations.

Hey!
That is much less than the $1233$ additions that we had before! (Sun)

 

[Evgeny.Makarov]

Suppose we want to calculate $1234 \cdot 5678$.

A straightforward way to calculate it, is by calculating:
$$1234 \cdot 5678 = \underbrace{5678 + 5678 + ... + 5678}_{1234\text{ terms}}$$
which takes $1234-1=1233$ additions.

The question was about the number of operations in terms of the number of bits. If we treat multiplication as repeated addition, then the number of additions is exponential, not quadratic, in the number of bits.

Note also that the complexity of this divide-and-conquer algorithm satisfies
\[
T(n)=4T(n/2)+f(n)
\]
so $T(n)=\Theta(n^2)$, just like for naive long multiplication. However, if (*) in post #1 is written in a different way, then it would require only three multiplications of $n/2$-bit numbers.

 

[I like Serena]

The question was about the number of operations in terms of the number of bits. If we treat multiplication as repeated addition, then the number of additions is exponential, not quadratic, in the number of bits.

I have shown that in base-10 instead of base-2, we can reduce the number of operations from 4 digits to 2 digits (as opposed to bits).

Base-10 should be more intuitive, since human multiplication is typically done by breaking up the numbers into digits, as we humans just happen to know the table for multiplications of 1 digit by heart.

 

[Evgeny.Makarov]

I am not talking about the base. If we implement multiplication as repeated addition, the number of additions will be exponential in the number of bits or digits. This is not the complexity the problem is talking about. It says that long multiplication takes quadratic number of operations in the number of bits or digits.

 

[I like Serena]

I am not talking about the base. If we implement multiplication as repeated addition, the number of additions will be exponential in the number of bits or digits. This is not the complexity the problem is talking about. It says that long multiplication takes quadratic number of operations in the number of bits or digits.

Yes.
So the divide-and-conquer strategy leads to $O(n^2)$, which is what the whole partition idea is about.
Otherwise we'd get $O(2^n)$.

 

[Evgeny.Makarov]

Otherwise we'd get $O(2^n)$.

That's not what the OP says.

First of all, why does the traditional method of the multiplication of two $n-$bit numbers require $O(n^2)$ bit operations?

Since repeated addition is exponential in the number of bits, mathmari could not have meant it by the "traditional method of the multiplication". So, it must mean long multiplication. Compared to it, the given divide-and-conquer algorithm is not asymptotically faster.