Software Design
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
User Name:
Password:
Remember me
Go Back   Dev Shed ForumsProgramming Languages - MoreSoftware Design

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Rate Thread Display Modes
 
Unread Dev Shed Forums Sponsor:
  #1  
Old December 5th, 2002, 10:41 AM
ninuzzo ninuzzo is offline
Junior Member
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Feb 2001
Location: south italy
Posts: 6 ninuzzo User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: < 1 sec
Reputation Power: 0
Send a message via ICQ to ninuzzo
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?

Reply With Quote
  #2  
Old December 7th, 2002, 05:22 PM
epl epl is offline
Contributing User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Mar 2001
Location: Dublin
Posts: 413 epl User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 2 h 18 m 18 sec
Reputation Power: 8
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...

Reply With Quote
  #3  
Old December 8th, 2002, 06:23 AM
Strike Strike is offline
Contributing User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Dec 2001
Location: Houston, TX
Posts: 383 Strike User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 1 h 41 m 27 sec
Reputation Power: 7
Send a message via ICQ to Strike Send a message via AIM to Strike Send a message via Yahoo to Strike
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.

Reply With Quote
Reply

Viewing: Dev Shed ForumsProgramming Languages - MoreSoftware Design > division algorithm for big number arithmetic


Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump


Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
  
 





© 2003-2008 by Developer Shed. All rights reserved. DS Cluster 4 hosted by Hostway
Stay green...Green IT