将大整数转换为十进制字符串

Question

冒险让这个问题被投票为重复，甚至可能被关闭，我仍然想问一下这个问题。

背景

在“普通”的数据类型中，比如int、long long等，要将二进制数值转换为十进制字符串，您可以按照以下伪代码操作：

Set length = 0
Set divisor to largest base10 value the data type will hold (Divisor).
  Loop
    Divide number in question by divisor.
    Place result in a string at position length.
    Increment the length by 1.
    Divide the divisor by 10.
Reverse the string.
Print the string.

实际上，（大多数）任何语言中的实现都非常简单。

问题

我遇到的问题是，在大整数（也称为任意精度算术）中，没有最大的十进制值可供使用。因此，问题是：“如果没有办法知道该值，如何将除数初始化为最大可能的基数10值？”

我尝试过的方法

仍在尝试起草解决方案。

研究

我找到的一些链接包括以下内容：

将“大”十六进制数字（字符串格式）转换为十进制数字（字符串格式），而不使用BigInteger类

{{link2：C：以十进制打印BigInteger}}

将BigInteger转换为十进制（Base 10）字符串的最快方法是什么？

将“大”十六进制数（字符串格式）转换为十进制数（字符串格式）而不使用BigInteger类的方法

谷歌搜索结果显示其他内容，但没有直接回答我的问题。

想法

我认为可能可行的一种方法如下（伪代码）：

Define p_divisor as previous divisor.
Set divisor = 1
  Loop:
    if divisor < dividend
      then
        Set p_divisor = divisor
        divisor = divisor * 10
      else
        end loop
  Loop:
    Divide number in question by divisor.
    Place result in a string at position length.
    Increment the length by 1.
    Divide the divisor by 10.
    if divisor == 1 then end loop
Reverse the string.
Print the string.

这样做是否正确？我已经有一个大整数库（包括乘法和除法）正在运作，所以很容易完成。我看到这种方法的主要问题是性能，因为您必须运行乘法序列以获取初始除数，然后对每个十进制位进行两次除法。一次是实际的除法，另一次是除数。

- Daniel Rudy

---

我会反复地将数字除以10，从右边生成数字。最后，将字符串翻转。 - melpomene

不要每次都除以10、100、1000等，而是每次只除以10，将余数作为下一个数字，并继续执行直到被除数为0（最后可以反转字符串或者一开始就以相反的顺序构建字符串——如果你能够确定数字中实际使用了多少比特，你可以相当准确地估计需要多少十进制位数）。 - Dmitri

我认为你的意思是先除以1000，然后是100，最后是10。我想我知道你的意图了。余数就是要放入字符串中的数字，而商则是新的被除数。这实际上是个好主意。因为除数是10，高速单字除法算法可以轻松地完成这个任务。此外，由于我是从字符串的开头填充的，所以我不认为需要反转字符串。这应该是一个答案，而不是一条评论。谢谢。 - Daniel Rudy

第二种方法在C语言中不起作用。因为如果除数小于被除数，则设置p_divisor = divisor，然后将divisor乘以10会导致无论使用什么整数类型都会溢出。 - chux - Reinstate Monica

Answer 1

一种（比较普遍的）实现方法，无论是对于大整数还是普通整数类型，都是反复将数字除以10，将余数作为下一位（从最低有效位开始）保存。继续操作直到数字变为0。由于第一个发现的数字是最低有效位，因此您可能需要在结尾处翻转字符串，或者在操作过程中以相反顺序构建字符串。

使用普通的unsigned int的示例可能如下所示：

void printUInt(unsigned x) {
  char buf[(sizeof(x) * CHAR_BIT) / 3 + 2]; // slightly oversize buffer
  char *result  = buf + sizeof(buf) - 1; // index of next output digit

  // add digits to result, starting at 
  //   the end (least significant digit)

  *result = '\0'; // terminating null
  do {
    *--result = '0' + (x % 10);  // remainder gives the next digit
    x /= 10;
  } while (x); // keep going until x reaches zero

  puts(result);
}

对于大整数，过程基本相同 -- 但如果可以，在一步中进行除法并找出余数最好。

上面的示例是从缓冲区的末尾构建字符串（因此result最终指向缓冲区的中间位置），但您也可以从开头构建，之后再反转它。

如果您能确定原始数字使用的位数（约每3个位数增加1位额外数字 -- 稍微少一些），则可以估计所需输出的大小。

- Dmitri

---

这似乎是答案。在我标记它为答案之前，我会等待几天看是否有其他人回复。我正在编写代码。从我找到的资料来看，每16位的5个小数位似乎可以转换成比特，这似乎可行。我通过2^208检查了该转换，它仍然有效。我可能会编辑原始帖子以添加那个小细节。 - Daniel Rudy

小改动：可以使用sizeof buf而不是sizeof (buf)。 2）可以使用*28/93或*87/289来近似log10（2），而不是使用/3。因此，char buf[sizeof x * CHAR_BIT) *28/93 + 2]; // 右大小的缓冲区最多为92位。 - chux - Reinstate Monica

Answer 2

已经有一个被接受的答案为您提供了一种简单的方法来实现这个。它可以很好地工作并给出一个不错的结果。然而，如果您真的需要将大数值转换为字符串，有更好的方法。

我不会详细介绍，因为我的解决方案是用Delphi编写的，许多读者无法轻松阅读，并且它非常长（几个100行代码中的几个函数，使用其他函数等，不能在简单的答案中解释，特别是因为转换以不同的数字基数处理）。

但原理是通过一个10的幂次数将数字分成两个几乎相等大小的半部分。为了进行转换，再次递归地将它们切成两个较小的部分，通过一个更小的10的幂次数，直到部分的大小达到某种较低限制（例如32位），然后以接受的答案方式最终进行转换。

然后，这些部分转换被“连接”（实际上，数字直接放置在单个缓冲区的正确地址中），因此最后，您得到一个巨大的数字字符串。

这有点棘手，我只是提到那些想要研究极大数字的人。对于少于100位数字的数字来说，这没有意义。

这是一个递归方法，但不是简单地除以10。

可以通过像这样预先计算缓冲区的大小来实现：

bufSize = myBigInt.bitCount() * Math.log10(2) + some_extra_to_be_sure;

我使用预先计算的表格来处理不同的数字基数，但这只是一个实现细节。

对于非常大的数字，这种方法比反复除以10的循环要快得多，特别是因为那种方法需要一直将整个数字除以10，而且它变小得非常缓慢。分治算法只会将数字划分为越来越小的部分，所需的（昂贵）除法总数要少得多（我猜约为log N而不是N）。因此，在（平均）更小的数字上进行更少的除法。

参见Brent、Zimmermann的《现代计算机算术》，算法1.26。

如果您想看看它是如何工作的，可以在这里找到我的代码和解释：BigIntegers unit。

- Rudy Velthuis

---

logN 是您递归树的深度，分割次数仍为 O(N)，但在这种方法中常数可能会小得多。 - Slava

我知道对于非常大的数字来说，它会快得多，因为昂贵的除法（使用大数）的数量大大减少。朴素算法不断地将一个非常缓慢减小的数字除以10。因此，总的除法次数可能仍然是O(n)，但其中大部分除以的数字要小得多。 - Rudy Velthuis

Answer 3

我遇到了类似的问题，但没有找到任何我喜欢的解决方案，所以想出了自己的方法。这个想法是将您的 BigInt 使用任何基数转换为另一个具有幂次为 10 的 BigInt，尽可能大但仍小于当前基数。然后您可以使用系统调用按“数字”进行转换，并连接结果。因此，没有明确的除法涉及，只隐藏在系统库函数中。仍然总体复杂度是二次的（就像其他基于除法的解决方案一样）。

friend std::ostream& operator<<(std::ostream& out, const BigInt_impl& x){
    using Big10 = BigInt_impl<char32_t, uint64_t, 1000000000>; // 1e9 is the max power of 10 smaller then BASE
    auto big10 = Big10(0);
    auto cm = Big10(1);
    for(size_t i = 0; i < x.digits.size(); ++i, cm *= BASE){
        big10 += cm*x.digits[i];
    }
    out << big10.digits.back();
    for(auto it = next(big10.digits.rbegin()); it != big10.digits.rend(); ++it){ 
        out << std::setfill('0') << std::setw(9) << *it;
    }
    return out;
}

在这个解决方案中要注意魔术常量1e9 - 这只是我的情况BASE = 2^32 。懒得好好做了。

（还有抱歉，对于C ++，我刚意识到问题是关于C的，但仍然想留下代码，可能作为思路的说明）。

- Slava

Answer 4

这是正确的方法吗？在 C 中，第二种方法并不适用于所有整数值。如果除数小于被除数，则依赖于将除数创建为大于（或等于）被除数的10的幂。由于大多数整数系统具有有限范围，因此当被除数等于INTEGER_MAX时，创建大于（或等于）被除数的10的幂是不可能的（除非INTEGER_MAX是10的幂）。

---

递归方法通过反复除以10并推迟数字分配，直到确定更重要的数字为止。当目标缓冲区的大小未知但足够时，这种方法非常有效。

以下处理有符号的int，并且即使是INT_MIN也不会出现未定义行为。

// Return location of next char to write
// Note: value is expected to be <= 0
static char *itoa_helper(char *s, int value) {
  if (value/10) {
    s = itoa_helper(s, value/10);
  }
  *s = '0' - value % 10;  // C99
  return s+1;
}

void itoa(int n, char *s) {
  if (n < 0) {
    *s++ = '-';
  } else {
    n = -n;
  }
  *itoa_helper(s, n) = '\0';
}

#define INT_SIZEMAX  ((CHAR_BIT*sizeof(int) - 1)*28/93 + 3)
char buf[INT_SIZEMAX];
itoa(INT_MIN, buf);

与其将负数转换为正数，这段代码做相反的操作，因为在大多数系统上-INT_MIN会失败。

- chux - Reinstate Monica

---

我不喜欢递归方法。我已经实现了一个不使用递归的方法。 - Daniel Rudy

使用正确的工具来完成工作。在递归是最佳方法的情况下，对其有偏见会导致使用斧头代替锯子或不熟悉正确使用工具的情况发生。 - chux - Reinstate Monica

递归是否是这里的正确工具？我不这样认为。这可以用简单的循环完成。 - Rudy Velthuis

确定字符串长度非常容易。只需计算位数（这很容易），然后乘以log10(2)即可。再多分配几个数字，就更加安全了。这是我在Delphi中自己的BigInteger的简单版本中所使用的方法。不那么简单的方法使用分治算法，但缓冲区大小的计算方式相同。甚至对于数百万位的BigIntegers也是准确的。 - Rudy Velthuis

@Rudy Velthuis 将您的评论发布为答案将允许投票和反馈。这比作为递归方法的注释更有意义。 - chux - Reinstate Monica