仅使用加法和乘法来实现除法

Question

我正在用C#编写一个BigDecimal类.我已经成功实现了+, - 和*运算符.但我无法想出一种计算2 BigDecimals除法的方法.使用这3个运营商实施部门的最快捷方式是什么？或者有更好的方法吗？(考虑开发时间和算法速度)

目标1:我希望结果是具有固定精度的另一个BigDecimal(应该是可更改的)

目标2:正如您所提到的,BigDecimal的目的不是固定的精度.那么我怎样才能实现无限精度呢？

另一个问题:使用Microsoft BCL的BigRational类进行任意精度算术然后在此线程中使用Christopher Currens的扩展方法更好(关于速度和灵活性):C#中是否有BigFloat类？得到十进制表示而不是写一个新类？

Answer 1

首先,我认为通过"大小数"表示你代表的是理性,其中分母被限制为10的任何幂.

你会想要想要你想要两位小数除法的输出.小数通过加法,减法和乘法关闭,但不会在除法之外结束.也就是说,任何两个小数乘在一起产生第三:(7/10)*(9/100)给你一千分之六十三,这是另一个小数.但除以这两位小数,你得到一个在分母中没有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次减法,所以接下来的数字是8 ...
• ... 等等

你知道为此目的更快的算法吗？

当然,有很多更快的分割算法.这是一个:Goldschmidt的算法.

首先,我希望很明显,如果你正在尝试计算,X / D那么你可以先计算1 / D然后乘以X.而且,让我们假设WOLOG严格地介于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.可能最简单的方法就是做一个例子.假设我们正在尝试计算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-E ².

由于0 <E <1,清楚地ë ²比E和也介于0和1的情况下,这意味着,1 -电子²是越接近1.其实,这是一个很大接近于1.通过多次我们得到接近1很快重复此过程.实际上,我们在这里所做的就是将每一步的正确数字加倍.显然,这比减法方法好很多,减法方法在每一步给出一个额外的数字.

继续这样做,直到你有你想要的准确性.由于每个步骤的准确位数大致加倍,因此您应该能够很快达到可接受的准确度.由于我们已经安排D大于或等于0.1开始,因此E绝不大于0.9; 反复平方0.9可以很快地将你降到很小的数字.