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.Aritmética de precisión arbitraria Explicación
Solo quiero saber si alguien tiene o puede proporcionar una explicación muy detallada y simplificada de la aritmética de precisión arbitraria.
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 int solo puede ser de 0 a 99 y desea manejar números de hasta 999999 (solo nos preocuparemos por los números positivos aquí para mantenerlo simple).
Lo haces dando el número tres int sy usando las mismas reglas que (deberías haber) aprendido en la escuela primaria para sumar, restar y otras operaciones básicas.
En una biblioteca de precisión arbitraria, no existe un límite fijo en la cantidad de tipos de base utilizados para representar nuestros números, simplemente cualquier memoria que pueda contener.
adición por ejemplo: 123456 + 78:
12 34 56
78
-- -- --
12 35 34
Trabajando desde el extremo menos significativo:
Esto es, de hecho, cómo la adición generalmente funciona en el nivel de bit dentro de su CPU.
La resta es similar (restando el tipo base y tomando prestado en lugar de acarreo), la multiplicación se puede hacer con adiciones repetidas (muy lento) o cruzados (más rápido) y la división es más complicada pero se puede hacer resta de los números involucrados (la división larga que habría aprendido de niño).
De hecho, he escrito bibliotecas para hacer este tipo de cosas usando las potencias máximas de diez que se pueden encajan en un número entero al cuadrado (para evitar el desbordamiento cuando se multiplican dos int s juntos, como un int ser de 16 bits limitado a 0 a través de 99 para generar 9801 (< 32768) cuando al cuadrado, o de 32 bits int usando de 0 a 9999 para generar 99,980,001 (< 2147483648)) que facilitó en gran medida los algoritmos.
Algunos trucos a tener en cuenta.
1/Al agregar o multiplicar números, antes de asignar el espacio máximo necesario entonces reducir más adelante, si usted encuentra que es demasiado. Por ejemplo, agregar dos números de 100 dígitos (donde el dígito es un 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) los números solo si es absolutamente necesario - mi biblioteca lo tuvo como una llamada separada para que el usuario pueda decidir entre la velocidad y el 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/Evitar restar números grandes de los pequeños ya que invariablemente termina con números como:
10
11-
-- -- -- --
99 99 99 99 (and you still have a borrow).
En cambio, restar 10 del 11, luego negarlo:
11
10-
--
1 (then negate to get -1).
Éstos son el 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.
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 un manejo especial para asegurar que estamos restando números pequeños de grandes:
small - big becomes -(big - small)
Multiplicación utiliza 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 esto se logra consiste en extraer cada uno de los dígitos de 32 uno a la vez (hacia atrás) a continuación, utilizando añadir a calcular una valor que se agregará al resultado (inicialmente cero).
ShiftLeft y ShiftRight operaciones se utilizan para multiplicar o dividir rápidamente un LongInt por el valor de ajuste (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 desplazamiento a la izquierda para obtener 475 4750 y desplazamiento a la derecha para obtener 32 3. Agregar 4750 a cero 3 veces para obtener 14.250 a continuación, añadir a consecuencia de 950 para obtener 15200.
desviación a la izquierda para llegar 4750 47500, desplazamiento a la derecha 3 para obtener 0. Desde la derecha se movió 32 es ahora cero, hemos terminado y, de hecho, 475 x 32 es igual a 15200.
División también es difícil, pero basado en la aritmética temprana (el "gazinta "método para" entra en "). 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 es 12345/27457 con 6 resto. Verificar:
457 x 27 + 6
= 12339 + 6
= 12345
Esto se implementa mediante el uso de una variable de draw-down (inicialmente cero) para derribar los segmentos de 12345 de uno en uno hasta que es mayor o igual a 27.
Luego simplemente restamos 27 de eso hasta que llegamos por debajo de 27 - el número de restas se agrega al segmento en la línea superior.
Cuando no hay más segmentos que 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 como GNU Multiple Precision Arithmetic Library - 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 (una falla bastante fatal para una biblioteca de propósito general en mi opinión) pero, si se puede mirar más allá de eso, es bastante bueno en Que hace.
Si no puede usarlo por razones de licencia (o porque no desea que su aplicación simplemente salga sin motivo aparente), al menos puede obtener los algoritmos desde 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.
No reinvente la rueda: ¡podría ser cuadrada!
Utilice una biblioteca de terceros, como GNU MP, que ya ha sido probada.
Pero quiero reinventar la rueda por el bien de aprender. –
Si desea aprender C, yo fijaría su punto de mira un poco más abajo. La implementación de una biblioteca bignum no es trivial por todo tipo de razones sutiles que harán tropezar a un alumno –
Biblioteca de terceros: aceptada, pero GMP tiene problemas de licencia (LGPL, aunque efectivamente actúa como GPL ya que es un poco difícil hacer alto rendimiento matemática a través de una interfaz compatible con LGPL). –
Puedes hacerlo con el nivel de la escuela secundaria de las matemáticas. Aunque los algoritmos más avanzados se utilizan en la realidad. Así por ejemplo, para sumar 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;
}
resultado tendrá que ser más grande por one place en caso de que además de cuidar de los valores máximos. Mira esto:
9
+
9
----
18
TTMath es una gran biblioteca si desea 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 Computational complexity of mathematical operations. Le dice cuánto espacio se requiere para cada operación que desea implementar. Por ejemplo, si tiene dos números N-digit, necesita 2N digits para almacenar el resultado de la multiplicación.
Como Mitch dijo, ¡de lejos no es una tarea fácil de implementar! Te recomiendo que eches un vistazo a TTMath si conoces C++.
El uso de matrices se me ocurrió, pero estoy buscando algo aún más general. ¡Gracias por la respuesta! –
Hmm ... el nombre del que pregunta y el nombre de la biblioteca no pueden ser una coincidencia, ¿o sí? ;) –
¡LoL, no me di cuenta de eso! Ojalá TTMath fuera mío :) Por cierto, esta es una de mis preguntas sobre el tema: – AraK
Usted lo hace básicamente de la misma manera que se hace con lápiz y papel ...
malloc y realloc) según sea necesarioNormalmente se utilizará como unidad básica de la computación
según lo dictado por su arquitectura.
La elección de la base binaria o decimal depende de sus deseos de máxima eficiencia de espacio, legibilidad humana y la ausencia de soporte matemático decimal codificado en binario (BCD) en su chip.
Si bien 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 '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 solo es 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 obtener algunos antecedentes teóricos, le recomiendo leer el primer capítulo del libro de Yap, "Fundamental Problems of Algorithmic Algebra". Como ya se mencionó, la biblioteca gmp bignum es una excelente biblioteca. Para números reales, he usado mpfr y me ha gustado.
Me interesa la parte sobre "utilizar una transformada discreta de Fourier o una transformación numérica para convertir esto en una operación esencialmente O (n ln (n))". ¿Cómo funciona eso? Solo una referencia estaría bien :) – detly
@detly: la multiplicación polinomial es lo mismo que la convolución, debería ser fácil encontrar información sobre el uso de la FFT para realizar una convolución rápida. Cualquier sistema numérico es un polinomio, donde los dígitos son coeficientes y la base es la base. Por supuesto, deberá cuidar los acarreos para evitar exceder el rango de dígitos. –
Suponiendo que se desea escribir un código entero grande a sí mismo, esto puede ser sorprendentemente fácil de hacer, que se habla como alguien que lo hizo recientemente Aquí están algunos de los trucos que he utilizado (aunque en MATLAB.):
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 adición de dos números es principalmente una cuestión de sumar los dígitos, luego verifica que haya 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á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.
Si está almacenando dígitos individuales en lugar de base-10^9 o base-2^32 o algo similar, todas sus fantasías de convolución por multiplicación son simplemente un desperdicio. Big-O no tiene sentido cuando tu constante es ** tan ** malo ... –
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/
Código SNIP
// 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);
}
Una de las referencias finales (en mi humilde opinión) es de Knuth TAOCP Volumen II. 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},
}
Creo que cubriste "Solo quiero saber si alguien tiene o puede proporcionar una explicación muy detallada y simplificada de la aritmética de precisión arbitraria" MUY bien –
Una pregunta de seguimiento: ¿Es posible establecer/detectar transportes y desbordamientos? sin acceso a código de máquina? – SasQ