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

发布于 2024-11-13 23:21:44 字数 1433 浏览 4 评论 0原文

前言

我正在通过编写和完善我自己的 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（以 10/2 为基数的数字）元素。
以 256 为基数，我们的向量如下所示： [7,91,205,21]

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

原文

Preface

I'm learning about computer math by writing and refining my own BigInt library. So far my first incarnation stores every digit of a base 10 number in successive elements of a vector. It can multiply and add with arbitrary precision. I want to speed it up by using all of the space available to me in a standard C++ data type by converting to base 2^x.

Information

I am reading 1000 or more digits from stdin in base 10 and I wish to convert them to base 2^x so I may store them easily in an array or vector of one of the standard C++ data types, likely unsigned int. I have only one idea for how to do base conversion, the repeated division with remainder method. Here is some C++ code describing that method:

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

Conundrums

Some things I'm lost on are whether or not division with remainder is the proper way to do radix conversion on large integers. I've tried looking at how the GMP library does it. gmp/mpn/generic/set_str.c is the relevant c source file where "the magic" happens, but I am not certain what is going on in there. Matt McCutchen's BigInt appears to use the repeated division with remainder method. If I do use this method, I essentially need write two versions of my BigInt class, one for working in Base10 and the other for Base2^x.

Conclusion

Offer advice on the proper steps for converting a huge number from a string to an array of 32 bit words.
Help me learn how GMP converts a string to an array of 32bit words without wading through many layers of abstraction.

Examples Using 4 bit word size

Number we want to store (obviously on the small size): 123456789

unsigned chars have a range of 0-255, if we want to split up our number and store it in the vector we can do it one of three ways:

As base 10, our vector looks like: [1,2,3,4,5,6,7,8,9]
- This is what my vector looked like in my first implementation.
As base 100, our vector looks like: [1,23,45,67,89]
- Easy to convert from base 10 to base 100, has ciel(digits in base10/2) elements.
As base 256, our vector looks like: [7,91,205,21]

Obviously the third solution is the most optimal for internal representation, and is what I am trying to get to.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

寒尘 2024-11-20 23:21:44

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

回复收藏 0 原文

蓝戈者 2024-11-20 23:21:44

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

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，因此这就是转换基数的方法。这不是最有效的方法，但它比除法快得多。

In general, to convert one base to another (from most significant digit to least), the algorithm is as follows:

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

In the reverse order, it's the following:

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

You can use your bigint library recursively using this math to figure out how to store the numbers. By that, I mean you need to implement BigInt*BigInt and BigInt+BigInt, so this is how you can convert bases. It's not the most efficient way, but it is a lot faster than division.

回复收藏 0 原文