Division of an array. What is the best way to split the two numbers stored in an array?

Question

I have two arrays (divend, divisor):

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

I need a result (divend / divisor) like:

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

I did this using array subtraction:

• subtract the divisor from the dividend until the dividend becomes equal to 0 or less than the divisor, each time increment of the quotient by 1,

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

Answer 1

Is there a better way to do this?

You can use a long split .

Answer 2

Make a long split.

It has temporary storage with a size equal to the divisor plus one, and is initialized to zero:

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

Now run the loop:

• Move each digit of the private space to the left.
• Slide each battery digit one place to the right.
• Make the next dividend figure, starting at the most significant end, and store it in the least significant place on the battery.
• Select accumulator / divisor and set the least significant place for the result. Install the battery on the rest.

It is used to use the same algorithm in assembly language for processors, which does not have separation instructions.

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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

in pseudo code:

 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; 

Answer 7

Go here! A is divident. B is a divisor. C is an integer R is the rest. Each "huge" number is a vector storing a large number. In huge [0], we store the number of digits, the number of which and the number are written in the reverse order. Let them say that we have number 1234, then the correction vector will 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=AB; 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 <- AB */ { 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]--; }