c# - 仅使用加法和乘法来实现除法

Question

我正在C＃中编写BigDecimal类。我已经成功实现+，-和*运算符。但是我想不出一种方法来计算2个BigDecimals的除法。使用这3个运算子执行除法的最快方法是什么？还是有更好的方法来做到这一点？ （考虑开发时间和算法速度）

目标1：我希望结果是另一个具有固定精度的BigDecimal（应该可以更改）

目标2：正如您提到的，BigDecimal的目的不是固定的精度。那么如何获得无限的精度呢？

另一个问题：将Microsoft BCL的BigRational类用于任意精度算法，然后在该线程中使用Christopher Currens的扩展方法是否更好（在速度和灵活性方面）：Is there a BigFloat class in C#?获取小数表示而不是编写一个新类？

Answer 1

首先，我假设用“大十进制”表示您表示一个有理数，其中分母被限制为10的任何幂。

您将要认真考虑要让小数点后两位的输出是什么。小数在加，减，乘运算中是封闭的，但在除法运算中是不封闭的。也就是说，任何两个小数相乘会产生第三个：（7/10）*（9/100）给您63/1000，这是另一个小数。但是，将这两个小数除以得到的分母中没有十的幂的有理数。

要回答您实际提出的问题：就像可以在循环中通过加法构建乘法一样，在循环中通过减法也可以构建除法。将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。
用10乘以6得到60
是7 <60吗？是...
...
我们做了八次减法，所以下一位是8 ...
... 等等



  您知道为此目的使用更快的算法吗？


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

首先，我希望很明显，如果您尝试计算X / D，则可以先计算1 / D，然后将其乘以X。此外，让我们假设WOLOG D严格在0到1之间。

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

好的，所以我们的问题是，我们有一个介于零和一之间的数字D，我们希望计算1 / D。也许最简单的事情就是做一个例子。假设我们正在尝试计算1 / 0.7。正确答案是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到1之间。

当我们将D乘以（2-D）时，就是将（1-E）乘以（1 + E），得出1-E2。

由于0
继续这样做，直到获得所需的准确性为止。由于您将每一步的准确数字大致加倍，因此您应该能够很快达到可接受的准确度。因为我们已经开始安排D大于或等于0.1，所以E永远不会大于0.9；反复平方0.9会很快使您降至很小的数目。