Division des grands nombres

Question

J'ai besoin d'un algorithme de division capable de gérer de grands entiers (128 bits). J'ai déjà demandé comment faire via des opérateurs de transfert de bits. Cependant, ma mise en œuvre actuelle semble demander une meilleure approche

En principe, je stocke les numéros sous forme de deux long long unsigned int sous la forme

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

Ce nombre est divisible par 24 et je souhaite le diviser par A / 24.

Mon approche actuelle consiste à le transformer comme suit

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

Cependant, c'est un buggy.

(Notez que floor est mod et que A % 24 est long double. Les divisions normales sont stockées dans 11000, les entiers sont stockés dans <=>.

Etant donné que <=> est égal à <=> en binaire, le deuxième résumé ne doit pas changer quelque chose dans la plage du quatrième, puisqu'il est décalé de 64 bits vers la gauche.

Ainsi, si <=> est divisible par 24 et que B ne l’est pas, cela indique facilement qu’il fait défaut, car il renvoie un nombre non entier.

Quelle est l'erreur dans ma mise en œuvre?

Answer 1

Pour ce faire, le moyen le plus simple consiste à traiter les nombres 128 bits en tant que quatre nombres 32 bits:

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

Et ensuite faire une longue division de 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)

Où X_Y signifie X*2^32 + Y. Ensuite, la réponse est E_F_G_H avec le reste T. À tout moment, vous n’avez besoin que de la division de nombres 64 bits. Cela ne devrait donc être possible qu’avec des opérations sur les entiers.

Answer 2

Cela pourrait-il éventuellement être résolu avec une multiplication inverse? La première chose à noter est que 24 == 8 * 3 donc le résultat de

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

Soit x = (a >> 3) alors le résultat de la division est 8 * (x / 3). Reste maintenant à trouver la valeur de x / 3.

L'arithmétique modulaire indique qu'il existe un nombre n tel que n * 3 == 1 (mod 2^128). Cela donne:

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

Il reste à trouver la constante <=>. wikipedia explique comment procéder. Vous devrez également implémenter des fonctionnalités pour multiplier à 128 bits.

J'espère que cela vous aidera.

/A.B.

Answer 3

Vous ne devriez pas utiliser long double pour vos " divisions normales " mais entiers là aussi. <=> ne dispose pas d'assez de chiffres significatifs pour bien répondre (et de toute façon, le but est de le faire avec des opérations sur les entiers, n'est-ce pas?).

Answer 4

  

Etant donné que 24 est égal à 11 000 en binaire, le deuxième sommet ne devrait pas changer quelque chose dans la plage du quatrième sommet puisqu'il est décalé de 64 bits vers la gauche.

Votre formule est écrite en nombres réels. (Un mod 24) / 24 peut avoir un nombre arbitraire de décimales (1/24 est par exemple 0,041666666 ...) et peut donc interférer avec le quatrième terme de votre décomposition, même une fois multiplié par 2 ^ 64.

La propriété selon laquelle Y * 2 ^ 64 n'interfère pas avec les chiffres binaires de poids plus faible dans une addition ne fonctionne que lorsque Y est un entier.

Answer 5

Ne pas.

Allez chercher une bibliothèque pour faire ce genre de choses - vous serez incroyablement reconnaissant de l'avoir choisi lors du débogage d'erreurs bizarres.

Snippets.org avait une bibliothèque C / C ++ BigInt sur son site il y a quelque temps, Google a également indiqué ce qui suit: http://mattmccutchen.net/bigint/