6

前言

我正在通过编写和改进我自己的 BigInt 库来学习计算机数学。到目前为止，我的第一个版本将基数为 10 的数字的每个数字存储在向量的连续元素中。它可以以任意精度进行乘法和加法。我想通过转换为基数 2^x 来使用标准 C++ 数据类型中的所有可用空间来加速它。

信息

我正在从以 10 为底的标准输入读取 1000 个或更多数字，我希望将它们转换为以 2^x 为底的数字，因此我可以轻松地将它们存储在标准 C++ 数据类型之一的数组或向量中，可能是无符号整数。我对如何进行基本转换只有一个想法，即用余数重复除法。下面是一些描述该方法的 C++ 代码：

vector<int> digits;
while(num!=0) {
   int mod = num%base;
   num = num/base;
   digits.push_back(mod);
}

难题

我迷失的一些事情是除以余数是否是对大整数进行基数转换的正确方法。我试过看看GMP 库是如何做到的。gmp/mpn/generic/set_str.c是“魔术”发生的相关c源文件，但我不确定那里发生了什么。Matt McCutchen 的BigInt似乎使用了带余数的重复除法。如果我确实使用这种方法，我基本上需要编写我的 BigInt 类的两个版本，一个用于在 Base10 中工作，另一个用于 Base2^x。

结论

  • 提供有关将大量数字从字符串转换为 32 位字数组的正确步骤的建议。
  • 帮助我了解 GMP 如何将字符串转换为 32 位字数组，而无需涉足许多抽象层。

使用 4 位字长的示例

我们要存储的号码（显然在小号上）：123456789

无符号字符的范围为 0-255，如果我们想拆分我们的数字并将其存储在向量中，我们可以通过以下三种方式之一进行：

  • 作为基数 10，我们的向量看起来像：[1,2,3,4,5,6,7,8,9]
    • 这就是我的向量在我的第一个实现中的样子。
  • 作为基数 100，我们的向量看起来像：[1,23,45,67,89]
    • 易于从基数 10 转换为基数 100，具有 ciel（base10/2 中的数字）元素。
  • 作为基数 256，我们的向量看起来像：[7,91,205,21]

显然，第三种解决方案是内部表示的最佳解决方案，也是我想要达到的。

4

3 回答 3

6

一旦您拥有适用于 bigint 库的乘法和加法函数，将字符串转换为 bigint 本身就很简单。从零转换结果开始。对于您处理的每个数字（从左到右），将前一个结果乘以 10 并添加新数字的值（使用您的 bigint multiply 和 add 函数）。

于 2011-06-06T22:47:35.153 回答
1

一般来说，要将一个基数转换为另一个基数（从最高有效位到最低位），算法如下：

output = 0
foreach digit in digits:
    output = output * base + digit

以相反的顺序，如下所示：

output = 0
multiplier = 1
foreach digit in digits:
    output = output + multiplier * digit
    multiplier = multiplier * base

您可以使用此数学递归地使用您的 bigint 库来确定如何存储数字。我的意思是你需要实现 BigInt*BigInt 和 BigInt+BigInt，所以这就是转换基数的方法。这不是最有效的方法，但它比除法快得多。

于 2011-06-06T22:51:37.550 回答
0

FryGuy 的帖子中没有提到的一件事是，在该方法中，必须在要转换为的基数中执行算术运算，而用作乘数的基数与原始数字的基数相同；您不再需要的基础或您要转换的基础。

整数的基数转换有两个公式。(1) 使用我们要转换为（目标基数）的基数 B 作为重复除数，加上在基数 b 中完成的算术运算，其中 b 是从 转换的基数。(2) 另一方面，使用基数 b 作为我们要转换的数字的乘数，这些数字恰好在同一个基数 b 中，并在基数 B 中进行算术运算。

(1) 公式以B为参数，以b为底进行算术运算

(2) 公式以b为参数，以B为底进行算术运算

这是 knuth, vol 2, 4.4 基数转换

于 2012-08-16T21:22:13.180 回答