#1
  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

    Comments on this post

    • Gran Roguismo agrees
    • BaronVonDoppleG agrees
  2. #2
  3. No Profile Picture
    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)

    shifting will be log in each output bit
    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

    Comments on this post

    • Gran Roguismo agrees
    • BaronVonDoppleG agrees
  4. #3
  5. 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).

    Comments on this post

    • Gran Roguismo agrees
    • BaronVonDoppleG agrees

IMN logo majestic logo threadwatch logo seochat tools logo