algorithm - 从 10^x 到 2^x 的大整数基数/基数转换

Question

前言

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

信息

我正在从 stdin 中以 10 为基数读取 1000 个或更多数字，我希望将它们转换为以 2^x 为基数，以便我可以轻松地将它们存储在标准 C++ 数据类型之一的数组或向量中，可能是 unsigned int。对于如何进行基数转换，我只有一个想法，即重复除法余数法。下面是一些描述该方法的 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]

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

Answer 1

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