Преобразование числа в строку методом умножения на 10

В этом тексте рассматривается метод преобразование двоичного числа в строку без использования операций деления и остатка.

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

char* utoa_div(uint32_t value, char* buffer) {size_t index = 0;// преобразование в строкуdo {buffer[index++] = (value % 10) + '0'; value /= 10;}while (value > 0);buffer[index] = '\0';// разворачивание строкиint start = 0;int end = index - 1;while (start < end) {char temp = buffer[start];buffer[start] = buffer[end];buffer[end] = temp;start++;end--;}return buffer;}

Проверки буфера на NULL и его размера здесь и далее опущены для краткости. У этого метода есть ряд недостатков:

• цифры извлекаются в обратном порядке — от младшего десятичного разряда к старшему, нужно разворачивать результат;

• используется деление и модуль. При желании первого недостатка можно избавиться, если писать цифры в буфер с конца с уменьшением индекса и возвращать указатель на фактическое начало строки в буфере или посчитать количество десятичных цифр перед преобразованием. А вот с делением и модулем все куда интереснее. По сравнению с другими арифметическими операциями, деление может быть медленным или очень медленным даже на современных высокопроизводительных процессорах[1]. На архитектурах без аппаратного деления, таких как ARM Сortex M0 или базовый Risc-V всё намного медленней.

Существуют оптимизации, которые позволяют сократить количество делений, используя базу 100 вместо 10 для извлечения сразу двух десятичных цифр с помощью дополнительной таблицы. Такой подход, в частности, используется в функциях std::to_chars стандартной библиотеки C++ в GCC и Clang. Однако он не снижает общей асимптотики алгоритма, а только уменьшает множитель. Еще есть оптимизация: замена деления на константу умножением на обратную величину [2]. И современный компиляторы активно эту технику применяют. То есть стандартная to_chars уже очень хорошо оптимизирована. Удастся ли с ней потягаться в скорости?

Если требуемая система исчисления кратна 2 (на двоичных компьютерах) — 2, 8 или 16, то вместо деления можно использовать сдвиги, а цифры можно извлекать в любом порядке, как от младшего разряда к старшему, так и наоборот. Конечно, если начинать со старшего разряда, то сначала надо пропускать ведущие нули.

char *utoa_16(uint32_t value, char *buffer){    char *ptr = buffer;    int i = 0;    uint8_t digit;    // пропуск ведущих нулей    do    {        digit = (value >> 28) & 0x0f;        value <<= 4;    } while (digit == 0 && i++ < 8);      // излечение цифр от старшего разряда к младшему    do    {        *ptr++ = (digit < 10 ? '0' : 'a' - 10) + digit;        digit = (value >> 28) & 0x0f;        value <<= 4;    }while (++i < 8);    *ptr = 0;    return buffer;}

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

Допустим, что у нас есть 16-ти разрядное число с фиксированной точкой, где 4 старших бита представляют целую часть, а 12 младших — дробную. Веса целочисленных бит обычные степени двойки, а веса дробной части — отрицательные степени двойки.

Храниться такое число может в обычной целочисленной переменной, разница только в том как мы интерпретируем эти биты. Что удобно, арифметика для таких чисел работает почти также, как и для обычных целых. Умножение числа с фиксированной точкой на целое делается как просто умножение двух целых, с последующей интерпретацией результата как числа с фиксированной точкой. Например, имеем число 0.5 — бит 11 равен 1, остальные нули. Умножаем его на 10 и получаем число 5 в целочисленной части — биты 12 и 14 равны 1, остальные нули.

Таким образом, можно извлекать цифры в любой требуемой системе исчисления с помощью умножения, выделения целочисленной части с помощью битовых операций и ее очисткой перед следующей операцией. [3, глава 4.4, Method 2a]

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

а = a * 10;

Заменяется на

a = (a << 1) + (a << 3);

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

В [3] этот метод используется для преобразования дробных частей. Возникает вопрос как преобразовать целое число в дробное и при этом не потерять ни одного бита точности? Ведь при работе с целыми числами мы рассчитываем получить абсолютную точность, без ошибок и округлений. Плюс дополнительное ограничение: по возможности не выходить за пределы преобразуемого типа данных. Чтобы преобразовать целое число в дробь, нужно умножить его на 2 степени количество бит в дробной части и разделить на ближайшую степень 10:

fraction = value * 2^m / 10^n

где m — номер бита, разделяющего дробную и целую части, а n — количество десятичных цифр.

Рассуждения далее будут для 32-х битных чисел. Как показывает практика не все значения m и n одинаково полезны. С одной стороны, для обеспечения точности, целочисленная часть должна быть минимально достаточной, чтоб вместить одну цифру требуемого основания. Для 10 это 4 бита и казалось бы можно извлекать цифры с бита 28 по 31 включительно. 2^28 = 268’435’456. Ближайшая степень 10, меньшая этого числа это 100’000’000. А степень 10 надо брать исключительно меньше степени 2, для отсутствия потери точности в младших разрядах. Однако имеем до 2-х бит переполнение. С другой стороны для минимизации переполнения отношение степени 2 к степени 10 должно быть как можно ближе к 1.

Поэтому с учетом возможных переполнений, необходимости остаться при этом в рамках 32-х битной арифметики лучше подходят значения n = 27 и m = 8.

fraction = value * 134’217’728 / 100’000’000

Для 32-х разрядного числа здесь потребуется 64-х битная арифметика и медленное деление. Умножение и последующее деление можно выразить как умножение на дробь:

k = 2^27 / 10^8 = 134’217’728 / 100’000’000 = 1.34217728 fraction = value * k

Переполнение при этом может быть максимум на 1 бит. Наименьшее число, которое вызовет переполнение, будет:

overflow_limit = 2^32 / 2^27 * 10^8 = 3’200’000’000

Если переполнение произошло, то результат преобразования в десятичном виде будет по модулю 3’200’000’000. То есть для его коррекции достаточно добавить 3 и 2 к двум старшим цифрам соответственно. Теперь возникает вопрос как эффективно умножить преобразуемое число на дробную константу k. Использование плавающей точки не вариант, так как не везде доступно и помет привести как к потерям точности, так и производительности. Коэффициент k удобно представить также в виде 32-ч битного числа с фиксированной точкой, но без целой части. Тогда результат умножения будет иметь все необходимые 32 бита точности. Для восполнения утраченной единицы, нужно сложить результат умножение с исходным числом.

fraction = value + value * 0.34217728

Для умножения на дробную величину можно воспользоваться функцией mulhsu 4, которая возвращает старшую половину от длинного умножения. На большинстве современных 32-х битных архитектурах имеется инструкция умножения 32*32=>64 бита.

uint32_t mulhsu_r(uint32_t u, uint32_t v){    uint64_t prod = (uint64_t)u * v;    prod += u >> 2; // дополнительное округление    return prod >> 32;}

Если такой инструкции нет, или тип uint64_t не доступен в компиляторе, то можно воспользоваться методом из [4, 8.2]:

uint32_t mulhsu_r(uint32_t u, uint32_t v){    uint32_t u0, v0, w0, t;    uint32_t u1, v1, w1, w2;    u0 = u & 0x0000ffff;    u1 = u >> 16;    v0 = v & 0x0000ffff;    v1 = v >> 16;    w0 = u0 * v0;    t = u1 * v0 + (w0 >> 16);    t += (u >> 18); // дополнительное округление    w1 = t & 0x0000ffff;    w2 = t >> 16;    w1 = u0 * v1 + w1;    return u1 * v1 + w2 + (w1 >> 16);}

Важно отметить, что дробь 0.34217728 имеет бесконечное периодическое представление в двоичной форме. Поэтому потребуется округление промежуточного результата. Без округления результат преобразования окажется заниженным на 1 примерно у 13% всех чисел. Непонятно почему, для округления промежуточного произведения, к нему требуется добавить 1/4 исходного числа, хотя интуитивно кажется, что там должна быть 1/2. Для 64-х и 128-и разрядных чисел добавка для округления составляет именно 1/2.

После умножения получилось число, содержащее 5 бит целой части, 27 бит дробной части и 1 бит возможного переполнения. Целую часть надо обработать отдельно, она может быть от 0 до 31, и быстрее всего преобразовать её с помощью цикла вычитания 10 из второй цифры результата, добавляя 1 к первой цифре, будет не более 3 итераций этого цикла. Переполнение может возникнуть если входное значение равно или превышает следующую величину:

overflow_limit = 2^32 * 10^8 / 2 ^ 27 = 3200000000

Для коррекции переполнения, так как оно максимум 1 бит, достаточно добавить “32” к старшим числам результата преобразования. Собираем всё вместе:

char *utoa_fract(uint32_t value, char *ptr){    constexpr uint32_t max_pow10 = 100'000'000ul;    constexpr uint32_t extract_bit_pos = 27;    constexpr uint32_t magic_constant = ((1ull << (32 + extract_bit_pos)) / max_pow10) - (1ull << 32);    constexpr uint32_t overflow_limit = (1ull << 32) * max_pow10 / (1ull << extract_bit_pos);    constexpr uint32_t extract_mask = ((1ull << 32) - 1) >> (32 - extract_bit_pos);    if (value == 0)    {        ptr[0] = '0';        ptr[1] = 0;        return ptr + 1;    }    char *end = ptr + 10;    // преобразование в десятичную дробь    uint32_t t = value + mulhsu_r(value, magic_constant) + 1;    uint8_t digit = uint8_t(t >> extract_bit_pos);        bool overflow = value >= overflow_limit;    // обработка переполнения и целочисленной части    if (overflow || digit > 9)    {        ptr[0] = overflow ? '3' : '0';        ptr[1] = (overflow ? '2' : '0') + digit;        while (ptr[1] > '9')        {            ptr[1] -= 10;            ptr[0]++;        }        ptr += 2;    }    else    {        // пропуск ведущих нулей        while ((t & 0xfffE'0000) == 0)        {            t *= 10000;            end -= 4;        }        while ((t & ~extract_mask) == 0)        {            t *= 10;            end--;        }        digit = uint8_t(t >> extract_bit_pos);        *ptr++ = digit + '0';    }    // извлечение десятичных цифр    while (ptr < end)    {        t = (t & extract_mask) * 10;        digit = uint8_t(t >> extract_bit_pos);        *ptr++ = digit + '0';    }    return ptr;}

Проведём замер скорости по сравнению с самым быстрым из стандартных для С++ способом std::to_chars. В таблице время выполнения в секундах на 10 миллионов итераций.

В среднем метод с умножением оказался примерно на треть быстрее std::to_chars. Для 64-х разрядных чисел этот метод имеет более скромное преимущество в среднем около 10%. В случае 128-ми разрядных чисел описываемый метод оказывается медленней для чисел менее 5 знаков из-за необходимости пропуска большого количества ведущих нулей. Однако, в среднем преимущество получается более 3.5.

Заключение

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

Разработанная функция utoa_fract реализует этот метод. Она использует умножение на специально подобранную дробную константу, работу с фиксированной точкой и эффективные операции для извлечения цифр. Несмотря на кажущуюся сложность по сравнению с традиционным методом деления, реализация utoa_fract оказывается значительно более производительной. Практические замеры показывают, что в среднем она работает примерно на треть быстрее, чем оптимизированная стандартная функция std::to_chars из библиотеки C++. Это делает метод умножения привлекательным для задач, чувствительных к скорости выполнения, особенно в системах реального времени или встраиваемых приложениях, где ресурсы процессора ограничены. Таким образом, описанная техника представляет собой эффективную альтернативу классическим алгоритмам преобразования чисел в строки.

Исходный код

https://gitflic.ru/project/chizhovka/utoa

Список источников.

1. https://mark1626.github.io/posts/2022/05/20/cost-of-int-division/

2. https://habr.com/ru/articles/256827/

3. Knuth, TAOCP, Volume 2

4. Henry S. Warren Jr. Hacker’s Delight.