Арифметика с произвольно большими целыми числами в PHP
https://stackoverflow.com/questions/37391
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Итак, PHP не лучший язык для работы с произвольно большими целыми числами, учитывая, что он изначально поддерживает только 32-разрядные целые числа со знаком. Однако я пытаюсь создать класс, который мог бы представлять произвольно большое двоичное число и иметь возможность выполнять простые арифметические операции над двумя из них (добавить / вычесть / умножить / разделить).
Моя цель связана с 128-битными целыми числами.
Есть пара подходов, на которые я смотрю, и проблемы, которые я вижу с ними. Будем весьма благодарны за любые комментарии или комментарии относительно того, что вы выберете и как вы можете это сделать.
Подход № 1: Создайте 128-разрядный целочисленный класс, который внутренне хранит его как четыре 32-разрядных целых числа. Единственная проблема с этим подходом состоит в том, что я не уверен, как поступить с проблемами переполнения / недополнения при манипулировании отдельными порциями двух операндов.
Подход №2. Используйте расширение bcmath, поскольку оно похоже на то, для чего оно было разработано. Единственное, что меня беспокоит при использовании этого подхода, - это настройка масштаба расширения bcmath, потому что в моих 128-битных целых числах не может быть ошибок округления; они должны быть точными. Меня также беспокоит возможность в конечном итоге преобразовать результат функций bcmath в двоичную строку (которую мне позже понадобится добавить в некоторые функции шифрования mcrypt).
Подход № 3: Сохраняйте числа в виде двоичных строк (вероятно, младший младший раз) Теоретически я должен иметь возможность хранить целые числа любого произвольного размера таким образом. Все, что мне нужно сделать, это написать четыре основные арифметические функции для выполнения add / sub / mult / div над двумя двоичными строками и получения результата двоичной строки. Это именно тот формат, который мне нужно передать mcrypt, так что это дополнительный плюс. Это подход, который, на мой взгляд, наиболее перспективен на данный момент, но у меня есть одно препятствие: PHP не предлагает мне никакого способа манипулирования отдельными битами (о которых я знаю). Я полагаю, что мне придется разбить его на куски размером в байты (без каламбура), после чего мои вопросы об обработке переполнения / недостаточного заполнения из подхода № 1 применимы.
Решение
расширение PHP GMP будет лучше для этого. В качестве дополнительного бонуса вы можете использовать его для преобразования десятичных чисел в двоичные, например:
gmp_strval(gmp_init($n, 10), 2);
Другие советы
Насколько я могу судить, расширение bcmath - это то, что вам нужно. Данные в руководстве по PHP немного скудны, но вы можете установить точность в точности, как вам нужно, используя функцию bcscale () или необязательный третий параметр в большинстве других функций bcmath. Не слишком уверен в отношении бинарных строк, но, немного погуглив, говорит, что вы должны иметь возможность делать это с помощью функции pack ().
Я реализовал следующую жалобу PEMDAS / BC а> что может быть полезно для вас.
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;
}
Он автоматически обрабатывает ошибки округления, просто установите точность на любые цифры, которые вам нужны.
