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?

Answer 1

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.