Печать больших чисел в десятичной форме

Question

Хотя представления числа являются относительным аспектом, мы обычно используем десятичную форму при печати во внешний мир.

Я нахожусь в Mac OS X, и, анализируя источник libc, я обнаружил, что знаменитый printf функция заканчивается вызовом маленькой функции __ultoa - после прохождения vfprintf_l1104 линии __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

Стандартный процесс не прост, но так или иначе вам нужно выполнить эквивалентные операции для получения десятичных цифр, и это может включать в себя высокоточную арифметику, даже если исходное значение в двоичном коде составляет всего несколько бит или один бит. Смотри мой вопрос:

Как вы печатаете точное значение числа с плавающей запятой?

Речь идет о числах с плавающей точкой, но все большие числа с плавающей точкой в ​​любом случае являются целыми числами, и очень большие и очень маленькие случаи являются единственными интересными случаями.