我正在考虑实现任意精度算术的不同方法(有时称为Bignum、Integer或BigInt)。
似乎常见的习惯用法是使用数组来存储实际值,并在空间需求增加或缩小时根据需要重新分配它。
更准确地说,似乎数组元素的位大小通常是通常支持的第二大大小(可能是为了使溢出计算更容易实现?),例如,语言/平台支持128位大小的数字-> 64位数组+128位变量来处理溢出。
有没有根本不同的方法来实现任意精度的算术运算,或者上面的方法是不会造成巨大性能损失的“可靠的”实现方式?
我的问题是关于底层的数据结构,而不是操作的算法。我认识Karatsuba,Toom-Cook等人。
发布于 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库,尽管我最近没有检查过它们是否还存在……
https://stackoverflow.com/questions/7878465
复制相似问题