任意精度分数算术中的浮点数与有理数(C / C ++)

由于实现AP分数的方法有两种,一种是模拟double数据类型的存储和行为,只有更多的字节,另一种是使用现有的整数APA实现来表示分数作为理性即作为一对整数,分子和分母,这两种方式中的哪一种更有可能在性能方面提供有效的算术? (内存使用率确实很小。)

我知道现有的C / C ++库,其中一些提供带有“浮点数”的小数APA,另一些提供有理数的(不过它们都没有定点APA,但是当然我可以对依赖于“的库进行基准测试”浮动“对使用合理实现的实现进行实现,但结果很大程度上取决于我必须从近十个可用库中随机选择的那些特定库的实现细节。 因此,我感兴趣的两种方法的理论优缺点(或者如果考虑定点APA则为三种)。

问题是你在标题中提到的任意精度是什么意思。 它是否意味着“任意,但在编译时预先确定并在运行时修复”? 或者它是否意味着“无限,即在运行时可扩展以表示任何有理数”?

在前一种情况下(精确定制在编译时,但后来修复)我会说最有效的解决方案之一实际上是定点算术(即你提到的两个都没有)。

首先,定点运算不需要任何专用库来进行基本算术运算。 它只是一个覆盖整数运算的概念。 这意味着如果你真的需要点之后的大量数字,你可以使用任何大整数库,将所有数据乘以2 ^ 64,你基本上可以立即获得64位二进制数字的定点运算。 dot(至少与算术运算一样长,对乘法和除法进行一些额外的调整)。 这通常比浮点或合理表示更有效。

还要注意,在许多实际应用中,乘法运算通常伴随着彼此“补偿”的除法运算(如x = y * a / b ),这意味着通常不需要对这种乘法和除法进行任何调整。 这也有助于定点运算的效率。

其次,定点算术在整个范围内提供统一的精度。 对于浮点或合理表示,情况并非如此,在某些应用程序中,后两种方法可能是一个重大缺陷(或者是一种好处,取决于您的需要)。

那么,再次,你为什么只考虑浮点和理性表示。 有什么东西阻止你考虑定点表示吗?

由于没有其他人似乎提到这一点,理性和花车代表不同的数字集。 值1/3可以用理性精确表示,但不能用浮点数表示。 即使是任意精度浮点也会占用无限多个尾数位来表示重复的十进制数,如1/3 。 这是因为浮点实际上有点像理性,但分母被约束为2的幂。任意精度有理可以表示任意精度浮点数可以和更多的所有内容,因为分母可以是任何整数而不是幂2.(也就是说,除非我非常误解了如何实现任意精度浮点数。)

这是对你提出的理论利弊的回应。

我知道你没有询问内存使用情况,但这是一个理论上的比较,以防其他人感兴趣。 如上所述,Rationals专注于可以简单地用分数表示法表示的数字,如1/3492113/203233 ,并且浮点数专用于数字,这些数字很容易用2的幂表示科学记数法,如5*2^4591537*2^203233 。 表示各自人类可读forms的数字所需的ascii类型的数量与它们的存储器使用成比例。

如果我有任何错误,请在评论中纠正我。

无论哪种方式,您都需要乘以任意大小的整数。 这将是您性能的主导因素,因为它的复杂性比O(n*log(n)) 。 像对齐操作数,加上或减去大整数这样的东西是O(n) ,所以我们会忽略它们。

对于简单的加法和减法,您不需要浮点数乘法*和有理数的3次乘法。 花车赢了手。

对于乘法,对于有理数,需要一个浮点乘法和两个乘法。 浮子有优势。

分区有点复杂,理性可能在这里胜出,但这绝不是确定的。 我说这是平局。

总的来说,恕我直言,事实上,对于有理数的加法至少为O(n*log(n)) O(n)而浮点数的O(n)明显地给出了浮点表示的胜利。

*如果指数基数和数字基数不同,则可能需要一次乘法才能执行加法。 否则,如果使用2的幂作为基础,那么对齐操作数需要稍微移位。 如果不使用2的幂,那么您可能还需要乘以一个数字,这也是一个O(n)操作。

你实际上是在问这个问题:“我需要和我选择的动物一起参加比赛。我应该选择一只乌龟还是一只蜗牛?”

第一个提议“模拟双重”听起来像交错的精度:使用一个双精度数组,其中和是定义的数字。 Douglas M. Priest的一篇论文“任意精度浮点运算算法”描述了如何实现这种算法。 我实现了这个并且我的经验非常糟糕:进行此运行所需的开销会使性能下降100-1000倍! 使用小数的另一种方法也有严重的缺点:你需要实现gcd和kgv,不幸的是,你的分子或分母中的每个素数都有很好的机会炸毁你的数字并杀死你的表现。

因此,根据我的经验,他们是表现最差的选择。

我建议使用MPFR库,它是C和C ++中最快的AP包之一。

有理数不能给出任意精度,而是确切的答案。 然而,它们在存储方面更昂贵,并且它们的某些操作变得昂贵并且根本不允许某些操作,例如取平直根,因为它们不一定产生合理的答案。

就个人而言,我认为在你的情况下,AP浮动更合适。