Aritmética con enteros arbitrariamente grandes en PHP

Question

Ok, PHP no es el mejor lenguaje para tratar con enteros arbitrariamente grandes, considerando que solo admite nativamente enteros de 32 bits. Lo que intento hacer es crear una clase que pueda representar un número binario arbitrariamente grande y poder realizar operaciones aritméticas simples en dos de ellos (agregar/restar/multiplicar/dividir).

Mi objetivo es tratar con enteros de 128 bits.

Hay un par de enfoques que estoy viendo y problemas que veo con ellos. Cualquier comentario o comentario sobre lo que elegiría y cómo podría hacerlo sería muy apreciado.

Método n.º 1: Crea una clase entera de 128 bits que almacena su número entero internamente como cuatro enteros de 32 bits. El único problema con este enfoque es que no estoy seguro de cómo manejar problemas de desbordamiento/subdesbordamiento al manipular trozos individuales de los dos operandos.

Método n.º 2: Utilice la extensión bcmath, ya que parece algo para lo que fue diseñado. Mi única preocupación al tomar este enfoque es la configuración de la escala de la extensión bcmath, porque no puede haber ningún error de redondeo en mis enteros de 128 bits; deben ser precisos. También me preocupa poder convertir finalmente el resultado de las funciones bcmath en una cadena binaria (que más adelante necesitaré introducir en algunas funciones de cifrado de mcrypt).

Método n.º 3: Almacene los números como cadenas binarias (probablemente LSB primero). En teoría, debería poder almacenar enteros de cualquier tamaño arbitrario de esta manera. Todo lo que tendría que hacer es escribir las cuatro funciones aritméticas básicas para realizar add/sub/mult/div en dos cadenas binarias y producir un resultado de cadena binaria. Este es exactamente el formato que necesito entregar a mcrypt, así que eso es un plus añadido. Este es el enfoque que creo que es el más prometedor en este momento, pero el punto clave que tengo es que PHP no me ofrece ninguna forma de manipular los bits individuales (que yo sepa). Creo que tendré que dividirlo en trozos del tamaño de un byte (sin juego de palabras), momento en el cual se aplican mis preguntas sobre el manejo del desbordamiento/desbordamiento del Método n. ° 1.

Answer 1

El PHP GMP extension será mejor para esto. Como un beneficio adicional, que se puede utilizar para hacer su conversión de decimal a binario, así:

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

Answer 2

Ya existen varios classesavailable para esto, por lo que es posible que desee consultarlos antes de escribir su propia solución (si aún es necesario escribir su propia solución).

Answer 3

Por lo que puedo decir, la extensión bcmath es la que usted querrá. Los datos en el manual de PHP son un poco escasos, pero puede establecer la precisión para que sea exactamente lo que necesita utilizando la función bcscale() o el tercer parámetro opcional en la mayoría de las otras funciones bcmath. No estoy seguro del asunto de las cadenas binarias, pero un poco de google me dice que deberías poder hacer uso de la función pack().

Answer 4

que implementaron las siguientes PEMDAS complaint BC evaluator que puede ser útil para usted.

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

Trata automáticamente de los errores de redondeo, solo establece la precisión a cualquier dígito que necesites.