December 5th, 2002, 09:41 AM
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?
December 7th, 2002, 04:22 PM
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...
December 8th, 2002, 05:23 AM
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.