Быстрое целочисленное преобразование в десятичное

Учитывая (беззнаковое) целое число, каков самый быстрый способ преобразовать его в строку, содержащую его десятичное представление?

Самый простой способ сделать это — многократно делить на 10, пока не дойдете до нуля. Мне не нравится такой подход, потому что он

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

Я подумал о следующем методе преобразования целых чисел в десятичную базу. Это хорошая идея? Как это делается в обычных реализациях таких функций, как printf ?

#include <stdint.h>

const static uint64_t i64_tab[20] = {
                     1u,
                    10u,
                   100u,
                  1000u,
                 10000u,
                100000u, /* 10^ 5 */
               1000000u,
              10000000u,
             100000000u,
            1000000000u,
           10000000000u, /* 10^10 */
          100000000000u,
         1000000000000u,
        10000000000000u,
       100000000000000u,
      1000000000000000u, /* 10^15 */
     10000000000000000u,
    100000000000000000u,
   1000000000000000000u,
  10000000000000000000u  /* 10^19 */
};

void uint64_to_string(char *out, uint64_t in) {
  int i;
  uint64_t tenpow;
  char accum;

  for (i = 19;i > 0;i--) {
    if (in >= i64_tab[i]) break;
  }

  do {
    tenpow = i64_tab[i];
    accum = '0';

    while (in >= tenpow) {
      in -= tenpow;
      accum++;
    }

    *out++ = accum;

  } while (i --> 0);

  *out = '\0';
}

const static uint32_t i32_tab[10] = {
           1u,
          10u,
         100u,
        1000u,
       10000u,
      100000u, /* 10^ 5 */
     1000000u,
    10000000u,
   100000000u,
  1000000000u, /* 10^9  */
};

void uint32_to_string(char *out, uint32_t in) {
  int i;
  uint32_t tenpow;
  char accum;

  for (i = 9;i > 0;i--)
    if (in >= i32_tab[i]) break;

  do {
    tenpow = i32_tab[i];
    accum = '0';

    while (in >= tenpow) {
      in -= tenpow;
      accum++;
    }

    *out++ = accum;

  } while (i --> 0);

  *out = '\0';
}

c performance data-conversion
person fuz    schedule 07.05.2012    source источник
comment
Учитывая (беззнаковое) целое число, каков самый быстрый способ преобразовать его в целое число? Вы имеете в виду, если вы начнете со строки? Потому что самый быстрый способ преобразовать целое число в целое — ничего не делать :)   -  person Justin    schedule 08.05.2012
comment
@FUZxxl извините, я всегда случайно попадаю в тег C.   -  person Seth Carnegie    schedule 08.05.2012
comment
@Сет Нет проблем. Мне просто не нравится Просто используйте X, мне все равно и я не знаю, кто это работает, хотя   -  person fuz    schedule 08.05.2012
comment
@FUZxxl, это зависит от того, что вы подразумеваете под «быстрым». Если вы действительно хотите что-то сделать, быстрее всего использовать встроенную функцию. Поэтому я подумал, что отвечу так (хотя это не C++, которого я не знал в то время). Никакого вреда не имелось в виду.   -  person Seth Carnegie    schedule 08.05.2012
comment
@Сет, я не сержусь на тебя. Извините, если мой комментарий был груб. Это может быть вызвано моим незнанием libc, но, похоже, я не нашел такой функции, кроме sprintf, которая несет большие накладные расходы, потому что сначала нужно интерпретировать строку формата. Забавно, что я нашел более 4 функций для достижения противоположного эффекта (от строки к целому). Кажется, людям не часто нужно записывать десятичные числа.   -  person fuz    schedule 08.05.2012
comment
Тесно связанный: версия того же вопроса на С++   -  person Ben Voigt    schedule 08.05.2012
comment
Я думаю, что это самый быстрый способ. 28 часов на моей коробке Hazwell i7, выполняющей тестовый цикл от LONG_MIN до LONG_MAX — если вы можете жить с подписанным выходом. Однако ядро ​​моего кода работает в беззнаковом пространстве, поэтому его легко изменить, если нет. stackoverflow.com/questions/21501815/   -  person    schedule 12.11.2014

Ответы (4)


arrow_upward
2
arrow_downward

Самый быстрый подход ко всем микроконтроллерам, кроме самых простых (например, 8-битных), - использовать деление, но уменьшить количество делений, генерируя несколько цифр одновременно.

Вы найдете очень оптимизированный код в ответах на мой вопрос здесь. Использование его в C должно быть тривиальным редактированием для устранения std::string - в фактическом преобразовании не используются функции C++. Ядро

while(val>=100)
{
   int pos = val % 100;
   val /= 100;
   *(short*)(c-1)=*(short*)(digit_pairs+2*pos); // or use memcpy
   c-=2;
}
while(val>0)
{
    *c--='0' + (val % 10);
    val /= 10;
}

Я также предоставил оптимизированный код без деления для 8-битных микро, аналогичный идее, показанной в коде в вопросе, но без циклов. Это заканчивается большим количеством кода, подобного этому:

    if (val >= 80) {
        ch |= '8';
        val -= 80;
    }
    else if (val >= 40) {
        ch |= '4';
        val -= 40;
    }
    if (val >= 20) {
        ch |= '2';
        val -= 20;
    }
    if (val >= 10) {
        ch |= '1';
        val -= 10;
    }
person Ben Voigt    schedule 07.05.2012
comment
Это интересно. Я собираюсь написать программу, чтобы сравнить этот подход с моим. - person fuz; 08.05.2012
comment
@FUZxxl: я предлагаю вам перейти к другому вопросу. Уже много кода с данными о производительности и эталонным кодом, необходимым для ваших собственных тестов. - person Ben Voigt; 08.05.2012

arrow_upward
2
arrow_downward

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

person usr    schedule 07.05.2012
comment
Умножение целых чисел по-прежнему выполняется довольно медленно, потому что это неконвейерная, микрокодированная операция, а это означает, что весь конвейер ООО останавливается во время выполнения. См. Справочное руководство по оптимизации архитектур Intel® 64 и IA-32 для x86; По опыту могу сказать, что на PPC еще хуже. - person Crashworks; 08.05.2012
comment
@Crashworks, у меня нет опыта в этом, и я уважаю твой. Это очень удивительно. Как насчет первоклассных процессоров, таких как Core i7? Они должны передавать muls? - person usr; 08.05.2012
comment
@usr Я не знаком с этой оптимизацией. У вас есть ссылка? Единственное, что я могу придумать, это использовать модульную инверсию, но это будет работать только для нечетных чисел. - person vhallac; 08.05.2012
comment
@BenVoigt Разве это не модульное умножение? - person vhallac; 08.05.2012
comment
ridiculousfish.com/blog/posts/labor-of-division- Episode-i.html Эта серия постов в блоге превосходна. Я прочитал его несколько дней назад. - person usr; 08.05.2012
comment
@vhallac Да, вся компьютерная целочисленная арифметика является модульной (более 2 ^ 32 или 2 ^ 64, естественно). Сначала я не поверил этому ответу, пока не посмотрел на вывод моего компилятора, и он действительно испускает мультипликативную инверсию. usr: Я полагаю, что это руководство для современных i7s. Целочисленное умножение очень сложно вписать в конвейер, потому что оно имеет очень много задержек ворот (bit.ly/JQRyeY) . Кроме того, многие процессоры реализуют его как итеративный алгоритм на одном сумматоре с частичным произведением, что означает, что он микрокодирован, а также не имеет постоянного количества шагов. - person Crashworks; 08.05.2012

arrow_upward
1
arrow_downward

Как правило, самый быстрый способ — индексировать достаточно большой массив указателей на строки. Один просмотр массива, одно разыменование указателя. Однако это сильно влияет на использование памяти ... Такова природа инженерных компромиссов. Насколько быстро достаточно быстро?

person Jens    schedule 07.05.2012
comment
Нет достаточно быстрого. То, что работает лучше всего, достаточно быстро - person fuz; 08.05.2012
comment
Да, есть достаточно быстро, потому что то, что работает лучше всего, обычно недостижимо из-за непомерных требований к ресурсам. Мой ответ - лучший пример. Достаточно ли у вас памяти для указателей 2 ** 64 и связанных строк? Возможно нет. Но я уверен, что это работает лучше всего. - person Jens; 08.05.2012
comment
Хороший контраргумент. Практически на всех машинах доступ к памяти ужасно медленный, если он не кэшируется. Таким образом, может быть преимуществом минимизировать количество выполняемых обращений к памяти. - person fuz; 08.05.2012

arrow_upward
1
arrow_downward

Версия printf для MS делает это "наивным" способом (после настройки набора переменных на основе необязательных флагов):

            while (precision-- > 0 || number != 0) {
                digit = (int)(number % radix) + '0';
                number /= radix;                /* reduce number */
                if (digit > '9') {
                    /* a hex digit, make it a letter */
                    digit += hexadd;
                }
                *text.sz-- = (char)digit;       /* store the digit */
            }
person AShelly    schedule 07.05.2012