AzaMath — Cистемы счисления (включая кастомные) + арифметика произвольной точности на PHP

    Возникла недавно задача, связанная с конвертацией между различными позиционными системами счисления.

    В качестве реального применение обычно выступают сервисы для сокращения URL, использующие системы base36/base62 или, например, хранение большого количества огромных чисел в том же base62 для экономии памяти.

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

    Получилась AzaMath — библиотека для конвертации между системами счисления (включая кастомные) + удобная арифметика произвольной точности.

    Поддерживает PSR-0, легко ставится через composer, 100% покрытие кода тестами.

    Системы счисления


    Основной задачей библиотеки, на текущий момент, является перевод маленьких, больших и огромных чисел из одной позиционной системы счисления в другую. Поддержка стандартных систем с основанием от 2 до 62 включительно, а также поддержка позиционных систем со своим собственным алфавитом (хоть все символы ASCII). Также желательно поддерживать отрицательные числа и дроби.

    Для начала анализ альтернативных реализаций, которые можно использовать.

    Вариант 1 — Специальные функции (decbin, bindec, decoct, ...)

    Шесть функций, входящих в PHP, для конвертации между самыми распространенными системами счисления (10, 2, 8, 16).
    Плюсы Минусы
    • Самый быстрый способ

    • Платформозависимый формат отрицательного числа. Без использования знака '-'. Это не подходит, потому что у нас могут быть числа любого размера
    • Максимальное поддерживаемое число равно константе PHP_INT_MAX
    • Дроби не поддерживаются
    • Игнорирует некорректные символы в исходном числе, но только при конвертации в десятичное число. В обратную сторону уже не работает.
    • Ограниченное число систем счисления


    Вариант 2 — base_convert

    Стандартная функция PHP, для конвертации между системами счисления от 2 до 36 включительно.
    Плюсы Минусы
    • Игнорирует некорректные символы в исходном числе

    • Отрицательные числа не поддерживаются
    • Максимальное поддерживаемое число равно константе PHP_INT_MAX + 1
    • Дроби не поддерживаются
    • Ограниченное число систем счисления
    • Медленнее на 40–70%, чем специальные функции


    Вариант 3 — GMP (gmp_strval(gmp_init($number, $x), $y))

    При наличии расширения GMP можно использовать функции для изменения системы счисления оттуда. Поддерживаются системы от 2 до 62 и от -2 до -36 (обычные системы 2–36, только на выходе буквы в верхнем регистре).
    Плюсы Минусы
    • Отрицательные числа поддерживаются нормально
    • Нет ограничения на размер числа
    • Поддерживаются все стандартные системы счисления (2–62)

    • Дроби не поддерживаются
    • Ошибка конвертации при некорректных символах в исходном числе
    • Медленнее на 70–90%, base_convert
    • Медленнее на 70–215%, чем специальные функции

    Свой вариант конвертации был реализован полностью независимо от сторонних расширений и без промежуточного конвертирования в десятичную системы, что позволило ему быть настолько быстрым, насколько это возможно на PHP (это медленно :) — примерно на 6000% медленнее, чем GMP реализация. Поэтому, при возможности, всегда используется более быстрая реализация. Также очень рекомендуется установить расширение GMP, если вдруг понадобится много и регулярно конвертировать числа. Отрицательные числа полностью поддерживаются.

    В комплект библиотеки, в качестве примера, входят три нестандартные системы счисления: base32 и base64 c алфавитами известных систем кодирования по стандарту RFC4648, также base64url из того же стандарта — base64 c алфавитом безопасным для использования в URL. Следует учитывать, что это конвертация чисел, а не произвольных строк, поэтому результат base64 будет совершенно отличным от результата функции base64_encode.

    Увы, поддержку дробей пока не закончил — не удалось сделать достаточно быстро и пришлось отложить. Возможно сделаю позже, либо, если кому-то это понадобится, с удовольствием приму pull-реквест с этой фичей.

    Примеры использования


    $res = NumeralSystem::convert('WIKIPEDIA', 36, 10);
    echo $res . PHP_EOL; // 91730738691298
    
    $res = NumeralSystem::convert('9173073869129891730738691298', 10, 16);
    echo $res . PHP_EOL; // 1da3c9f2dd3133d4ed04bce2
    
    $res = NumeralSystem::convertTo('9173073869129891730738691298', 62);
    echo $res . PHP_EOL; // BvepB3yk4UBFhGew
    
    $res = NumeralSystem::convertFrom('BvepB3yk4UBFhGew', 62);
    echo $res . PHP_EOL; // 9173073869129891730738691298
    

    // Добавляем новую систему c произвольным алфавитом.
    // Каждый символ должен встречаться только один раз.
    // Допустимы только ASCII символы.
    $alphabet = '!@#$%^&*()_+=-'; // эквивалент base14
    $name     = 'StrangeSystem';
    NumeralSystem::setSystem($name, $alphabet);
    
    $number = '9999';
    $res = NumeralSystem::convertTo($number, $name);
    echo $res . PHP_EOL; // $)!$
    
    $res = NumeralSystem::convertFrom($res, $name);
    echo $res . PHP_EOL; // 9999
    


    Арифметика произвольной точности


    Оперирование над большими числами выполнено в качестве удобной обертки над расширением BCMath. В исходном состоянии BCMath не слишком удобен для реального применения. Одно только наполнение результата нулями до указанной точности (1234.2130000000...) чего стоит.

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

    Все числа внутри представляются в виде строки, но на входе принимаются и типы int/float. При тестах быстро выяснилось, насколько сильно теряется точность с типом данных float. К тому же экспоненциальная запись (12e26, 12e-26) вообще не поддерживается на уровне BCMath. Так что пришлось искать возможность сохранения максимально доступной точности, поэтому все числа с плавающей точкой на входе обрабатываются специальным алгоритмом, сохраняя точность, насколько это возможно.

    Примеры использования


    // Создаем новое число с указанной точностью вычислений - 20 (по умолчанию 100)
    $number = new BigNumber('118059162071741130342591466421', 20);
    
    // Деление
    $number->divide(12345678910);
    echo $number . PHP_EOL; // 9562792207086578954.49764831288650451382
    
    // Снова деление с округлением с указанной точностью и алгоритмом
    // Поддерживаются три алгоритма округления:
    //  1) HALF_UP - округление до целого наверх от *.5 (по умолчанию)
    //  2) HALF_DOWN - округление до целого вниз от *.5
    //  3) CUT, обрезка числа до указанной точности, все далее просто отбрасывается
    // Использовать можно, с помощью констант BigNumber::ROUND_* или
    // со стандартными константами PHP - PHP_ROUND_HALF_UP, PHP_ROUND_HALF_DOWN
    $number->divide(9876543210)->round(3, PHP_ROUND_HALF_DOWN);
    echo $number . PHP_EOL; // 968232710.955
    

    // Сравнения чисел
    $number = new BigNumber(10);
    echo ($number->compareTo(20) < 0) . PHP_EOL; // 1
    echo $number->isLessThan(20) . PHP_EOL; // 1
    
    $number = new BigNumber(20);
    echo ($number->compareTo(10) > 0) . PHP_EOL; // 1
    echo $number->isGreaterThan(10) . PHP_EOL; // 1
    
    $number = new BigNumber(20);
    echo ($number->compareTo(20) === 0) . PHP_EOL; // 1
    echo $number->isLessThanOrEqualTo(20) . PHP_EOL; // 1
    

    // Фильтрация чисел. Аргументы всех функций также фильтруются.
    $number = new BigNumber("9,223 372`036'854,775.808000");
    echo $number . PHP_EOL; // 9223372036854775.808
    

    // Возводим в степень и выводим в 62-ричной системе счисления
    $number = new BigNumber('9223372036854775807');
    $number = $number->pow(2)->convertToBase(62);
    echo $number . PHP_EOL; // 1wlVYJaWMuw53lV7Cg98qn
    


    Ссылки



    UPD:
    Вышло небольшое обновление библиотеки — обертка для наиболее примитивных арифметических действий только над целыми числами любого размера, которая может работать без дополнительных расширений (нативная реализация, использует BCMath или GMP при наличии).
    О наших новых разработках и обновлениях открытых компонентов мы пишем теперь на нашем блоге AzaGroup.ru.
    Метки:
    • +12
    • 5,1k
    • 8
    Поделиться публикацией
    Комментарии 8
    • 0
      Можете пояснить эту конструкцию?
      if ($this->isNegative()) {
      	// 14 is the magic precision number
      	$number = bcadd($number, '0', 14);
      	if ('.00000000000000' !== substr($number, -15)) {
      		$number = bcsub($number, '1', 0);
      	}
      }
      
      • –3
        Эмпирически подобранная логика для округления отрицательных чисел к меньшему значению (floor). Подобный подход применяется еще в нескольких местах для оптимизаций и/или упрощения кода.

        Точность здесь учитывается только до 14 знака после запятой. Можно точнее, но вроде бы нет смысла.
        Такая же логика и для положительных чисел при округлении в верхнюю сторону (ceil).
        • +1
          Эмпирически подобранная логика в мат. библиотеке? Кхм… Почему-то вспомнился бородатый анекдот о военной кафедре и значении синуса, которое в военное время может достигать трех. Не обижайтесь только, это просто шутка конечно же. Удачи в дальнейшем совершенствовании вашей библиотеки.
          • 0
            В данном случае всегда будет ограничение точности. Оно может быть жестко задано, как сейчас, или быть привязанным к общей установленной точности вычисления. А экспериментально подобранная логика может быть уместна в любых библиотеках.
      • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          Нет, такого не планировалось. Погрешность еще и копится с каждой новой операцией. Не проще задать заведомо хороший запас точности? Тогда мелкие погрешности теряются при округлении результата до требуемой точности.
          • НЛО прилетело и опубликовало эту надпись здесь
            • 0
              Так можно же все вычисления проводить с точностью до 100 знака, потом округлять до двух. Погрешность будет копиться около последних ста чисел после запятой и без проблем отрезаться.
              Собственно как раз так использую.

        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.