Cálculo de precisión arbitraria Explicación

StackOverflow https://stackoverflow.com/questions/1218149

  •  10-07-2019
  •  | 
  •  

Pregunta

Estoy tratando de aprender C y han llegado a través de la incapacidad para trabajar con números grandes (es decir, de 100 dígitos, 1000 dígitos, etc.).Soy consciente de que existen las bibliotecas para hacer esto, pero quiero intentar aplicar a mí mismo.

Solo quiero saber si alguien tiene o puede proporcionar una forma muy detallada, atontada explicación de cálculo de precisión arbitraria.

¿Fue útil?

Solución

Es todo una cuestión de almacenamiento adecuado y algoritmos para el tratamiento de números de partes más pequeñas.Supongamos que usted tiene un compilador en el que un int sólo puede ser de 0 a 99 y desea manejar los números hasta 999999 (sólo vamos a preocuparse por los números positivos aquí para keep it simple).

Para ello hay que dar a cada número tres ints y utilizando las mismas reglas que usted (debe tener) aprendió en la escuela primaria para la suma, la resta y la de otras operaciones básicas.

En una precisión arbitraria de la biblioteca, no hay ningún límite en el número de la base de los tipos utilizados para representar los números, lo que la memoria puede contener.

Además, por ejemplo: 123456 + 78:

12 34 56
      78
-- -- --
12 35 34

Trabajando desde el menos significativo de la final:

  • inicial de llevar a = 0.
  • 56 + 78 + 0 llevar a = 134 = 34 con 1 llevar a
  • 34 + 00 + 1 llevar a = 35 = 35 con 0 llevar a
  • 12 + 00 + 0 llevar a = 12 = 12 0 llevar a

Este es, en efecto, cómo la adición generalmente funciona en el nivel de bit dentro de su CPU.

La resta es similar (con la resta de la base y tipo de prestado en lugar de llevar), la multiplicación se puede hacer con la repetición de las adiciones (muy lento) o cruzada de productos (más rápido) y la división es más complicado pero se puede hacer por el cambio y la resta de los números involucrados (la división larga habrían aprendido como un niño).

De hecho, he escrito bibliotecas para hacer este tipo de cosas a través de las máximas potencias de diez que pueden encajar en un número entero al cuadrado (para evitar el desbordamiento, cuando la multiplicación de dos ints juntos, como una de 16 bits int se limita a 0 a 99 para generar 9,801 (<De 32.768) cuando se eleva al cuadrado, o de 32 bits int el uso de 0 a 9,999 para generar 99,980,001 (<2,147,483,648)), que en gran medida alivió los algoritmos.

Algunos trucos a tener en cuenta.

1/ a la hora de sumar o multiplicar números, pre-asignar el máximo espacio necesario entonces reducir más tarde si se encuentra que es demasiado.Por ejemplo, la adición de dos de 100"digit" (donde dígito es un int) los números nunca le dará más de 101 dígitos.Multiplicar un número de 12 dígitos por un número de 3 dígitos que nunca generará más de 15 dígitos (agregar el dígito cuenta).

2/ Para mayor velocidad, normalizar (reducir el espacio de almacenamiento requerido para) los números sólo si es absolutamente necesario - mi biblioteca tenía esto como una llamada independiente por lo que el usuario puede decidir entre la velocidad y el almacenamiento de preocupaciones.

3/ Adición de un positivo y un número negativo se resta, y restar un número negativo es lo mismo que sumar el equivalente positivo.Usted puede ahorrar un poco de código por tener el sumar y restar métodos se llaman unos a otros después de ajustar los signos.

4/ Evitar restar números grandes de los pequeños, ya que invariablemente terminan con números como:

         10
         11-
-- -- -- --
99 99 99 99 (and you still have a borrow).

En lugar de ello, restar 10 de 11, luego negarlo:

11
10-
--
 1 (then negate to get -1).

Aquí están los comentarios (se convirtió en el texto) de una de las bibliotecas que tenía que hacer esto para.El código en sí es, por desgracia, derechos de autor, pero usted puede ser capaz de recoger la información suficiente para manejar las cuatro operaciones básicas.Asumir en el siguiente que -a y -b representar números negativos y a y b son cero o números positivos.

Para además, si los signos son diferentes, el uso de la resta de la negación:

-a +  b becomes b - a
 a + -b becomes a - b

Para resta, si los signos son diferentes, utilizar, además de la negación:

 a - -b becomes   a + b
-a -  b becomes -(a + b)

También manejo especial para asegurar que estamos restando un pequeño número de grandes:

small - big becomes -(big - small)

La multiplicación utiliza la entrada de nivel de matemáticas de la siguiente manera:

475(a) x 32(b) = 475 x (30 + 2)
               = 475 x 30 + 475 x 2
               = 4750 x 3 + 475 x 2
               = 4750 + 4750 + 4750 + 475 + 475

La forma en que esto se logra consiste en la extracción de cada uno de los dígitos de 32 de una en una (hacia atrás), a continuación, utilizando agregar para calcular un valor añadido al resultado (inicialmente cero).

ShiftLeft y ShiftRight las operaciones de forma rápida multiplicar o dividir una LongInt por la envoltura de valor (10 "real" de las matemáticas).En el ejemplo anterior, podemos agregar 475 a cero 2 veces (el último dígito de 32) para obtener 950 (resultado = 0 + 950 = 950).

Luego nos fuimos a cambio de 475 a obtener 4750 y a la derecha mayús 32 para obtener 3.Agregar 4750 a cero 3 veces para obtener 14250, a continuación, agregue el resultado de 950 a obtener 15200.

Desplazamiento a la izquierda de 4750 para obtener 47500, mayús derecha 3 para obtener 0.Desde el desplazado a la derecha de 32 ahora es cero, hemos terminado y, de hecho 475 x 32 igual 15200.

División también es complicado, pero basado en los principios de la aritmética (la "gazinta" método para "entra").Considere la siguiente división larga para 12345 / 27:

       457
   +-------
27 | 12345    27 is larger than 1 or 12 so we first use 123.
     108      27 goes into 123 4 times, 4 x 27 = 108, 123 - 108 = 15.
     ---
      154     Bring down 4.
      135     27 goes into 154 5 times, 5 x 27 = 135, 154 - 135 = 19.
      ---
       195    Bring down 5.
       189    27 goes into 195 7 times, 7 x 27 = 189, 195 - 189 = 6.
       ---
         6    Nothing more to bring down, so stop.

Por lo tanto 12345 / 27 es 457 con el resto 6.Verificar:

  457 x 27 + 6
= 12339    + 6
= 12345

Esto se implementa mediante el uso de una muestra variable (inicialmente cero) para derribar a los segmentos de 12345 uno a la vez hasta que sea mayor o igual a 27.

Luego simplemente restar 27 de que hasta que no lleguemos a continuación 27 - el número de sustracciones es el segmento añadido a la parte superior de la línea.

Cuando no hay más segmentos para traer abajo, tenemos nuestro resultado.

Tenga en cuenta que estos son bastante algoritmos básicos.Hay formas mucho mejores para hacer compleja la aritmética si sus números van a ser particularmente grande.Usted puede mirar en algo como GNU Múltiples Aritmética de Precisión de la Biblioteca - es mucho mejor y más rápido que mis propias bibliotecas.

Tiene el lamentable misfeature en que simplemente va a salir si se ejecuta fuera de la memoria (más bien un defecto fatal para un propósito general de la biblioteca en mi opinión) pero, si usted puede mirar más allá de eso, es bastante buena en lo que hace.

Si no puede utilizar por razones de licencia (o porque no quiere que su aplicación acaba de salir de la sin razón aparente), que al menos podría obtener los algoritmos de allí para la integración en su propio código.

También he encontrado que el bod más en MPIR (un fork de GMP) son más susceptibles a los debates sobre los posibles cambios parecen más amigable para los desarrolladores montón.

Otros consejos

Si bien reinventar la rueda es extremadamente bueno para su edificación y aprendizaje personal, también es una tarea extremadamente grande. No quiero disuadirlo, ya que es un ejercicio importante y uno que he hecho yo mismo, pero debe tener en cuenta que hay problemas sutiles y complejos en el trabajo que abordan los paquetes más grandes.

Por ejemplo, multiplicación. Ingenuamente, puede pensar en el método de 'niño de escuela', es decir, escribir un número sobre el otro, luego hacer una multiplicación larga como aprendió en la escuela. ejemplo: 

      123
    x  34
    -----
      492
+    3690
---------
     4182

pero este método es extremadamente lento (O (n ^ 2), siendo n el número de dígitos). En cambio, los paquetes bignum modernos usan una transformación de Fourier discreta o una transformación numérica para convertir esto en una operación esencialmente O (n ln (n)).

Y esto es solo para enteros. Cuando ingresa a funciones más complicadas en algún tipo de representación real de números (log, sqrt, exp, etc.) las cosas se vuelven aún más complicadas.

Si desea algunos antecedentes teóricos, le recomiendo leer el primer capítulo del libro de Yap, " Problemas fundamentales del álgebra algorítmica " . Como ya se mencionó, la biblioteca gmp bignum es una biblioteca excelente. Para números reales, he usado mpfr y me ha gustado.

No reinvente la rueda: ¡podría resultar cuadrada!

Utilice una biblioteca de terceros, como GNU MP , que se ha probado y comprobado.

Usted es básicamente de la misma manera que con el lápiz y el papel...

  • El número es para ser representado en un buffer (matriz) capaz de tomar en un tamaño arbitrario (lo que significa que el uso de malloc y realloc) según sea necesario
  • implementar la aritmética básica tanto como sea posible, utilizando un lenguaje compatible estructuras, y de acuerdo con lleva y moviendo el radix-manualmente un punto de
  • que recorren el análisis numérico de los textos para encontrar eficiente argumentos para tratar por función más compleja
  • sólo implementar tanto como usted necesita.

Normalmente se utiliza como unidad básica de la computación

  • bytes que contiene con 0-99 o 0-255
  • 16 bits de palabras con marchitan entre 0-9999 o 0--65536
  • 32 bits de las palabras que contienen...
  • ...

según lo dictado por su arquitectura.

La elección de binario o de base decimal depende de los deseos para el máximo aprovechamiento del espacio, humanos legibilidad, y la presencia de la ausencia de Decimal Codificado en Binario (BCD) de apoyo de matemáticas en su chip.

Puedes hacerlo con el nivel de matemáticas de secundaria. Aunque en realidad se utilizan algoritmos más avanzados. Entonces, por ejemplo, para agregar dos números de 1024 bytes: 

unsigned char first[1024], second[1024], result[1025];
unsigned char carry = 0;
unsigned int  sum   = 0;

for(size_t i = 0; i < 1024; i++)
{
    sum = first[i] + second[i] + carry;
    carry = sum - 255;
}
El resultado

tendrá que ser mayor en one place en caso de suma para cuidar los valores máximos. Mira esto: 

9
   +
9
----
18

TTMath es una gran biblioteca si quieres aprender. Está construido con C ++. ¡El ejemplo anterior fue tonto, pero así es como se hacen las sumas y restas en general!

Una buena referencia sobre el tema es Complejidad computacional de las operaciones matemáticas . Le indica cuánto espacio se requiere para cada operación que desea implementar. Por ejemplo, si tiene dos N-digit números, entonces necesita 2N digits para almacenar el resultado de la multiplicación.

Como dijo Mitch , ¡no es una tarea fácil de implementar! Le recomiendo que eche un vistazo a TTMath si conoce C ++.

Una de las referencias finales (en mi humilde opinión) es el TAOCP Volumen II de Knuth. Explica muchos algoritmos para representar números y operaciones aritméticas en estas representaciones. 

@Book{Knuth:taocp:2,
   author    = {Knuth, Donald E.},
   title     = {The Art of Computer Programming},
   volume    = {2: Seminumerical Algorithms, second edition},
   year      = {1981},
   publisher = {\Range{Addison}{Wesley}},
   isbn      = {0-201-03822-6},
}

Suponiendo que desea escribir un código entero grande usted mismo, esto puede ser sorprendentemente simple de hacer, hablado como alguien que lo hizo recientemente (aunque en MATLAB). Aquí están algunos de los trucos que utilicé:

  • Almacené cada dígito decimal individual como un número doble. Esto simplifica muchas operaciones, especialmente la salida. Si bien ocupa más almacenamiento del que desea, la memoria es barata aquí y hace que la multiplicación sea muy eficiente si puede convolucionar un par de vectores de manera eficiente. Alternativamente, puede almacenar varios dígitos decimales en un doble, pero tenga en cuenta que la convolución para hacer la multiplicación puede causar problemas numéricos en números muy grandes.

  • Almacene un bit de signo por separado.

  • La adición de dos números es principalmente una cuestión de sumar los dígitos, luego verifique si hay un acarreo en cada paso.

  • La multiplicación de un par de números se realiza mejor como convolución seguida de un paso de acarreo, al menos si tiene un código de convolución rápido de barrido.

  • Incluso cuando almacena los números como una cadena de dígitos decimales individuales, se puede hacer una división (también operaciones mod / rem) para obtener aproximadamente 13 dígitos decimales a la vez en el resultado. Esto es mucho más eficiente que una división que funciona con solo 1 dígito decimal a la vez.

  • Para calcular la potencia de un entero, calcule la representación binaria del exponente. Luego use operaciones de cuadratura repetidas para calcular los poderes según sea necesario.

  • Muchas operaciones (factoring, pruebas de primalidad, etc.) se beneficiarán de una operación powermod. Es decir, cuando calcula mod (a ^ p, N), reduzca el resultado mod N en cada paso de la exponenciación donde p se ha expresado en forma binaria. No calcule a ^ p primero, y luego intente reducirlo mod N.

Aquí hay un ejemplo simple (ingenuo) que hice en PHP.

Implementé " Añadir " y " Multiplicar " y lo usé para un ejemplo de exponente.

http://adevsoft.com/simple-php -arbitrary-precision-integer-big-num-example /

Recorte de código 

// Add two big integers
function ba($a, $b)
{
    if( $a === "0" ) return $b;
    else if( $b === "0") return $a;

    $aa = str_split(strrev(strlen($a)>1?ltrim($a,"0"):$a), 9);
    $bb = str_split(strrev(strlen($b)>1?ltrim($b,"0"):$b), 9);
    $rr = Array();

    $maxC = max(Array(count($aa), count($bb)));
    $aa = array_pad(array_map("strrev", $aa),$maxC+1,"0");
    $bb = array_pad(array_map("strrev", $bb),$maxC+1,"0");

    for( $i=0; $i<=$maxC; $i++ )
    {
        $t = str_pad((string) ($aa[$i] + $bb[$i]), 9, "0", STR_PAD_LEFT);

        if( strlen($t) > 9 )
        {
            $aa[$i+1] = ba($aa[$i+1], substr($t,0,1));
            $t = substr($t, 1);
        }

        array_unshift($rr, $t);
     }

     return implode($rr);
}
Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top