Arithmétique de précision arbitraire Explication

StackOverflow https://stackoverflow.com/questions/1218149

  •  10-07-2019
  •  | 
  •  

Question

J'essaie d'apprendre le C et je suis incapable de travailler avec des nombres VRAIMENT grands (100 chiffres, 1 000 chiffres, etc.). Je suis conscient qu'il existe des bibliothèques pour le faire, mais je veux essayer de le mettre en œuvre moi-même.

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

Était-ce utile?

La solution

Tout est une question de stockage adéquat et d'algorithmes pour traiter les nombres comme de plus petites pièces. Supposons que vous avez un compilateur dans lequel un int ne peut être compris entre 0 et 99 et que vous souhaitez gérer des nombres allant jusqu'à 999999 (nous nous préoccuperons uniquement des nombres positifs pour rester simple).

Vous faites cela en donnant à chaque numéro trois 123456 + 78 s et en utilisant les mêmes règles que vous devriez (avoir) appris à l’école primaire pour l’addition, la soustraction et les autres opérations de base.

Dans une bibliothèque de 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.

Ajout par exemple: -a: 

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

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

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

C’est en fait la manière dont l’addition fonctionne généralement au niveau des bits de votre CPU.

La soustraction est similaire (utiliser la soustraction du type de base et emprunter au lieu de reporter), la multiplication peut être effectuée 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 effectuée par décalage et soustraction des nombres impliqués (la longue division que vous auriez appris en tant qu'enfant).

J'ai en fait écrit des bibliothèques pour faire ce genre de choses en utilisant les puissances maximales de dix qui peuvent être contenues dans un entier lorsqu'il est carré (pour éviter les débordements lors de la multiplication de deux -b s ensemble, tel qu'un 16 bits < => étant limité à 0 à 99 pour générer 9 801 (< 32,768) au carré, ou à 32 bits a en utilisant 0 à 9 999 pour générer 99 980 001 (< 2 147 483 648)), ce qui a grandement facilité les algorithmes .

Quelques astuces à surveiller.

1 / Lorsque vous ajoutez ou multipliez des nombres, pré-allouez le maximum d’espace puis réduisez-le ultérieurement si vous trouvez que c’est trop. Par exemple, ajouter deux 100 - & Quot; digit & Quot; (où digit est b), les nombres ne vous donneront jamais plus de 101 chiffres. Multiplier un nombre de 12 chiffres par un nombre de 3 chiffres ne générera jamais plus de 15 chiffres (additionnez les chiffres).

2 / Pour plus de rapidité, normalisez (réduisez le stockage requis pour) les numéros uniquement si cela est absolument nécessaire - ma bibliothèque avait cet appel en tant qu'appel séparé afin que l'utilisateur puisse choisir entre les problèmes de vitesse et de stockage.

3 / L'addition d'un nombre positif et négatif équivaut à une soustraction, et soustraire un nombre négatif équivaut à ajouter le positif équivalent. Vous pouvez économiser un peu de code en faisant en sorte que les méthodes d’addition et de soustraction s’appellent après l’ajustement des signes.

4 / Évitez de soustraire les gros nombres des petits, car vous finissez invariablement avec des nombres tels que: 

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

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

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

Voici les commentaires (convertis en texte) de l’une des bibliothèques pour lesquelles je devais le faire. Malheureusement, le code lui-même est protégé par des droits d'auteur, mais vous pourrez peut-être choisir suffisamment d'informations pour gérer les quatre opérations de base. Supposons par la suite que ShiftLeft et ShiftRight représentent des nombres négatifs et que LongInt et 12345 / 27 sont des nombres égaux à zéro ou positifs.

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

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

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

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

Manipulation spéciale pour nous assurer de soustraire 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 y parvenir, il faut extraire chacun des chiffres de 32 un par un (en arrière), puis utiliser add pour calculer une valeur à ajouter au résultat (initialement zéro).

Les opérations

457 et 6 permettent de multiplier ou de diviser rapidement un <=> par la valeur de bouclage (10 pour les & "vrais &"; mathématiques). Dans l'exemple ci-dessus, nous ajoutons 475 à zéro 2 fois (le dernier chiffre de 32) pour obtenir 950 (résultat = 0 + 950 =950).

Ensuite, nous avons quitté l'équipe 475 pour obtenir 4750 et l'équipe de droite 32 pour obtenir 3. Ajouter 4750 à zéro 3 fois pour obtenir 14250 puis ajouter au résultat de 950 pour obtenir 15 200.

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

La

Division est également délicate, mais repose sur une arithmétique précoce (la méthode & "; gazinta &" pour & "passe en &";). Considérons la longue division suivante pour <=>: 

       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.

Donc <=> est <=> avec le reste <=>. Vérifiez: 

  457 x 27 + 6
= 12339    + 6
= 12345

Ceci est mis en œuvre en utilisant une variable draw-down (initialement zéro) pour réduire les segments de 12345 un par un jusqu'à ce qu'il soit supérieur ou égal à 27.

Nous en déduisons simplement 27 jusqu'à ce que nous descendions au-dessous de 27 - le nombre de soustractions est le segment ajouté à la ligne supérieure.

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

Gardez à l’esprit que ce sont des algorithmes assez basiques. Il existe de bien meilleurs moyens de faire de l’arithmétique complexe si vos chiffres sont particulièrement volumineux. Vous pouvez rechercher quelque chose comme la bibliothèque arithmétique à précision multiple de GNU - elle est bien meilleure et plus rapide que mes propres bibliothèques.

Il y a un problème assez regrettable dans le sens où il disparaîtra simplement s'il manque de mémoire (un défaut plutôt fatal pour une bibliothèque à usage général, à mon avis), mais si vous pouvez regarder au-delà, c'est plutôt bon à quoi c'est le cas.

Si vous ne pouvez pas l'utiliser pour des raisons de licence (ou parce que vous ne voulez pas que votre application se ferme sans raison apparente), vous pouvez au moins obtenir les algorithmes à partir de là pour l'intégration dans votre propre code.

J'ai également constaté que les MPIR (une fourchette de BPF) sont plus susceptibles de discussions sur les modifications potentielles - elles semblent plus conviviales pour les développeurs.

Autres conseils

Bien que réinventer la roue soit extrêmement bénéfique pour votre éducation et votre apprentissage personnels, c’est également une tâche extrêmement lourde. Je ne veux pas vous dissuader car c’est un exercice important et que j’ai fait moi-même, mais vous devez savoir qu’il existe au travail des problèmes subtils et complexes auxquels des paquets plus volumineux s’attaquent.

Par exemple, multiplication. Naïvement, vous pourriez penser à la méthode de «l’écolier», c’est-à-dire écrire un nombre au-dessus de l’autre, puis multiplier à long comme vous l’avez appris à l’école. exemple: 

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

mais cette méthode est extrêmement lente (O (n ^ 2), n étant le nombre de chiffres). Les paquets bignum modernes utilisent plutôt une transformation de Fourier discrète ou une transformation Numeric pour la transformer en une opération essentiellement O (n ln (n)).

Et ceci ne concerne que les entiers. Lorsque vous entrez dans des fonctions plus complexes sur un type de représentation réelle du nombre (log, sqrt, exp, etc.), les choses deviennent encore plus compliquées.

Si vous souhaitez des connaissances 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 vrais nombres, j’ai utilisé mpfr et je l’ai aimé.

Ne réinventez pas la roue: elle pourrait se révéler carrée!

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

Vous le faites fondamentalement 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 utiliser malloc et realloc) selon les besoins
  • vous implémentez autant que possible l'arithmétique de base à l'aide de structures prises en charge par le langage, et gérez les transferts et le déplacement manuel du point-radix
  • vous parcourez des textes d'analyse numériques pour trouver des arguments efficaces vous permettant de traiter par une fonction plus complexe
  • vous ne mettez en œuvre que ce dont vous avez besoin.

Typiquement, vous utiliserez comme unité de base du calcul

  • octets contenant avec 0-99 ou 0-255
  • Les mots de 16 bits contenant flétrir 0-9999 ou 0--65536
  • mots de 32 bits contenant ...
  • ...

selon votre architecture.

Le choix de la base binaire ou décimale dépend de vos souhaits: efficacité maximale de l’espace, lisibilité humaine et absence de prise en charge mathématique en décimal codé binaire (BCD) sur votre puce.

Vous pouvez le faire avec le niveau de mathématiques au lycée. Bien que des algorithmes plus avancés soient utilisés dans la réalité. Donc, par exemple, pour ajouter 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 grand de one place en cas d'addition pour prendre en charge les valeurs maximales. Regardez ceci: 

9
   +
9
----
18

TTMath est une excellente bibliothèque si vous souhaitez apprendre. Il est construit en C ++. L’exemple ci-dessus était stupide, mais c’est comme ça que l’addition et la soustraction sont faites en général!

Une complexité des opérations mathématiques est une bonne référence en la matière. Il vous indique combien d’espace est requis pour chaque opération que vous souhaitez implémenter. Par exemple, si vous avez deux N-digit nombres, vous avez besoin de 2N digits pour stocker le résultat de la multiplication.

Comme le dit Mitch , ce n’est de loin pas une tâche facile à mettre en œuvre! Je vous recommande de regarder TTMath si vous connaissez le C ++.

L’une des références ultimes (IMHO) est le volume II du TAOCP de Knuth. Il explique de nombreux algorithmes permettant de représenter des nombres et des opérations arithmétiques sur ces représentations. 

@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},
}

En supposant que vous souhaitiez écrire vous-même un gros code entier, cette opération peut être étonnamment simple à faire. Parlez comme quelqu'un qui l'a fait récemment (bien que dans MATLAB.) Voici quelques astuces que j'ai utilisées:

  • J'ai enregistré chaque chiffre décimal individuel sous forme de nombre double. Cela simplifie de nombreuses opérations, en particulier la sortie. Bien que cela prenne plus de mémoire que vous ne le souhaiteriez, la mémoire est bon marché ici et la multiplication est très efficace si vous parvenez à transformer deux vecteurs de manière efficace. Alternativement, vous pouvez stocker plusieurs chiffres décimaux dans un double, mais attention, cette convolution pour effectuer la multiplication peut causer des problèmes numériques sur de très grands nombres.

  • Stocker un bit de signe séparément.

  • L'addition de deux nombres consiste principalement à ajouter les chiffres, puis à rechercher un report à chaque étape.

  • Il est préférable de multiplier une paire de nombres sous forme de convolution suivie d'une étape de retenue, du moins si vous avez un code de convolution rapide au robinet.

  • Même lorsque vous stockez les nombres sous forme de chaîne de chiffres décimaux individuels, vous pouvez effectuer une division (ainsi que des opérations mod / rem) pour obtenir environ 13 chiffres décimaux à la fois dans le résultat. C'est beaucoup plus efficace qu'une division qui ne fonctionne qu'avec 1 chiffre décimal à la fois.

  • Pour calculer une puissance entière d'un entier, calculez la représentation binaire de l'exposant. Utilisez ensuite des opérations de quadrillage répétées pour calculer les puissances nécessaires.

  • De nombreuses opérations (factorisation, tests de primalité, etc.) bénéficieront d'une opération powermod. En d’autres termes, lorsque vous calculez mod (a ^ p, N), réduisez le résultat mod N à chaque étape de l’exponentiation où p a été exprimé sous une forme binaire. Ne calculez pas d'abord un ^ p, puis essayez de le réduire mod N.

Voici un exemple simple (naïf) que j'ai utilisé en PHP.

J'ai implémenté " Ajouter " et " Multiply " et utilisé que pour un exemple d'exposant.

http://adevsoft.com/simple-php -arbitrary-precision-integer-big-num-example /

Capture de code 

// 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);
}
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top