# Binary division of large numbers

• 05-31-2007
hooper
Binary division of large numbers
Hi,

As a newbie to this forum can I first say that I'm far from an expert programmer. I write in C using gcc on a Linux machine, and I'm always surprised when something actually works! Please could anyone help me with a problem I can't see any way to resolve?

I am trying to make an encoder for OneCode, the new 4-state barcode system used by the USPS. Once done it will form part of my larger barcode encoding project at (http://rjstuart.pwp.blueyonder.co.uk/zint).

Following the instructions on the USPS website I have got as far as the correct calculation of a 102-digit binary number which I have stored in a short int array (not the best use of memory, but it works). In order to get this far I have already written functions which handle binary addition, subtraction and multiplication. The next step is that I need to divide. As an example (in hex):

016907B2A24ABC16A2E5C004B1 divided by 27C.

I will need both the quotient and the remainder. I have written code that will recursively take away until I get a negative number, and from it I can get the correct values, but it takes forever to do the calculation this way. I've looked at the 'long division' method of binary division but can't figure out how to put it into code.

I'm sure there must be a quicker way, but how?

Thank you for any suggestions.
• 05-31-2007
Cactus_Hugger
If you don't mind the extra bulk of a library, libgmp is a math library for large numbers.

This Wikipedia article may be of help to you.

Otherwise, I once implemented division thus, which should be quicker than your way:
1) Find the smallest number of digits that can contain the answer. For base-10, this is: (number_of_digits_in_numerator) - (number_of_digits_in_demoninator - 1) + 1 (for safety/rounding) This is the max. number of digits possible in your answer. (But may be less)
3) Take the most significant digit, increment it by one.
4) Multiply the number by the denominator.
5) If the result of the multiplication is larger than the numerator, reduce the digit that was incremented by 1, and move down to the next less significant place. Repeat to step 3 using this digit. If there is no less significant digit, you're done.

Example:
100 / 5
Digits to use: 3 - (1 - 1) + 1 = 4.
1000 * 5 = 5000, too big.
0100 * 5 = 500, too big.
0010 * 5 = 50, too small.
0020 * 5 = 100, right on. (Special case, quit early!)

This algorithm needs only (digits_in_answer * base) iterations to find an answer. Although my examples (and implementation) was in base-10, it should work the same in base-2.
• 05-31-2007
dwks

BTW, the "license" link in your contents does not work. Also, I think "GNU Public Licence" should be "GNU General Public Licence", but perhaps what you have is sufficient.

 Also, the last link contains text that should be a link:
Quote:

Extensive use of Wikipedia (http://en.wikipedia.org/wiki/Barcode)
[/edit]
• 05-31-2007
hooper
I'm afraid the Wikipedia article may as well be in Russian for all I understand of it.

I think you're on to something with that division method, however. It wouldn't cut down any processing time as it is because it would still have to work out 1000 * 5 as 5+5+5+5...., but if I combine it with a lookup table to take shortcuts (like "1000 * 5 makes 5000, so don't bother to work it out!") it might be just what I'm looking for. I'll play with it a bit and see if I can make it work.

Thanks.
• 05-31-2007
Cactus_Hugger
Quote:

It wouldn't cut down any processing time as it is because it would still have to work out 1000 * 5 as 5+5+5+5....
Multiplication can be implemented better than that. Think of how a student works out a multiplication problem, and you'll get a decent algorithm with just that.

First, for any multiplication problem, especially ones like 1000 * 5, do not do 5 + 5 + 5..., even if that is your algorithm of choice. Reverse your operands: 1000 + 1000 + 1000 + 1000 + 1000, done.

Take 123 * 45:
Code:

```123  45 ---```
Always place the operand with less digits on bottom. (Swapping operands by calling your multiplication function recursively is usually sufficient, depending on your data structures.) From there, take each single digit, and multiply it as a schoolchild would, getting a total for that digit. For our problem:
1) 5 * 3 = 15. Record the 5, carry the 1. (Sub-answer: '5', Answer: 0)
2) 5 * 2 = 10 + carry = 11. Record the 1, carry the 1. (Sub-answer: '15', answer: 0)
3) 5 * 1 = 5 + carry = 6. (Sub-answer: '615', answer: 0)
5) Repeat for next digit (4 * 123 = sub answer of 492. Since this is tens place, multiply the sub answer by 10. (100 for hundreds, 1000 for thousands, etc)). 4920 + 615 = 5535.

Using this algorithm, all the multiplications should be simple (for base-10 or base-2) and not require bignumber work. After that, your bignum adder is called only as many times as there are digits in the smaller operand, minus 1. (No addition is needed in 1000 * 5.)

Again, try wiki. This article has info on multiplying. The method I've attempted to demonstrate is the first one, long multiplication. The "Peasant or binary multiplication" may be more useful to you. (I read that part, and it's easy enough to understand.)

And if it requires this much work with large numbers, perhaps you should think about libgmp, or some other library. No point in reinventing the wheel, and their work is likely going to be faster and less prone to bugs.
• 06-01-2007
iMalc
Psuedo code for the basics of division (A / B):
Code:

```set result to zero do     shift result left 1 bit     if B <= A then subtract B from A and increment result     shift B right 1 bit while B != 0 result contains the answer A contains the remainder```
C++ code for this is here:
http://homepages.ihug.co.nz/~aurora7...ul_Classes.htm