c++ - 数组除法 - 将存储在数组中的两个数字相除的最佳方法是什么？

Question

我有两个数组（股息，除数）：

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

我需要结果（股息/除数）为：

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

我使用数组减法做到了这一点：

• 从被除数中减去除数，直到被除数变为 0 或小于除数，每次将商增加 1，

但这需要很长时间。有一个更好的方法吗？

Answer 1

做长除法。

有一个大小等于除数加一的临时存储，并初始化为零：

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

现在运行一个循环：

1. 将商的每个数字向左移动一个空格。
2. 将累加器的每个数字向右移动一个空格。
3. 取除数的下一位，从最高有效端开始，并将其存储到累加器的最低有效位置。
4. 找出accumulator / divisor商的最不显着位置并将其设置为结果。将累加器设置为余数。

曾经在没有除法指令的 CPU 的汇编语言中大量使用相同的算法。

Answer 2

除此之外，您是否考虑过使用 BigInt 类（或您的语言中的等价物）已经可以为您做到这一点？

Answer 3

您可以使用长除法http://en.wikipedia.org/wiki/Long_division

Answer 4

有一个更好的方法吗？

您可以使用长除法。

Answer 5

您可以使用长除法算法或更通用的多项式长除法。

Answer 6

为什么不将它们转换为整数，然后使用常规除法呢？

在伪代码中：

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

给你！A 是股息。B 是除数。C 是整数商，R 是余数。 每个“巨大”数字都是一个保留大数字的向量。在 huge[0] 中，我们保留数字的位数，然后将数字向后记忆。 假设我们有数字 1234，那么 corespoding 向量将是：

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]--;
            }