Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Notice that n here represents the length of the number (number of it's binary digits) and not the number itself. –  Artium Oct 31 '12 at 23:30
    
@Artium Thanks, I added it in! –  awfsdioafj Oct 31 '12 at 23:34
add comment

3 Answers 3

up vote 1 down vote accepted

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.

share|improve this answer
    
@awfsdioafj: Welcome! Let us know if there is anything else that you would like to know. –  Matt Groff Oct 31 '12 at 23:47
    
Thank You! One last thing: Aren't there at most $2n$ additions? There are $2n -1$ columns + one additional possibly "carry over" 1. Why are there $n^2$ additions? –  awfsdioafj Oct 31 '12 at 23:52
    
@awfsdioafj: Yes, but each of those $2n$ additions has up to $n$ terms, so they don't complete in constant time each. (Which is strictly speaking besides the point because "$O(n^2)$" by definition expresses an upper bound, so counting too much work will never give a wrong big-O result). –  Henning Makholm Oct 31 '12 at 23:55
    
@HenningMakholm Thanks! –  awfsdioafj Oct 31 '12 at 23:58
add comment

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})$.

share|improve this answer
    
What about adding the numbers up? How long would they take? –  awfsdioafj Oct 31 '12 at 23:39
    
Adding up the partial sums takes $O(n^{2})$ time. $O(n^{2} + n^{2}) = O(n^{2})$ –  Unreasonable Sin Oct 31 '12 at 23:48
add comment

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)

share|improve this answer
    
Could you describe how a multiplication algorithm could be done in such case in O(1)? a link will be even better :) –  User Mar 4 at 15:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.