只使用加法和乘法实现除法

首先，我假设"大小数"的意思是表示一个有理数，其中分母被限制为10的任意幂。

你需要认真思考两个小数除法的输出是什么。小数在加法、减法和乘法上是闭合的，但在除法上不是闭合的。也就是说，任何两个小数相乘都会产生第三个小数：（7/10）*（9/100）得出63/1000，这是另一个小数。但是除以这两个小数，你得到一个分母中没有10次方的有理数。

为了回答你实际提出的问题：就像乘法可以由循环中的加法构成一样，除法也可以由循环的减法构成。要将23除以7，请说：

• 是7<23？是的
• 23减去7得到16
• 是7<16？是的
• 16减去7得到9
• 是7<9？是的
• 9减去7得到2
• 是7<2.没有。我们有第一个数字。我们做了三次减法，所以第一个数字是3
• 2乘以10得到20
• 是7<20？是的
• 20减去7得到13
• 是7<13？是的
• 15减去7得到6
• 是7<6.没有。我们做了两次减法和一次10的乘法运算，所以下一个数字是2
• 6乘以10得到60
• 是7<60？是的
• 我们做了八次减法，所以下一个数字是8
• 。。。等等

你知道有什么更快的算法吗？

当然，有很多更快的除法算法。这里有一个：Goldschmidt算法。

首先，我希望很清楚，如果你试图计算X / D，那么你可以先计算1 / D，然后乘以X。此外，让我们假设WOLOG，D严格地在0和1之间。

如果不是呢？如果D为负数，则将其和X反转；如果D为零，则给出一个错误；如果D是1，则答案是X；如果D大于1，那么将它和X都除以10，这对你来说应该很容易，因为你的系统是十进制的。继续应用这些规则，直到你的D介于0和1之间。（作为额外的优化：当D很小时，算法是最慢的，所以如果D小于，比如说0.1，将X和D乘以10，直到D大于或等于0.1。）

好的，我们的问题是，我们有一个介于0和1之间的数字D，我们希望计算1 / D。也许最简单的事情就是做一个例子。假设我们正在尝试计算CCD_ 6。正确答案是1.42857142857...

从2减去0.7得到1.3。现在将分数的两部分乘以1.3:

(1 / 0.7) * (1.3 / 1.3) = 1.3 / 0.91

太好了。我们现在已经将1 / 0.7计算到一位数的准确度。

现在再做一次。2减去0.91得到1.09。将分数的两部分乘以1.09:

(1.3 / 0.91) * (1.09 / 1.09) = 1.417 / 0.9919

太好了，现在我们有两个正确的数字。现在再做一次。2减去0.9919得到1.0081。顶部和底部乘以1.0081:

(1.417 / 0.9919) * (1.0081 / 1.0081) = 1.4284777 / 0.99993439

嘿，现在我们有四个正确的数字。看看进展如何？每走一步，分母都会更接近1，因此分子也会更接近1 / 0.7。

这比减法收敛得快得多。

你明白为什么它有效吗？

由于D在0和1之间，所以存在一个数E，使得D＝1-E，并且E也在0和一之间。

当我们把D乘以（2-D）时，我们就是把（1-E）乘以（1+E），这就得到1-E²。

由于0<E<1，显然E²小于E，也在0和1之间，这意味着1-E²更接近1。事实上，它是一个批次，更接近1。通过多次重复这个过程，我们很快就会接近1。实际上，我们在这里所做的是将每一步的正确数字数量大致增加一倍。显然，这比减法要好得多，减法在每一步上给一个额外的数字。

继续这样做，直到你达到你想要的准确性。由于每一步的准确数字数量大约是原来的两倍，因此您应该能够很快达到可接受的准确度。由于我们已经安排D从一开始就大于或等于0.1，因此E永远不会大于0.9；反复求0.9的平方可以很快地把你降到一个很小的数字。

• 您可以在Java BigDecimal实现中找到一些想法
• 对于计算a/b，您可以使用二进制搜索算法来查找这样的c，即b*c=a（您应该运行算法，直到达到所需的精度）
• 你也可以看看这个BigFloat类，它有一个有趣的指数形式的实现
• 对于无限精度，您可以将BigDecimal存储为两个BigInteger的有理分式

有理分式表示的代数：

(x1/x2) + (y1/y2) = (x1*y2+x2*y1)/(x2*y2)    
(x1/x2) - (y1/y2) = (x1*y2-x2*y1)/(x2*y2)    
(x1/x2) * (y1/y2) = (x1*y1)/(x2*y2)
(x1/x2) / (y1/y2) = (x1*y2)/(x2*y1)

双精度（固定精度）实现示例：

public double Divide(double a, double b, double eps)
{
    double l = 0, r = a;
    while (r - l > eps)
    {
        double m = (l + r) / 2;
        if (m * b < a)
            l = m;
        else
            r = m;
    }
    return (l + r) / 2;
}

Eric Lippert的答案看起来很像"以最慢的方式进行长除法"。它是准确的，但不快。假设您有一种用双精度近似BigDecimal的方法，并且由于您已经在BD类中实现了+、-和*，您可以（近似地）执行以下操作：

BD operator/(BD a, BD b) {
  BD r, result=0, residual;
  double aa, bb, rr;
  residual = a;
  bb = b;
  while (residual > desired) {
    rr = (double)residual / bb;
    r = rr; // assuming you have a conversion from double to bigdecimal with loss of precision
    result += r;
    residual = a - (result * b);
  }
  return result;
}

这将进行逐次逼近，但同时需要多个数字（基本上，您可以使用BD算术找到错误，然后使用二重算术将其除法）。我认为这应该是一个相对直接和有效的方法。

我已经使用float和double实现了上面的一个版本——只是为了向自己证明这个原理是可行的。使用简单的C框架，只需要两次迭代就可以将精度降低到double除法的水平。我希望你明白。

#include <stdio.h>
double divide(double a, double b);
int main(void) {
  double a, b, result;
  float fa, fb, fr;
  a = 123.5;
  b = 234.6;
  fa = a;
  fb = b;
  fr = fa / fb;
  printf("using float: %f'n", fr);
  result = divide(a, b);
  printf("using double: %lf'n", result);
  printf("difference: %le'n", result - fr);
}
double divide(double a, double b) {
      double r, result=0, residual;
      float aa, bb, rr;
      residual = a;
      bb = b;
      while (residual > 1e-8) {
        rr = (float)residual / bb;
        r = rr; // assuming you have a conversion from double to bigdecimal with loss of precision
        result += r;
        residual = a - (result * b);
        printf("residual is now %le'n", residual);
      }
      return result;
    }

输出：

using float: 0.526428
residual is now 8.881092e-06
residual is now 5.684342e-14
using double: 0.526428
difference: 3.785632e-08