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

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

1 голос
/ 14 октября 2011

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

Я нахожусь в 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 просто typedef'ed к 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 5000 : 

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

Хотя это имеет простое представление для оснований 2 или 16, десятичную форму вычислить немного сложнее.

Итак, как именно библиотеки, подобные GMP, справляются с этим?Похоже, взятие по модулю и деления могут быть дорогими для таких больших чисел.Есть ли более быстрый алгоритм, или я ошибаюсь, и стандартный процесс прост для компьютеров?

1 Ответ

3 голосов
/ 14 октября 2011

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

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

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

...