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 +,-,* ?

Printable View

- 11-26-2011DuskoDividing 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 +,-,* ?

- 11-26-2011manasij7479
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) - 11-26-2011smokeyangel
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:

Quote:

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;

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. - 11-26-2011iMalc
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.