División de números grandes

Necesito algún algoritmo de división que pueda manejar enteros grandes (128 bits). Ya he preguntado cómo hacerlo a través de operadores de cambio de bit. Sin embargo, mi aplicación actual parece pedir un mejor enfoqueDivisión de números grandes

Básicamente, almacenar números como dos long long unsigned int 's en el formato

A * 2^64 + B con B < 2^64.

Este número es divisible por 24 y quiero dividirlo por 24.

Mi enfoque actual es transformarla como

A * 2^64 + B  A    B 
-------------- = ---- * 2^64 + ---- 
     24   24   24 

      A    A mod 24     B   B mod 24 
= floor(----) * 2^64 + ---------- * 2^64 + floor(----) + ---------- 
      24    24.0      24   24.0

Sin embargo, esto está libre de errores.

(Tenga en cuenta que es A/24 baja y que es modA % 24. Las divisiones normales se almacenan en long double, los números enteros se almacenan en long long unsigned int.

Desde 24 es igual a 11000 en binario, el segundo sumando no debería cambiar algo en el rango del cuarto summand ya que se desplaza 64 bits hacia la izquierda.

Entonces, si A * 2^64 + B es divisible por 24, y B no lo es, muestra fácilmente que se produce un error ya que devuelve algunos no integrales número

¿Cuál es el error en mi implementación?

Fuente

2009-11-27 Etan

¿Cuál fue el problema con el enfoque de cambio de bit? –

parece exagerado cuando ya puede dividir el int64 – Etan

La manera más fácil que puedo pensar para hacer esto es tratar los números de 128 bits como cuatro de 32 bits números:

A_B_C_D = A*2^96 + B*2^64 + C*2^32 + D

y luego hacer una división larga por 24:

E = A/24 (with remainder Q) 
F = Q_B/24 (with remainder R) 
G = R_C/24 (with remainder S) 
H = S_D/24 (with remainder T)

Cuando el medio X*2^32 + YX_Y. Entonces la respuesta es E_F_G_H con el resto T. En cualquier punto, solo necesitas dividir los números de 64 bits, por lo que esto debería ser posible solo con operaciones enteras.

Fuente

2009-11-27 13:12:09 interjay

No impide que su algoritmo funcione en absoluto, pero F, G y H pueden ser mayores de 2^32. Tuve dificultades para conciliar eso con el hecho de que la notación 'E_F_G_H' se parece a la concatenación, pero una vez que se entiende esto, es un algoritmo muy bueno. –

En realidad, F, G y H serán menores que 2^32, porque Q, R y S son todos menores que 24. Entonces la notación E_F_G_H * es * concatenación. – interjay

¡Correcto! Olvidé mi división de lápiz y papel ... Recordé que había una parte de adivinanzas desagradable, pero ahí es cuando el divisor tiene demasiados dígitos. Siempre que el divisor en sí sea lo suficientemente corto como para caer dentro del rango para el cual funciona la división primitiva (como es el caso aquí), nunca hay necesidad de adivinar cuando se aplica el algoritmo de división de lápiz y papel. Perdón por la confusion. –

No debe utilizar long double para sus "divisiones normales", sino enteros allí también. long double no tiene suficientes cifras significativas para obtener la respuesta correcta (y de todos modos el punto es hacer esto con operaciones enteras, ¿correcto?).

Fuente

2009-11-27 12:31:39

; el objetivo es simplemente dividir un int de 128 bits por 24, lo que da como resultado un error épico en este momento. Long double tiene 64 bit de mantisa, por lo que no debería ser un problema. o lo hace? – Etan

Etan debería haber vinculado a su pregunta original. Parece que el objetivo no es hacerlo con números enteros sino hacerlo en absoluto. Además, 'long double' puede ser tan pequeño como un doble de 64 bits, pero también puede ser más grande (digamos un doble extendido de 10 bytes, pero nada en absoluto, realmente ... IEEE 754 es principalmente paramétrico con respecto al tamaño de los bits) Por lo tanto * podría * posiblemente tener la precisión necesaria (no digo que sea una buena idea usar cálculos de coma flotante para algo tan fácil como la aritmética de enteros de 128 bits). –

¿Cómo dividirlo sin el doble largo? – Etan

Dado que 24 es igual a 11000 en binario, el segundo summand no debe cambiar algo en el rango del cuarto summand ya que se desplaza 64 bits hacia la izquierda.

Su fórmula está escrita en números reales. (Un mod 24)/24 puede tener un número arbitrario de decimales (1/24 es por ejemplo 0.041666666 ...) y por lo tanto puede interferir con el cuarto término en su descomposición, incluso una vez multiplicado por 2^64.

La propiedad de que Y * 2^64 no interfiere con los dígitos binarios de menor peso en una adición solo funciona cuando Y es un número entero.

Fuente

2009-11-27 12:32:32

Interfiere en decimales ya que no puede escribirlos exactamente allí. En binario, tiene una implementación acotada ya que 1/24 se puede escribir en una cantidad final de dígitos. – Etan

@Etan ¿Realmente? ¿Cuántos dígitos se necesitan para representar 1/24 exactamente en binario, entonces? (Si esa es una pregunta demasiado difícil, comience con la cantidad de dígitos binarios que se necesitan para representar exactamente 1/3) –

1/24 = 0.00001010101010101 binarios ... la secuencia continúa para siempre. – dave4420

No.

Ve a buscar una biblioteca para hacer esto: estarás increíblemente agradecido de que hayas elegido para depurar errores extraños.

Fragmentos.org tenía una biblioteca C/C++ BigInt en su sitio hace un tiempo, Google también presentó lo siguiente: http://mattmccutchen.net/bigint/

Fuente

2009-11-27 12:49:04

Tengo que hacerlo manualmente, ya que es para un problema ACC ICPC. – Etan

¿Podría posiblemente resolverse con multiplicación inversa? Lo primero a destacar es que 24 == 8 * 3 por lo que el resultado de

a/24 == (a >> 3)/3

Vamos x = (a >> 3) entonces el resultado de la división es 8 * (x/3). Ahora queda encontrar el valor de x/3.

La aritmética modular establece que existe un número n tal que n * 3 == 1 (mod 2^128). Esto da:

x/3 = (x * n)/(n * 3) = x * n

Queda por encontrar la constante n. Hay una explicación sobre cómo hacer esto en wikipedia. También deberá implementar la funcionalidad para multiplicar a números de 128 bits.

Espero que esto ayude.

/A.B.

Fuente

2009-11-27 13:45:46

Respuesta

Cuestiones relacionadas