División de grandes números

Question

Necesito algún algoritmo de división que pueda manejar números enteros grandes (128 bits).Ya pregunté cómo hacerlo mediante operadores de desplazamiento de bits.Sin embargo, mi implementación actual parece requerir un mejor enfoque.

Básicamente, almaceno los números como dos long long unsigned intestá 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 transformarlo 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 tiene errores.

(Tenga en cuenta que el piso es A / 24 y eso mod es A % 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 sumando ya que se desplaza 64 bits hacia la izquierda.

Así que si A * 2 ^ 64 + B es divisible por 24 y B no lo es, muestra fácilmente que produce errores ya que devuelve algún número no entero.

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

Answer 1

La forma más fácil en que se me ocurre hacer esto es tratar los números de 128 bits como cuatro números de 32 bits:

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

Y luego haz 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)

Donde X_Y significa X*2^32 + Y. Entonces la respuesta es E_F_G_H con el resto T. En cualquier momento, solo necesita la división de números de 64 bits, por lo que esto debería ser posible solo con operaciones de enteros.

Answer 2

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

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

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

La aritmética modular indica 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 <=>. 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.

Answer 3

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

Answer 4

  

Dado que 24 es igual a 11000 en binario, el segundo sumando no debería cambiar algo en el rango del cuarto sumando ya que se desplaza 64 bits a 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.

Answer 5

No lo hagas

Ve a buscar una biblioteca para hacer estas cosas: estarás increíblemente agradecido de haber elegido al depurar errores extraños.

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