math - isprobableprime - Aritmética de precisión arbitraria Explicación

isprobableprime biginteger (8)

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

Implementé "Agregar" 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); }

Estoy tratando de aprender C y me he encontrado con la imposibilidad de trabajar con números REALMENTE grandes (es decir, 100 dígitos, 1000 dígitos, etc.). Soy consciente de que existen bibliotecas para hacer esto, pero quiero intentar implementarlo yo mismo.

Solo quiero saber si alguien tiene o puede proporcionar una explicación muy detallada y simplista de la aritmética de precisión arbitraria.

Lo haces básicamente de la misma manera que lo haces con lápiz y papel ...

El número se representará en un búfer (matriz) capaz de tomar un tamaño arbitrario (lo que significa usar malloc y realloc ) según sea necesario
implementa la aritmética básica tanto como sea posible usando estructuras soportadas por el lenguaje, y trata con acarreos y moviendo el punto de la raíz manualmente
exploras textos de análisis numérico para encontrar argumentos eficientes para tratar con funciones más complejas
solo implementa todo lo que necesita.

Normalmente usarás como unidad básica de cálculo

bytes que contienen con 0-99 o 0-255
Las palabras de 16 bits que contienen wither 0-9999 o 0--65536
Palabras de 32 bits que contienen ...
...

según lo dictado por su arquitectura.

La elección de la base binaria o decimal depende de los deseos de la máxima eficiencia de espacio, la legibilidad humana y la ausencia de soporte matemático con codificación decimal binaria (BCD) en el chip.

Mientras que reinventar la rueda es extremadamente bueno para su edificación y aprendizaje personal, también es una tarea extremadamente grande. No quiero disuadirte ya que es un ejercicio importante y que he hecho yo mismo, pero debes tener en cuenta que hay cuestiones sutiles y complejas en el trabajo que abordan los paquetes más grandes.

Por ejemplo, multiplicación. Ingenuamente, podrías pensar en el método del ''colegial'', es decir, escribir un número sobre el otro, luego hacer una multiplicación larga como aprendiste 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 transformada discreta de Fourier o una transformada numérica para convertir esto en una operación esencialmente O (n ln (n)).

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

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 excelente biblioteca. Para números reales, he usado mpfr y me ha gustado.

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

Use una biblioteca de terceros, como GNU MP , probada y probada.

Puedes hacerlo con el nivel de matemáticas de la escuela secundaria. Aunque los algoritmos más avanzados se utilizan en la realidad. 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 más grande en one place en caso de que se agregue para cuidar los valores máximos. Mira este :

9 + 9 ---- 18

TTMath es una gran biblioteca si quieres aprender. Está construido usando C ++. El ejemplo anterior fue tonto, ¡pero así es como se hace la suma y la resta en general!

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

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

Suponiendo que desee escribir un código entero grande usted mismo, esto puede ser sorprendentemente simple de hacer, hablada como alguien que lo hizo recientemente (aunque en MATLAB). Estos son algunos de los trucos que utilicé:

Almacenaba cada dígito decimal individual como un número doble. Esto hace que muchas operaciones sean simples, especialmente la salida. Aunque ocupa más espacio de almacenamiento de lo que podrías desear, la memoria es barata aquí, y hace que la multiplicación sea muy eficiente si puedes combinar 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 suma de dos números es principalmente una cuestión de sumar los dígitos, luego verificar el 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ápida al tocar.
Incluso cuando almacena los números como una cadena de dígitos decimales individuales, la división (también mod / rem ops) se puede hacer 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 solo con 1 dígito decimal a la vez.
Para calcular una potencia entera 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 (factoraje, pruebas de primalidad, etc.) se beneficiarán de una operación powermod. Es decir, cuando se calcula mod (a ^ p, N), se reduce el resultado mod N en cada paso de la exponenciación donde p se ha expresado en forma binaria. No calcule un ^ p primero, y luego intente reducirlo mod N.

Una de las referencias definitivas (en mi humilde opinión) es el Volumen II de TAOCP 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}, }

Todo es una cuestión de almacenamiento adecuado y algoritmos para tratar los números como partes más pequeñas. Supongamos que tiene un compilador en el que un int solo puede ser de 0 a 99 y desea manejar números hasta 999999 (solo nos preocuparemos de los números positivos aquí para que todo sea sencillo).

Lo haces dando a cada número tres int y usando las mismas reglas que (deberías) haber aprendido en la escuela primaria para sumar, restar y las otras operaciones básicas.

En una biblioteca de precisión arbitraria, no hay un límite fijo en la cantidad de tipos de base utilizados para representar nuestros números, simplemente cualquier memoria que pueda contener.

Además, por ejemplo: 123456 + 78 :

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

Trabajando desde el final menos significativo:

carga inicial = 0.
56 + 78 + 0 acarreo = 134 = 34 con 1 acarreo
34 + 00 + 1 acarreo = 35 = 35 con 0 acarreo
12 + 00 + 0 acarreo = 12 = 12 con 0 acarreo

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

La resta es similar (utilizando resta del tipo base y tomando prestado en lugar de carry), la multiplicación puede hacerse con adiciones repetidas (muy lenta) o productos cruzados (más rápidos) y la división es más complicada pero puede hacerse cambiando y restando los números involucrado (la división larga que hubieras aprendido de niño).

De hecho, he escrito bibliotecas para hacer este tipo de cosas usando los poderes máximos de diez que pueden caber en un entero al cuadrado (para evitar el desbordamiento al multiplicar dos int s juntos, como un int 16 bits que se limita a 0 a través de 99 para generar 9,801 (<32,768) al cuadrado, o 32 int usando 0 a 9.999 para generar 99,980,001 (<2,147,483,648)) que alivió en gran medida los algoritmos.

Algunos trucos a tener en cuenta.

1 / Al agregar o multiplicar números, preasigne el espacio máximo necesario y luego reduzca más adelante si encuentra que es demasiado. Por ejemplo, agregar dos números de 100 dígitos (donde el dígito es un número int ) 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 nunca generará más de 15 dígitos (suma los dígitos).

2 / Para mayor velocidad, normalice (reduzca el almacenamiento requerido para) los números solo si es absolutamente necesario - mi biblioteca lo tuvo como una llamada separada para que el usuario pueda decidir entre velocidad y preocupaciones de almacenamiento.

3 / La suma de un número positivo y negativo es una resta, y restar un número negativo es lo mismo que sumar el equivalente positivo. Puede guardar bastante código haciendo que los métodos de sumar y restar se llamen unos a otros después de ajustar los letreros.

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

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

En cambio, resta 10 de 11, luego niega:

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

Aquí están los comentarios (convertidos en texto) de una de las bibliotecas para las que tuve que hacer esto. El código en sí mismo, por desgracia, está protegido por derechos de autor, pero es posible que pueda seleccionar la información suficiente para manejar las cuatro operaciones básicas. Suponga en lo siguiente que -a y -b representan números negativos y a y b son números cero o positivos.

Además , si los signos son diferentes, use la resta de la negación:

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

Para la resta , si los signos son diferentes, use la adición de la negación:

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

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

small - big becomes -(big - small)

La multiplicación usa matemáticas de nivel de entrada 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 se logra esto implica extraer cada uno de los dígitos de 32 uno por uno (hacia atrás) y luego usar agregar para calcular un valor que se agregará al resultado (inicialmente cero).

ShiftLeft operaciones ShiftLeft y ShiftRight se utilizan para multiplicar o dividir rápidamente un LongInt por el valor de ShiftRight (10 para matemáticas "reales"). En el ejemplo anterior, agregamos 475 a cero 2 veces (el último dígito de 32) para obtener 950 (resultado = 0 + 950 = 950).

Luego dejamos el cambio 475 para obtener 4750 y el desplazamiento a la derecha 32 para obtener 3. Agregue 4750 a cero 3 veces para obtener 14250 y luego sume el resultado de 950 para obtener 15200.

Cambie a la izquierda 4750 para obtener 47500, a la derecha a 3 para obtener 0. Como el desplazamiento a la derecha 32 ahora es cero, hemos terminado y, de hecho, 475 x 32 es igual a 15200.

La división también es complicada pero se basa en la aritmética temprana (el método "gazinta" para "entrar"). 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 variable de reducción (inicialmente cero) para reducir los segmentos de 12345 uno a la vez hasta que sea mayor o igual a 27.

Luego simplemente restamos 27 de eso hasta que llegamos a menos de 27; el número de restas se agrega al segmento en la línea superior.

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

Tenga en cuenta que estos son algoritmos bastante básicos. Hay formas mucho mejores de hacer aritmética compleja si sus números van a ser particularmente grandes. Puede buscar algo así como la Biblioteca de Aritmética de Precisión Múltiple de GNU : es sustancialmente mejor y más rápido que mis propias bibliotecas.

Tiene el desafortunado error ya que simplemente saldrá si se queda sin memoria (un error bastante fatal para una biblioteca de propósito general en mi opinión) pero, si se puede mirar más allá, es bastante bueno en lo que hace.

Si no puede usarlo por razones de licencia (o porque no desea que su aplicación salga sin motivo aparente), al menos podría obtener los algoritmos de allí para integrarlos en su propio código.

También encontré que los cuerpos en MPIR (una bifurcación de GMP) son más susceptibles a las discusiones sobre cambios potenciales, parecen un grupo más amigable con los desarrolladores.