为什么更高的进制对此很有帮助?
我还有另一个问题,就是我应该如何将字符串转换为更高的进制(>16)。我读到除了base64之外,没有标准的方法。最后一个问题是,我如何使用这些更高的进制。一些示例会很好。
在寄存器中进行乘法或加法运算所花费的CPU周期往往是相同的。因此,通过使用整个寄存器,您将获得最少的迭代次数和最佳性能。也就是说,在32位架构上,将基本单位设置为32位,在64位架构上,将其设置为64位。否则,例如,如果您只填充了32位寄存器的8位,则会浪费周期。
第一个答案已经阐述得很好。我个人使用基数为2^16,以免在乘法中溢出。这样可以使任何两个数字相乘时只需乘一次,就不会溢出。
转换为更高的进制需要快速的除法方法,以及尽可能多地打包数字(假定您的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
所有方法都应该使用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