首页 文章

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

提问于
浏览 次
6

前言

我正在通过编写和改进我自己的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 library 是怎么回事 . gmp/mpn/generic/set_str.c是"the magic"发生的相关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]

显然，第三种解决方案对于内部表示来说是最优化的，而且正是我想要达到的目标 .

algorithm math gmp bigint

3 回答

  • 0

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

    回复于
  • 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，所以这就是你如何转换基数 . 这不是最有效的方式，但它比分区快得多 .

    回复于
  • 6

    在FryGuy的帖子中没有提到的一点是，在该方法中，算术必须在您转换的基础上执行 to ，而用作乘数的基数与原始数字的基数相同;您不再需要的基础或您要转换的基础 from .

    整数上的基数转换有两个公式 . （1）使用基数B，我们正在转换 to （目标基数），作为重复除数，加上在基数b中完成的算术，其中b是基数转换 from . 另一方面，（2）使用基数b作为我们正在转换的数字的乘数，它恰好位于相同的基数b中，并且在基数B中进行算术运算 .

    （1）公式使用B作为参数并在基数b中进行算术运算

    （2）公式使用b作为参数并在基数B中进行算术运算

    这是knuth，第2卷，4.4基数转换

    回复于

相关问题