Dividing numbers with up to 100 digits

This is a discussion on Dividing numbers with up to 100 digits within the C++ Programming forums, part of the General Programming Boards category; How would you divide huge numbers that are stored in arrays and have between 1 and 100 digits, i already ...

  1. #1
    Registered User
    Join Date
    Apr 2011
    Posts
    13

    Dividing numbers with up to 100 digits

    How would you divide huge numbers that are stored in arrays and have between 1 and 100 digits, i already implemented some basic arithmetic operations like +,-,* ?

  2. #2
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    Well... remember the 'long' division method you learnt in primary school?
    Try that out..
    (I don't know if there is a better algorithm for division....like in multiplication)
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  3. #3
    Registered User
    Join Date
    Mar 2010
    Posts
    535
    Do you want the result as integer quotient and remainder? Or do you want to end up with a fractional (floating or fixed point) number?

    For integer division there are plenty of optimised algorithms (see , but I think they're all quite complex... as far as I know there isn't an easy, efficient way.

    I can't remember the method I used last time I did something like this..... I know it had something to do with shifting and subtracting. I think it was like this:

    Integer division can be done by the conventional algorithm using repeated subtraction and
    shifting by a single digit. First the divisor y is shifted left until it is larger than the dividend x. Let q
    be the quotient and r the remainder. We assume 0 ≤ y < x. Note that multiplication by 2 is a left
    shift by 1 digit, and division by 2 by a right shift. With the precondition 0 < y ≤ x, the result
    satisfies q*y + r = x and 0 ≤ r < y.

    r := x; q := 0; y0 := y;
    REPEAT y := 2*y UNTIL y > x;
    REPEAT y := y DIV 2; q := 2*q;
    IF r >= y THEN r := r - y; q := q+1 END
    UNTIL y = y0;
    (copied from http://www.inf.ethz.ch/personal/wirt...s/Division.pdf)

    I don't remember this being too troublesome - it does involve implementing a raft of other operations though: shifting, masking, comparisons.. but I don't think there's a way around that. Depending on what you're trying to do, it might be better to just pick up an arbitrary precision arithmetic library rather than re inventing the wheel.

    If you do decide to reinvent the wheel, I've found Python really useful in validating my results since it supports arbitrary length integer arithmetic.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    It depends on how the numbers are "stored in arrays". If the digits are held as their ASCII value in one byte each for example, then it is easy to divide by powers of 10, you just remove digits from the end.
    If you store it in binary then you need to do it differently.
    We can't really give you an answer that will work for you unless we see some code that shows how you're storing stuff and how you're doing some of the operations.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Counting Digits & Numbers
    By yacek in forum C Programming
    Replies: 4
    Last Post: 10-06-2010, 08:44 PM
  2. dividing a multi-digit into single-digits
    By doctorevil in forum C++ Programming
    Replies: 13
    Last Post: 08-09-2007, 04:51 PM
  3. Dividing numbers?
    By elfjuice in forum C++ Programming
    Replies: 5
    Last Post: 05-28-2002, 10:16 AM
  4. Dividing int numbers by 256, but fast!
    By Boksha in forum C++ Programming
    Replies: 4
    Last Post: 04-04-2002, 02:44 PM
  5. Number system base M, print numbers N digits wide...
    By biterman in forum C Programming
    Replies: 12
    Last Post: 11-19-2001, 03:31 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21