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 +,-,* ?
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 +,-,* ?
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)
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:
(copied from http://www.inf.ethz.ch/personal/wirt...s/Division.pdf)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.
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"
