#1
  1. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2001
    Location
    south italy
    Posts
    6
    Rep Power
    0

    division algorithm for big number arithmetic


    I want to write a library to handle bit integer number arithmetic for the C programming language, using i386 assembler. I will represent every big number as a double word (32bit) sequence.

    I know how to perform addition (it's quite easy, i will propagate the carry bit from the least significant dword to the most significant one). I also can cope with subtraction and multiplication .

    But how about division? I can't figure out a simple algorithm for this except using multiple subtractions which is inefficient. I know the rules from division from primary school but they seem not easy to implement.

    how IDIV and DIV is implemented inside the processor (with two complement numbers)?
    what's the algorithm?
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2001
    Location
    Dublin
    Posts
    413
    Rep Power
    14
    i'm not 100% but i guess it's the same as you learned in school.
    try doing binary long division exactly as you learned to do decimal division and i think you'll have it...
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2001
    Location
    Houston, TX
    Posts
    383
    Rep Power
    14
    This is the algorithm I have from my Computer Hardware class's textbook Computer Organization & Design:

    It requires a 64 bit register (or equivalent), which we will call the Remainder register (following the book convention, which goes through 3 iterations, eventually removing all data storage but the Divisor and Remainder register) and a Divisor register, which is 32 bit.

    1. Store the dividend in the right half of Remainder
    2. Shift Remainder left one bit
    3. Subtract Divisor from Remainder, store the result in the left half of Remainder.
    4. Test Remainder
    4a. (Remainder >= 0) Shift Remainder left one bit, set rightmost bit to 1
    4b. (Remainder < 0) Add Divisor back to the left half of Remainder, replace left half of Remainder with sum. Shift Remainder left, set rightmost bit to 0.
    5. Test iteration count.
    5a. (done this 32 times) Shift left half of Remainder right 1 bit.
    5b. (done it <32 times) Go back to step 3.
    Debian - because life's too short for worrying.
    Best. (Python.) IRC bot. ever.

IMN logo majestic logo threadwatch logo seochat tools logo