首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >对于任何特定语言都有效的任意精度算术,是否有通用的实现策略?

问对于任何特定语言都有效的任意精度算术,是否有通用的实现策略?
EN

Stack Overflow用户
提问于 2011-10-24 23:59:09
回答 1查看 1.6K关注 0票数 16

我正在考虑实现任意精度算术的不同方法(有时称为Bignum、Integer或BigInt)。

似乎常见的习惯用法是使用数组来存储实际值,并在空间需求增加或缩小时根据需要重新分配它。

更准确地说,似乎数组元素的位大小通常是通常支持的第二大大小(可能是为了使溢出计算更容易实现?),例如,语言/平台支持128位大小的数字-> 64位数组+128位变量来处理溢出。

有没有根本不同的方法来实现任意精度的算术运算,或者上面的方法是不会造成巨大性能损失的“可靠的”实现方式?

我的问题是关于底层的数据结构,而不是操作的算法。我认识Karatsuba,Toom-Cook等人。

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2011-10-25 01:18:59

可以以一种与通常的base-2^n系统完全不同的方式使用Chinese Remainder Theorem to represent large integers。

我相信基于CRT的表示仍然会使用元素数组,就像传统的表示一样,它是基于最方便的本机算法的。然而,当除以一系列质数,而不是基数为2^n的数字时,这些元素保存着该数字的余数。

与传统表示一样,所使用的元素的数量决定了可表示数量的最大大小。不幸的是,很难计算一个基于CRT的数字是否大于另一个,因此很难判断您的表示是否溢出了最大尺寸。请注意,加法和乘法在CRT表示中速度非常快,如果您能够处理溢出问题,这可能是一个优势。

但是,为了回答您的问题:我认为可以准确地说,基数为2^n的系统确实是大多数流行的bignum库使用的“经过验证的”表示法。我想我记得有现存的基于CRT的bignum库,尽管我最近没有检查过它们是否还存在……

票数 10
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/7878465

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档