最著名的任意精确算法实现方法是什么？

Question

我将为.NET编写一个类库，它为整数、有理数和可能是复数提供了任意精确算法的实现。我应该熟悉哪些最广为人知的方法？

我试着从Knuth的TAOCP第2卷(塞米诺迪算法，第4章-算术)开始，但它太复杂了。至少我不能在相对较短的时间内得到这些想法。

Answer 1

如果您使用的是C# 4.0或更高版本，那么您已经有了一个BigInteger类。从这里开始，创建自己的Rational类将节省大量时间。

如果你想自己构建所有的东西，那么你必须实现一些复杂的算法，尤其是乘法算法。您可以从具有时间复杂度O(n²)的朴素乘法算法开始。许多其他算法都依赖于乘法(除法、模幂、gcd、平方根等)。如果你让所有的东西都正常工作，并且有一组可靠的单元测试，那么你可以用简单的乘法算法来代替像3路Toom-Cook乘法或者更高级的算法。

Answer 2

关于为什么存在BigInteger而不是BigReal等问题:这与浮点表示的任意性质有关。64位浮点的IEEE标准为指数(“特性”)和“整体”数字部分(“尾数”)预留了一些位。虽然有一个扩展精度浮点的标准，但它似乎是通用的：http://en.wikipedia.org/wiki/IEEE_754-2008#_和_可扩展_精密度_格式。

因此，扩展浮点需要任意决定使数字的各个部分的大小，而整数的扩展则是很简单的:根据需要继续添加高阶数字。因此，研究理性主义(一种扩展精度整数的比率)而不是浮点是有意义的。看看这里-- http://www.jsoftware.com/jwiki/Essays/Extended%20Precision%20Functions --关于这方面的一些高层考虑。