Array Division - What is the best way to divide two numbers stored in an array?

Question

I have two arrays (dividend, divisor):

dividend[] = {1,2,0,9,8,7,5,6,6};
divisor[] = {9,8};

I need the result (dividend/divisor) as:

quotient[] = {1,2,3,4,5,6,7};

I did this using array subtraction:

• subtract divisor from dividend until dividend becomes 0 or less than divisor, each time incrementing quotient by 1,

but it takes a huge time. Is there a better way to do this?

Solution 1

Is there a better way to do this?

You can use long division.

Solution 2

Do long division.

Have a temporary storage of size equal to the divisor plus one, and initialized to zero:

accumulator[] = {0,0,0};

Now run a loop:

1. Shift each digit of the quotient one space to the left.
2. Shift each digit of the accumulator one space to the right.
3. Take the next digit of the dividend, starting from the most-significant end, and store it to the least-significant place of the accumulator.
4. Figure out accumulator / divisor and set the least-significant place of the quotient to the result. Set the accumulator to the remainder.

Used to use this same algorithm a lot in assembly language for CPUs what didn't have division instructions.

Solution 3

Other than that, have you considered using BigInt class (or the equivalent thing in your language) which will already does this for you?

Solution 4

You can use long division http://en.wikipedia.org/wiki/Long_division

Solution 5

You can use Long division algorithm or the more general Polynomial Long Division.

View more solutions