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

Join Date
Feb 2002
Posts
3
Rep Power
0

#### Divide algorithm

Hello,

I'm working on a big number library (for learning purposes). I'm trying to come up with the best divide function for an arbitraraly long number (multiple of 32 bits - dword).

What would be best?

Repeated subtraction? or a combination of bit shifts and repeated subtraction?

what has the best worst case run time? average run time?

What would be the best way to come up with the combination of bit shifts + subtraction?

-cARL

• Gran Roguismo agrees
• BaronVonDoppleG agrees
2. No Profile Picture
WoR
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Mar 2002
Posts
20
Rep Power
0
repeated subtraction can be exponentiol in hte number of bits used; example:
bigNumber_N_bits / 1
needs 2 exp N subtractions. Each subtraction is again linear in N
So the result will be O(N*expN) (less than perfect)

with potential N output bits you get
O(NlogN) (better and likely optimal in O() notation)

As for the constants (practical programming), doing a full subtraction for each output bit is tough.
You might want to consider working only on a limited window of bits and keeping track of the operations you missed on the data outside of the window.
I don't know if it works at all (just an idea). It certainly won't spare you any of the O() operations,
but might localize data access a bit more and thus run faster. Window size should grow with log of bitnumber N, else the number of operations stored will be linear in N and you don't gain anything.

I hope this helps

• Gran Roguismo agrees
• BaronVonDoppleG agrees
3. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Mar 2002
Location
Oxford, UK
Posts
28
Rep Power
0
The fastest known division algorithm (for normal cases) is called non-restoring division. If you do a search on google, you'll get plenty of hits (its what CPUs use).