
December 8th, 2002, 05:23 AM
|
|
Contributing User
|
|
Join Date: Dec 2001
Location: Houston, TX
Posts: 383
Time spent in forums: 1 h 41 m 27 sec
Reputation Power: 12
|
|
|
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.
|