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

Question

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

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

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

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

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

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

Answer 1

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

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

Answer 2

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

Answer 3

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

Answer 4

я реализовал следующие PEMDAS complaint BC evaluator, которые могут быть полезными для вас.

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; 
} 

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