Арифметика с произвольно большими целыми числами в PHP

Question

Хорошо, поэтому PHP не лучший язык для работы со сколь угодно большими целыми числами, учитывая, что он изначально поддерживает только 32-битные целые числа со знаком. Однако я пытаюсь создать класс, который мог бы представлять произвольно большое двоичное число и иметь возможность выполнять простые арифметические операции над двумя из них (сложение / вычитание / умножение / деление).

Моя цель связана с 128-битными целыми числами.

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

Подход № 1: Создать 128-разрядный целочисленный класс, который внутренне хранит его целое число в виде четырех 32-разрядных целых чисел. Единственная проблема, связанная с этим подходом, заключается в том, что я не уверен, что делать с обработкой проблем переполнения / потери при обработке отдельных фрагментов двух операндов.

Подход № 2: Используйте расширение bcmath, так как оно похоже на то, для чего оно было разработано. Единственное, что меня беспокоит при использовании этого подхода, - это настройка масштаба расширения bcmath, потому что в моих 128-битных целых числах не может быть ошибок округления; они должны быть точными. Меня также беспокоит возможность в конечном итоге преобразовать результат функций bcmath в двоичную строку (которую позже мне понадобится добавить в некоторые функции шифрования mcrypt).

Подход № 3: Сохраните числа в виде двоичных строк (вероятно, младший младший разряд). Теоретически я должен иметь возможность хранить целые числа любого произвольного размера таким образом. Все, что мне нужно сделать, это написать четыре основные арифметические функции для выполнения add / sub / mult / div над двумя двоичными строками и получения результата двоичной строки. Это именно тот формат, который мне нужно передать mcrypt, так что это дополнительный плюс. Это подход, который, на мой взгляд, наиболее перспективен на данный момент, но у меня есть одно препятствие: PHP не предлагает мне никакого способа манипулирования отдельными битами (о которых я знаю). Я полагаю, что мне придется разбить его на куски размером в байты (без каламбура), после чего применяются мои вопросы об обработке переполнения / недостаточного заполнения из подхода № 1.

Answer 1

Расширение PHP GMP будет лучше для этого. В качестве дополнительного бонуса вы можете использовать его для преобразования десятичных чисел в двоичные, например:

gmp_strval(gmp_init($n, 10), 2);

Answer 2

Для этого уже есть различные классы , так что вы можете захотеть взглянуть на них, прежде чем писать собственное решение (если действительно необходимо написать собственное решение).

Answer 3

Насколько я могу судить, расширение bcmath - это то, что вам нужно. Данные в руководстве по PHP немного скудны, но вы можете установить точность в точности, как вам нужно, используя функцию bcscale () или необязательный третий параметр в большинстве других функций bcmath. Не слишком уверен насчет бинарных строк, но немного погуглив, говорит, что вы должны иметь возможность делать это с помощью функции pack ().

Answer 4

Я реализовал следующую Оценку BC PEMDAS по жалобам , которая может быть вам полезна.

function BC($string, $precision = 32)
{
    if (extension_loaded('bcmath') === true)
    {
        if (is_array($string) === true)
        {
            if ((count($string = array_slice($string, 1)) == 3) && (bcscale($precision) === true))
            {
                $callback = array('^' => 'pow', '*' => 'mul', '/' => 'div', '%' => 'mod', '+' => 'add', '-' => 'sub');

                if (array_key_exists($operator = current(array_splice($string, 1, 1)), $callback) === true)
                {
                    $x = 1;
                    $result = @call_user_func_array('bc' . $callback[$operator], $string);

                    if ((strcmp('^', $operator) === 0) && (($i = fmod(array_pop($string), 1)) > 0))
                    {
                        $y = BC(sprintf('((%1$s * %2$s ^ (1 - %3$s)) / %3$s) - (%2$s / %3$s) + %2$s', $string = array_shift($string), $x, $i = pow($i, -1)));

                        do
                        {
                            $x = $y;
                            $y = BC(sprintf('((%1$s * %2$s ^ (1 - %3$s)) / %3$s) - (%2$s / %3$s) + %2$s', $string, $x, $i));
                        }

                        while (BC(sprintf('%s > %s', $x, $y)));
                    }

                    if (strpos($result = bcmul($x, $result), '.') !== false)
                    {
                        $result = rtrim(rtrim($result, '0'), '.');

                        if (preg_match(sprintf('~[.][9]{%u}$~', $precision), $result) > 0)
                        {
                            $result = bcadd($result, (strncmp('-', $result, 1) === 0) ? -1 : 1, 0);
                        }

                        else if (preg_match(sprintf('~[.][0]{%u}[1]$~', $precision - 1), $result) > 0)
                        {
                            $result = bcmul($result, 1, 0);
                        }
                    }

                    return $result;
                }

                return intval(version_compare(call_user_func_array('bccomp', $string), 0, $operator));
            }

            $string = array_shift($string);
        }

        $string = str_replace(' ', '', str_ireplace('e', ' * 10 ^ ', $string));

        while (preg_match('~[(]([^()]++)[)]~', $string) > 0)
        {
            $string = preg_replace_callback('~[(]([^()]++)[)]~', __FUNCTION__, $string);
        }

        foreach (array('\^', '[\*/%]', '[\+-]', '[<>]=?|={1,2}') as $operator)
        {
            while (preg_match(sprintf('~(?<![0-9])(%1$s)(%2$s)(%1$s)~', '[+-]?(?:[0-9]++(?:[.][0-9]*+)?|[.][0-9]++)', $operator), $string) > 0)
            {
                $string = preg_replace_callback(sprintf('~(?<![0-9])(%1$s)(%2$s)(%1$s)~', '[+-]?(?:[0-9]++(?:[.][0-9]*+)?|[.][0-9]++)', $operator), __FUNCTION__, $string, 1);
            }
        }
    }

    return (preg_match('~^[+-]?[0-9]++(?:[.][0-9]++)?$~', $string) > 0) ? $string : false;
}

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