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

Pour une mise en œuvre simple, vous pouvez être intéressé par ce . Je le garde en signet car c'est un bon matériel de référence.

Answer 2

L'une des références ultimes (IMHO) est le TAOCP Volume II de Knuth. Il explique de nombreux algorithmes pour représenter les nombres et les 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},
}

Answer 3

En supposant que vous souhaitiez écrire vous-même un code pour les grands nombres entiers, cela peut être étonnamment simple à faire, dit quelqu'un qui l'a fait récemment (bien qu'en MATLAB.) Voici quelques-unes des astuces que j'ai utilisées :

• J'ai stocké chaque chiffre décimal individuel comme un nombre double. Cela simplifie de nombreuses opérations, notamment la sortie. Bien que cela prenne plus de place que vous ne le souhaiteriez, la mémoire est bon marché ici, et cela rend la multiplication très efficace si vous pouvez convoluer une paire de vecteurs efficacement. Alternativement, vous pouvez stocker plusieurs chiffres décimaux dans un double, mais attention alors à ce que la convolution pour faire la multiplication puisse causer des problèmes numériques sur de très grands nombres.

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

• L'addition de deux nombres consiste principalement à additionner les chiffres, puis à vérifier la présence d'une retenue à chaque étape.

• La multiplication d'une paire de nombres est mieux réalisée sous forme de convolution suivie d'une étape de report, du moins si vous disposez d'un code de convolution rapide.

• Même lorsque vous stockez les nombres sous la forme d'une chaîne de chiffres décimaux individuels, la division (ainsi que les opérations mod/rem) peut être effectuée pour obtenir environ 13 chiffres décimaux à la fois dans le résultat. C'est beaucoup plus efficace qu'une division qui ne fonctionne que sur un seul 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 répétées d'élévation au carré pour calculer les puissances nécessaires.

• De nombreuses opérations (factorisation, tests de primalité, etc.) bénéficieront d'une opération de powermod. C'est-à-dire que 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 a^p, puis essayez de le réduire mod N.

Answer 4

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

J'ai implémenté "Add" et "Multiply" et je les ai utilisés pour un exemple d'exposant.

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

Code snip

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