4
$\begingroup$

Using the grade school method of multiplying two binary numbers takes $O(n^2)$ time, where $n$ is the length of the number in bits. Why is this true?

  • 0
    @Artium Thanks, I added it in!2012-10-31

3 Answers 3

5

As computer scientists, we can consider two numbers to be multiplied, $A$ and $B$.

We can then rearrange the problem as follows. Let the smaller number have $n$ bits, and the larger number have $m$ bits. We can then break apart the larger number into chunks of $n$ bits, and perform seperate multiplications on these pieces. After this is done, we can add the results together.

Breaking the multiplication into pieces allows us to focus on the important part of multiplication, which then becomes two $n$ bit numbers. It's generally easiest to describe multiplication in this fashion, because all other multiplication problems generally reduce to this problem.

As for the $O(n^2)$ term, this comes from having to multiply each bit of $A$ with each bit of $B$. Since there are now $n$ bits in each number, this takes $n^2$ bit multiplicatoins. In general, we can describe this in asymptotic notation or Big-O notation.

All other operations require $n^2$ or less operations, so this is why we describe this as $O(n^2)$. For example, there are also approximately $n^2$ additions, or $O(n^2)$. This is because we take the multiplication results from multiplying all the bits together, of which there are $n^2$, and add them together. So this also takes $O(n^2)$. In general, there are $O(n^2)$ operations or less for each type of arithmatic that we use in the problem.

  • 0
    @Henn$i$ngMakholm Thanks!2012-10-31
1

Let $a$ and $b$ be binary numbers with $n$ digits. (We use $n$ digits for each since that is worst case.) When using the partial products (grade school) method, you take one of the digits of $a$ and multiply it with each digit of $b$. This single pass takes $n$ steps. This process must be repeated for each digit of $a$. Since $a$ has $n$ digits and $b$ has $n$ digits, the worst-case runtime is $O(n^{2})$.

  • 0
    Adding up the partial sums takes $O(n^{2})$ time. $O(n^{2} + n^{2}) = O(n^{2})$2012-10-31
0

This O(N^2) operattion is true for number larger than 64 bits. If the number fits in 64 bits this is done in 1 clockcyle or O(1)

  • 2
    Could you describe how a multiplication algorithm could be done in such case in O(1)? a link will be even better :)2014-03-04