3

我正在尝试实现 BigInt 并阅读了一些关于它的线程和文章，其中大多数建议使用更高的基数（256 或 2 32甚至 2 64）。

为什么更高的碱基有利于这个目的？

我的另一个问题是我应该如何将字符串转换为更高的基数（> 16）。我读到没有标准的方法，除了base64。最后一个问题，我如何使用那些更高的碱基。一些例子会很棒。

4

2 回答 2

9

乘以或添加适合寄存器的数字所花费的 CPU 周期往往是相同的。因此，通过用完整个寄存器，您将获得最少的迭代次数和最佳性能。也就是说，在 32 位架构上，将基本单元设为 32 位，在 64 位架构上，将其设为 64 位。否则——比如说，如果你只填满 32 位寄存器的 8 位——你就是在浪费周期。

于 2012-04-16T16:36:27.673 回答
2

  1. 第一个答案最好地说明了这一点。我个人使用基数 2^16 来防止乘法溢出。这允许任何两个数字相乘一次而不会溢出。

  2. 转换为更高的基数需要快速除法方法以及尽可能多地打包数字（假设您的 BigInt lib 可以处理多个基数）。

考虑基数 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

最后，如果您应该解包，请解包

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

以 10 到 10000 为底的示例

4th*10 + 3rd
*10 + 2nd
*10 + 1st
  1. ？？？

您应该有一个存储 toString 的字母 + 大小的基类。如果 Base 无效，则只需在逗号分隔列表中显示数字。

您的所有方法都应该使用 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

于 2012-04-16T19:32:17.620 回答