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

Question

前言

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

信息

我正在从基数10中的stdin读取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

unsigned chars的范围是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乘法和添加函数).