Arithmétique à précision arbitraire Explication

Question

J'essaie d'apprendre le C et je me suis heurté à l'impossibilité de travailler avec de VRAIS grands nombres (c'est-à-dire 100 chiffres, 1000 chiffres, etc.). Je sais qu'il existe des bibliothèques pour faire cela, mais je veux essayer de l'implémenter moi-même.

Je veux juste savoir si quelqu'un a ou peut fournir une explication très détaillée et simplifiée de l'arithmétique de précision arbitraire.

Answer 1

Tout est une question de stockage adéquat et d'algorithmes permettant de traiter les nombres comme des parties plus petites. Supposons que vous ayez un compilateur dans lequel une valeur de int ne peut être que de 0 à 99 et vous voulez gérer les nombres jusqu'à 999999 (nous ne nous occuperons ici que des nombres positifs pour rester simple).

Vous faites cela en donnant à chaque numéro trois int et en utilisant les mêmes règles que vous (auriez dû) apprendre à l'école primaire pour l'addition, la soustraction et les autres opérations de base.

Dans une bibliothèque à précision arbitraire, il n'y a pas de limite fixe au nombre de types de base utilisés pour représenter nos nombres, juste ce que la mémoire peut contenir.

Addition par exemple : 123456 + 78 :

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

Travailler à partir de l'extrémité la moins significative :

• report initial = 0.
• 56 + 78 + 0 report = 134 = 34 avec 1 report
• 34 + 00 + 1 retenue = 35 = 35 avec 0 retenue
• 12 + 00 + 0 report = 12 = 12 avec 0 report

C'est, en fait, la façon dont l'addition fonctionne généralement au niveau des bits dans votre CPU.

La soustraction est similaire (en utilisant la soustraction du type de base et l'emprunt au lieu de la retenue), la multiplication peut être faite avec des additions répétées (très lente) ou des produits croisés (plus rapide) et la division est plus délicate mais peut être faite par décalage et soustraction des nombres impliqués (la division longue que vous auriez apprise étant enfant).

En fait, j'ai écrit des bibliothèques pour faire ce genre de choses en utilisant les puissances maximales de dix qui peuvent tenir dans un entier lorsqu'il est élevé au carré (pour éviter un débordement lors de la multiplication de deux int ensemble, comme par exemple une carte de 16 bits int étant limité à 0 à 99 pour générer 9 801 (<32 768) au carré, ou 32 bits. int en utilisant de 0 à 9 999 pour générer 99 980 001 (<2 147 483 648)), ce qui a grandement facilité les algorithmes.

Quelques astuces dont il faut se méfier.

1/ Lorsque vous additionnez ou multipliez des nombres, préallouez l'espace maximum nécessaire, puis réduisez-le plus tard si vous trouvez que c'est trop. Par exemple, l'addition de deux nombres de 100 "chiffres" (où le chiffre est un int ) ne vous donneront jamais plus de 101 chiffres. La multiplication d'un nombre à 12 chiffres par un nombre à 3 chiffres ne donnera jamais plus de 15 chiffres (additionnez les chiffres).

2/ Pour plus de rapidité, normalisez (réduisez le stockage requis pour) les nombres seulement si c'est absolument nécessaire - ma bibliothèque a fait en sorte que cela soit un appel séparé pour que l'utilisateur puisse décider entre les préoccupations de vitesse et de stockage.

3/ L'addition d'un nombre positif et négatif est une soustraction, et la soustraction d'un nombre négatif est identique à l'addition du nombre positif équivalent. Vous pouvez économiser une bonne partie du code en faisant en sorte que les méthodes d'addition et de soustraction s'appellent mutuellement après avoir ajusté les signes.

4/ Évitez de soustraire les grands nombres des petits car vous vous retrouvez invariablement avec des nombres du type :

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

Au lieu de cela, soustrayez 10 de 11, puis niez-le :

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

Voici les commentaires (transformés en texte) d'une des bibliothèques pour laquelle j'ai dû faire cela. Le code lui-même est, malheureusement, protégé par le droit d'auteur, mais vous pourrez peut-être en tirer suffisamment d'informations pour effectuer les quatre opérations de base. Supposons dans ce qui suit que -a y -b représentent des nombres négatifs et a y b sont des nombres nuls ou positifs.

Pour ajout si les signes sont différents, utiliser la soustraction de la négation :

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

Pour soustraction si les signes sont différents, utiliser l'addition de la négation :

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

Une manipulation spéciale est également nécessaire pour s'assurer que l'on soustrait les petits nombres des grands :

small - big becomes -(big - small)

Multiplication utilise les mathématiques de base comme suit :

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

Pour ce faire, il faut extraire chacun des chiffres de 32 un par un (à l'envers) puis utiliser add pour calculer une valeur à ajouter au résultat (initialement zéro).

ShiftLeft y ShiftRight Les opérations sont utilisées pour multiplier ou diviser rapidement un LongInt par la valeur de l'enveloppe (10 pour les "vraies" mathématiques). Dans l'exemple ci-dessus, nous ajoutons 2 fois 475 à zéro (le dernier chiffre de 32) pour obtenir 950 (résultat = 0 + 950 = 950).

Ensuite, nous décalons à gauche 475 pour obtenir 4750 et décalons à droite 32 pour obtenir 3. Ajoutez 4750 à zéro 3 fois pour obtenir 14250 puis ajoutez au résultat de 950 pour obtenir 15200.

Décalez à gauche 4750 pour obtenir 47500, décalez à droite 3 pour obtenir 0. Puisque le 32 décalé à droite est maintenant zéro, nous avons terminé et, en fait, 475 x 32 est égal à 15200.

Division est également délicate, mais elle est basée sur l'arithmétique ancienne (la méthode "gazinta" pour "entre dans"). Considérons la division longue suivante pour 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.

Par conséquent, 12345 / 27 es 457 avec reste 6 . Vérifier :

  457 x 27 + 6
= 12339    + 6
= 12345

Ceci est mis en œuvre en utilisant une variable de réduction (initialement zéro) pour réduire les segments de 12345 un par un jusqu'à ce qu'ils soient supérieurs ou égaux à 27.

Ensuite, il suffit de soustraire 27 de ce chiffre jusqu'à ce que nous soyons en dessous de 27 - le nombre de soustractions est le segment ajouté à la ligne supérieure.

Lorsqu'il n'y a plus de segments à abattre, nous avons notre résultat.

---

Gardez à l'esprit que ce sont des algorithmes assez basiques. Il existe de bien meilleures façons de faire de l'arithmétique complexe si vos nombres doivent être particulièrement grands. Vous pouvez envisager quelque chose comme Bibliothèque arithmétique de précision multiple GNU - il est nettement meilleur et plus rapide que mes propres bibliothèques.

Elle a un défaut plutôt malheureux, à savoir qu'elle s'arrêtera simplement si elle manque de mémoire (un défaut plutôt fatal pour une bibliothèque d'usage général à mon avis) mais, si vous pouvez passer outre, elle est plutôt bonne dans ce qu'elle fait.

Si vous ne pouvez pas l'utiliser pour des raisons de licence (ou parce que vous ne voulez pas que votre application s'arrête sans raison apparente), vous pouvez au moins y récupérer les algorithmes pour les intégrer dans votre propre code.

J'ai aussi trouvé que les gars de l'équipe de MPIR (un fork de GMP) sont plus ouverts aux discussions sur les changements potentiels - ils semblent être plus favorables aux développeurs.

Answer 2

Si réinventer la roue est extrêmement bon pour votre édification personnelle et votre apprentissage, c'est aussi une tâche extrêmement lourde. Je ne veux pas vous dissuader, car il s'agit d'un exercice important que j'ai moi-même réalisé, mais vous devez être conscient qu'il y a des problèmes subtils et complexes à l'œuvre que les paquets plus importants abordent.

Par exemple, la multiplication. Naïvement, on peut penser à la méthode de l'écolier, c'est-à-dire écrire un chiffre au-dessus de l'autre, puis faire une multiplication longue comme on l'a appris à l'école :

      123
    x  34
    -----
      492
+    3690
---------
     4182

mais cette méthode est extrêmement lente (O(n^2), n étant le nombre de chiffres). Au lieu de cela, les paquets bignum modernes utilisent soit une transformée de Fourier discrète, soit une transformée numérique pour transformer cette opération en une opération essentiellement O(n ln(n)).

Et ceci est juste pour les entiers. Lorsque vous entrez dans des fonctions plus complexes sur un type de représentation réelle d'un nombre (log, sqrt, exp, etc.), les choses deviennent encore plus compliquées.

Si vous souhaitez obtenir des informations théoriques, je vous recommande vivement de lire le premier chapitre du livre de Yap, "Problèmes fondamentaux de l'algèbre algorithmique" . Comme déjà mentionné, la bibliothèque gmp bignum est une excellente bibliothèque. Pour les nombres réels, j'ai utilisé MPFR et l'ont aimé.

Answer 3

Ne réinventez pas la roue : elle pourrait s'avérer carrée !

Utilisez une bibliothèque tierce, telle que GNU MP qui a fait ses preuves.

Answer 4

Vous le faites essentiellement de la même manière que vous le faites avec un crayon et du papier...

• Le nombre doit être représenté dans un tampon (tableau) capable de prendre une taille arbitraire (ce qui signifie que l'on utilise malloc y realloc ) au besoin
• vous implémentez l'arithmétique de base autant que possible en utilisant des structures prises en charge par le langage, et vous vous occupez manuellement des reports et du déplacement du point radix
• vous parcourez les textes d'analyse numérique pour trouver des arguments efficaces pour traiter des fonctions plus complexes
• vous ne mettez en œuvre que ce dont vous avez besoin.

En général, vous utiliserez comme unité de base de calcul

• octets contenant 0-99 ou 0-255
• Mots de 16 bits contenant soit 0-9999 soit 0--65536.
• Des mots de 32 bits contenant...
• ...

comme le dicte votre architecture.

Le choix de la base binaire ou décimale dépend de vos souhaits en matière d'efficacité de l'espace, de lisibilité par l'homme et de la présence ou non d'un support mathématique BCD (Binary Coded Decimal) sur votre puce.

Answer 5

Vous pouvez le faire avec le niveau de mathématiques du lycée. Bien que des algorithmes plus avancés soient utilisés dans la réalité. Par exemple, pour additionner deux nombres de 1024 octets :

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;
}

Le résultat devra être plus important en one place en cas d'addition pour tenir compte des valeurs maximales. Regardez ceci :

9
   +
9
----
18

TTMath est une grande bibliothèque si vous voulez apprendre. Elle est construite en utilisant C++. L'exemple ci-dessus était stupide, mais c'est la façon dont l'addition et la soustraction sont effectuées en général !

Une bonne référence sur le sujet est Complexité computationnelle des opérations mathématiques . Il vous indique l'espace nécessaire pour chaque opération que vous souhaitez mettre en œuvre. Par exemple, si vous avez deux N-digit les chiffres, alors vous avez besoin 2N digits pour stocker le résultat de la multiplication.

Comme Mitch Cela dit, ce n'est de loin pas une tâche facile à mettre en œuvre ! Je vous recommande de jeter un coup d'œil à TTMath si vous connaissez le C++.