c - 以十进制形式打印大数字

Question

虽然数字的表示在某种程度上是相对的，但我们对外打印一般使用小数形式。

我在 Mac OS X 中，在分析 libc 的源代码时，我发现著名的 printf 函数最终调用了一个小函数 __ultoa — 之后通过 vfprintf_l，1104 行 __vfprintf，最后是 __ultoa。它的定义如下(在本例中，所有这些都直接来自 FreeBSD):

/*
 * Convert an unsigned long to ASCII for printf purposes, returning
 * a pointer to the first character of the string representation.
 * Octal numbers can be forced to have a leading zero; hex numbers
 * use the given digits.
 */
static CHAR *
__ultoa(u_long val, CHAR *endp, int base, int octzero, const char *xdigs)
{
    CHAR *cp = endp;
    long sval;

    /*
     * Handle the three cases separately, in the hope of getting
     * better/faster code.
     */
    switch (base) {
    case 10:
        if (val < 10) {     /* many numbers are 1 digit */
            *--cp = to_char(val);
            return (cp);
        }
        /*
         * On many machines, unsigned arithmetic is harder than
         * signed arithmetic, so we do at most one unsigned mod and
         * divide; this is sufficient to reduce the range of
         * the incoming value to where signed arithmetic works.
         */
        if (val > LONG_MAX) {
            *--cp = to_char(val % 10);
            sval = val / 10;
        } else
            sval = val;
        do {
            *--cp = to_char(sval % 10);
            sval /= 10;
        } while (sval != 0);
        break;

    case 8:
        do {
            *--cp = to_char(val & 7);
            val >>= 3;
        } while (val);
        if (octzero && *cp != '0')
            *--cp = '0';
        break;

    case 16:
        do {
            *--cp = xdigs[val & 15];
            val >>= 4;
        } while (val);
        break;

    default:                /* oops */
        LIBC_ABORT("__ultoa: invalid base=%d", base);
    }
    return (cp);
}

此处 CHAR 只是类型定义为 char(出于某种原因)而 to_char 确实基本上是你所期望的:

#define to_char(n)  ((n) + '0')

十进制形式的转换以一种直接的方式发生，除以10 并取 %10:

do {
    *--cp = to_char(sval % 10);
    sval /= 10;
} while (sval != 0);

然而，虽然这对小数字(最多 8 个字节)有效，但似乎太多了对我来说是“体力劳动”。在 GMP 中，您可以轻松计算出 2⁵⁰⁰⁰:

mpz_t n;
mpz_init(n);
mpz_ui_pow_ui(n, 2ul, 5000ul);
gmp_printf("%Zd\n", n);

虽然这对于基数 2 或 16 有一个简单的表示，但十进制形式是有点难计算。

那么，像 GMP 这样的库究竟是如何处理这些的呢？看起来像取模和对于如此大的数字，除法可能会很昂贵。有没有更快的算法，还是我错了，标准过程对计算机来说很容易？

Answer 1

标准的过程并不容易，但是无论如何都需要做等价运算才能得到十进制的数字，即使二进制的原始值只有几位或一位，这也涉及到高精度的运算一位。看我的问题:

How do you print the EXACT value of a floating point number?

这是关于 float 的，但是所有大的 float 无论如何都是整数，非常大和非常小的情况是唯一有趣的情况。