Thread: Binary division of large numbers

  1. #1
    Registered User
    Join Date
    May 2007
    Posts
    2

    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.

  2. #2
    int x = *((int *) NULL); Cactus_Hugger's Avatar
    Join Date
    Jul 2003
    Location
    Banks of the River Styx
    Posts
    902
    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)
    2) Start with all digits 0.
    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.
    Start with: 0000.
    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.
    Last edited by Cactus_Hugger; 05-31-2007 at 02:49 PM.
    long time; /* know C? */
    Unprecedented performance: Nothing ever ran this slow before.
    Any sufficiently advanced bug is indistinguishable from a feature.
    Real Programmers confuse Halloween and Christmas, because dec 25 == oct 31.
    The best way to accelerate an IBM is at 9.8 m/s/s.
    recursion (re - cur' - zhun) n. 1. (see recursion)

  3. #3
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    The only thing I can suggest is a google search. http://www.google.ca/search?hl=en&q=...division&meta=

    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.

    [edit] Also, the last link contains text that should be a link:
    Extensive use of Wikipedia (http://en.wikipedia.org/wiki/Barcode)
    [/edit]
    Last edited by dwks; 05-31-2007 at 03:31 PM.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  4. #4
    Registered User
    Join Date
    May 2007
    Posts
    2
    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.

  5. #5
    int x = *((int *) NULL); Cactus_Hugger's Avatar
    Join Date
    Jul 2003
    Location
    Banks of the River Styx
    Posts
    902
    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)
    4) No carry, no digits. Add sub-answer to answer (0 + 615 = 615)
    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.
    Last edited by Cactus_Hugger; 05-31-2007 at 11:18 PM.
    long time; /* know C? */
    Unprecedented performance: Nothing ever ran this slow before.
    Any sufficiently advanced bug is indistinguishable from a feature.
    Real Programmers confuse Halloween and Christmas, because dec 25 == oct 31.
    The best way to accelerate an IBM is at 9.8 m/s/s.
    recursion (re - cur' - zhun) n. 1. (see recursion)

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary numbers?
    By Cherry65 in forum C++ Programming
    Replies: 11
    Last Post: 12-17-2008, 10:10 AM
  2. Replies: 3
    Last Post: 07-04-2008, 12:39 PM
  3. checking if binary numbers are palindromic
    By Beatz in forum C Programming
    Replies: 3
    Last Post: 01-24-2008, 01:49 PM
  4. how to deal wth large numbers
    By bvgsrs in forum C++ Programming
    Replies: 2
    Last Post: 06-18-2007, 06:16 AM
  5. Binary Numbers and Base 2 Calculation for Longs
    By SlyMaelstrom in forum Tech Board
    Replies: 8
    Last Post: 11-09-2005, 08:30 PM