215

7
+4  Q:

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

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?

+1  A:

Is there a better way to do this?

You can use long division.

+1  A:

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

A:

Why not convert them to integers and then use regular division?

in pseudocode:

int dividend_number
foreach i in dividend
dividend_number *= 10
dividend_number += i

int divisor_number
foreach i in divisor
divisor_number *= 10
divisor_number += i

int answer = dividend_number / divisor_number;
This can easily cause overflow. If the OP could do this, he probably wouldn't be using arrays in the first place.
ya that is true, i am working with numbers having 100 digits.
I think the point is that the numbers in the array represent BigInts, that is, they have the potential to be much larger than can fit in an integer.
Ah, thought this was an academic exercise. Looks like he should be using something like GMP then, no?
+3  A:

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.

Which brings up the related question, "how do you compute accumulator / divisor?"
Use repeated subtractions, but with this method you'd do about 40 instead of 1,234,567 of them.
I don't remember the trick, exactly, but Knuth shows a way to do it with no more than two subtractions (rather than the 40 here) per digit of quotient. TAOCP vol. 2 I think.
+3  A:

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

BigInt class is applicable to only Java i guess and in C++ i'm not aware of anything that serves the purpose.
What about the GNU MP Bignum library - http://gmplib.org/. `GMP is a free library for arbitrary precision arithmetic, operating on signed integers, rational numbers, and floating point numbers`
Aye, and there's also OpenSSL's BigNum library.
+2  A:

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

A:

There you go! A is the divident. B is the divisor. C is the integer quotinent R is the rest. Each "huge" number is a vector retaining a big number. In huge[0] we retain the number of digits the number has and thren the number is memorized backwards. Let's say we had the number 1234, then the corespoding vector would be:

v[0]=4; //number of digits
v[1]=4;
v[2]=3;
v[3]=2;
v[4]=1;

....

SHL(H,1) does: H=H*10;
SGN(A,B) Compares the A and B numbers
SUBSTRACT(A,B) does: A=A-B;
DIVIDHUGE: makes the division using the mentioned procedures...

void Shl(Huge H, int Count)
/* H <- H*10ACount */
{
memmove(&H[Count+1],&H[1],sizeof(int)*H[0]);
memset(&H[1],0,sizeof(int)*Count);
H[0]+=Count;
}
int Sgn(Huge H1, Huge H2) {
while (H1[0] && !H1[H1[0]]) H1[0]--;
while (H2[0] && !H2[H2[0]]) H2[0]--;

if (H1[0] < H2[0]) {
return -1;
} else if (H1[0] > H2[0]) {
return +1;
}

for (int i = H1[0]; i > 0; --i) {
if (H1[i] < H2[i]) {
return -1;
} else if (H1[i] > H2[i]) {
return +1;
}
}
return 0;
}

void Subtract(Huge A, Huge B)
/* A <- A-B */
{ int i, T=0;

for (i=B[0]+1;i<=A[0];) B[i++]=0;
for (i=1;i<=A[0];i++)
A[i]+= (T=(A[i]-=B[i]+T)<0) ? 10 : 0;
while (!A[A[0]]) A[0]--;
}

void DivideHuge(Huge A, Huge B, Huge C, Huge R)
/* A/B = C rest R */
{ int i;

R[0]=0;C[0]=A[0];
for (i=A[0];i;i--)
{ Shl(R,1);R[1]=A[i];
C[i]=0;
while (Sgn(B,R)!=1)
{ C[i]++;
Subtract(R,B);
}
}
while (!C[C[0]] && C[0]>1) C[0]--;
}