为什么在实现 BigInt 时要使用更高的进制?

4
我正在尝试实现BigInt,并阅读了一些与此相关的线程和文章,大多数建议使用更高的进制(256或232甚至264)。
为什么更高的进制对此很有帮助?
我还有另一个问题,就是我应该如何将字符串转换为更高的进制(>16)。我读到除了base64之外,没有标准的方法。最后一个问题是,我如何使用这些更高的进制。一些示例会很好。

2
你的两个问题没有任何关联,最好分别在不同的线程中提出。此外,你的第二个问题没有意义。BASE64不是一种进制。 - Mr Lister
@MrLister:BASE64编码可能不是一个基数,但它使用一种基于64的字母表,并且可以用于真正的“b=64”数字。 - user7116
2个回答

10

在寄存器中进行乘法或加法运算所花费的CPU周期往往是相同的。因此,通过使用整个寄存器,您将获得最少的迭代次数和最佳性能。也就是说,在32位架构上,将基本单位设置为32位,在64位架构上,将其设置为64位。否则,例如,如果您只填充了32位寄存器的8位,则会浪费周期。


你的意思是使用一个字(32位或64位)作为基础? - questions
是的,使用本地寄存器大小将是最有效的。假设您的本地寄存器为64位;每个64位操作将花费恒定时间。使一些位变为零(如果您仅使用低8位,则顶部36位为零)不会改变该恒定时间,但现在您需要发出八倍更多的指令。 - Useless
дҪ еҸҜиғҪжғідҪҝз”Ё2^30жҲ–2^31дҪңдёәеҹәж•°пјҢиҖҢдёҚжҳҜ2^32пјҢд»ҘдҫҝеңЁдёҚдҪҝз”ЁжұҮзј–иҜӯиЁҖзҡ„жғ…еҶөдёӢе®һзҺ°вҖңиҝӣдҪҚвҖқгҖӮ - dan04
1
通常最好使用比字长一半的位数(如果支持乘法),这样可以确保每个操作都可以在内部执行而无需事先检查潜在的溢出,并在操作完成后规范化表示。 - David Rodríguez - dribeas
1
@DavidRodríguez:我倾向于始终使用32位。这是因为你可以确保存在一个64位数据类型来存储结果,在理智的架构中,32x32的乘法结果通常会得到64位的值。类似地,在64位机器上进行64x64的乘法通常会产生128位的结果,但由于大多数C实现没有128位类型来表示它,因此没有便携式的方法来获取上位比特。 - R.. GitHub STOP HELPING ICE
显示剩余2条评论

2
  1. 第一个答案已经阐述得很好。我个人使用基数为2^16,以免在乘法中溢出。这样可以使任何两个数字相乘时只需乘一次,就不会溢出。

  2. 转换为更高的进制需要快速的除法方法,以及尽可能多地打包数字(假定您的BigInt库能够处理多种进制)。

考虑10进制 -> 2进制。实际转换应该是 10 -> 10000 -> 32768 -> 2。这可能看起来比较慢,但从10进制到10000进制的转换非常快速。在10000和32768之间进行转换的迭代次数非常快,因为要迭代的数字非常少。将32768拆分为2也非常快。

因此,首先将基数打包到它可以达到的最大基数。要做到这一点,只需将数字组合在一起。该基数应小于等于2^16,以防溢出。

接下来,将数字组合在一起,直到它们大于或等于目标基数。从这里开始,使用快速除法算法除以目标基数,否则通常会溢出。

一些快速代码:

if (!packed) pack()

from = remake() //moves all of the digits on the current BigInt to a new one, O(1)
loop
    addNode()

    loop
        remainder = 0
        remainder = remainder*fromBase + from.digit
        enter code here`exitwhen remainder >= toBase
        set from = from.prev
        exitwhen from.head

    if (from.head) node.digit = remainder
    else node.digit = from.fastdiv(fromBase, toBase, remainder)

    exitwhen from.head

快速除法的介绍
loop
    digit = remainder/divide
    remainder = remainder%divide

    //gather digits to divide again
    loop
        this = prev
        if (head) return remainder

        remainder = remainder*base + digit
        exitwhen remainder >= divide

        digit = 0

return remainder

最后,如果需要解包,请进行解包操作。

打包只是将数字组合在一起。

以十进制转换为万进制为例:

4th*10 + 3rd
*10 + 2nd
*10 + 1st
  1. 你应该有一个基类,用于存储toString方法所需的字母表和大小信息。如果基类无效,则只需以逗号分隔的列表形式显示数字。

所有方法都应该使用BigInt的当前基数,而不是某个常量。

就这样了吗?

从那里开始,您将能够执行诸如以下操作:

BigInt i = BigInt.convertString("1234567", Base["0123456789"])

在这里,[]被重载了,它会创建一个新的基础或返回已经创建的基础。

你还可以做一些类似的事情:

i.toString()
i.base = Base["0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"]
i.base = 256
i.base = 45000

等等,如果你正在使用整数并且想要返回BigInt余数,那么除法可能会有点棘手 =P,但这仍然相当容易 ^_^。

这是我在vjass中编写的BigInt库(是的,为了魔兽争霸3,哈哈,请不要评判我)

TriggerEvaluate(evalBase)这样的东西只是为了防止线程崩溃(恶意操作限制)。

祝你好运:D


2^16太保守了。几乎所有32位编译器都有64位类型,因此使用32位limb不会很麻烦。在64位编译器中也有128位类型。 - phuclv

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接