Comment implémenter big int en C ++

Question

Je voudrais implémenter une grande classe int en C ++ en tant qu'exercice de programmation & # 8212; une classe capable de gérer des nombres plus grands qu'une longue. Je sais qu'il existe déjà plusieurs implémentations open source, mais j'aimerais écrire la mienne. J'essaie d'avoir une idée de la bonne approche.

Je comprends que la stratégie générale consiste à obtenir le nombre sous forme de chaîne, puis à le diviser en nombres plus petits (un seul chiffre par exemple) et à les placer dans un tableau. À ce stade, il devrait être relativement simple de mettre en œuvre les différents opérateurs de comparaison. Ma principale préoccupation est de savoir comment je mettrais en œuvre des choses comme l'addition et la multiplication.

Je recherche une approche générale et des conseils par opposition au code de travail réel.

Answer 1

Éléments à prendre en compte pour une grande classe d'int:

1. Opérateurs mathématiques: +, -, /, *,% N'oubliez pas que votre classe peut être de chaque côté de la opérateur, que les opérateurs peuvent être enchaîné, que l'un des opérandes pourrait être un int, float, double, etc.

2. Opérateurs d'E / S: > > ;, < < C'est où vous savez comment bien créez votre classe à partir d'une entrée utilisateur et comment la formater pour la sortie également.

3. Conversions / distributions: comprendre quels types / classes votre big int la classe doit être convertible en, et comment gérer correctement le conversion. Une liste rapide serait inclure double et float, et peut include int (avec les limites appropriées vérification) et complexe (à supposer peut gérer la plage).

Answer 2

Un défi amusant. :)

Je suppose que vous voulez des entiers de longueur arbitraire. Je suggère l'approche suivante:

Considérons la nature binaire du type de données & "int &"; Pensez à utiliser des opérations binaires simples pour émuler ce que les circuits de votre CPU font lorsqu'ils ajoutent des éléments. Au cas où cela vous intéresserait plus en profondeur, pensez à lire cet article de Wikipédia sur les demi-ajouteurs et les ajouts complets . Vous ferez quelque chose de similaire, mais vous pouvez descendre à un niveau aussi bas - mais étant paresseux, je pensais que je renoncerais à une solution encore plus simple.

Mais avant d'entrer dans les détails algorithmiques sur l'ajout, la soustraction, la multiplication, trouvons une structure de données. Une façon simple, bien sûr, est de stocker des choses dans un std :: vector.

template< class BaseType >
class BigInt
{
typedef typename BaseType BT;
protected: std::vector< BaseType > value_;
};

Vous pouvez envisager de créer un vecteur de taille fixe et de le préallouer. La raison étant que pour diverses opérations, vous devrez passer par chaque élément du vecteur - O (n). Vous voudrez peut-être savoir à l'avance quelle sera la complexité d'une opération, et c'est exactement ce que fait n.

Mais maintenant, quelques algorithmes pour opérer sur les nombres. Vous pouvez le faire au niveau logique, mais nous utiliserons cette puissance magique pour calculer les résultats. Mais ce que nous allons reprendre de l'illustration logique de Half- et FullAdders est la façon dont il traite les portages. A titre d'exemple, considérons la manière dont vous implémenteriez l'opérateur + = . Pour chaque nombre dans BigInt & Lt; & Gt; :: value_, vous ajouteriez ceux-ci et verriez si le résultat produisait une forme de retenue. Nous ne le ferons pas un peu, mais nous nous baserons sur la nature de notre BaseType (long, int, court ou autre): il déborde.

Si vous ajoutez deux nombres, le résultat doit être supérieur au plus grand de ces chiffres, n'est-ce pas? Si ce n'est pas le cas, le résultat a débordé.

template< class BaseType >
BigInt< BaseType >& BigInt< BaseType >::operator += (BigInt< BaseType > const& operand)
{
  BT count, carry = 0;
  for (count = 0; count < std::max(value_.size(), operand.value_.size(); count++)
  {
    BT op0 = count < value_.size() ? value_.at(count) : 0, 
       op1 = count < operand.value_.size() ? operand.value_.at(count) : 0;
    BT digits_result = op0 + op1 + carry;
    if (digits_result-carry < std::max(op0, op1)
    {
      BT carry_old = carry;
      carry = digits_result;
      digits_result = (op0 + op1 + carry) >> sizeof(BT)*8; // NOTE [1]
    }
    else carry = 0;
  }

  return *this;
}
// NOTE 1: I did not test this code. And I am not sure if this will work; if it does
//         not, then you must restrict BaseType to be the second biggest type 
//         available, i.e. a 32-bit int when you have a 64-bit long. Then use
//         a temporary or a cast to the mightier type and retrieve the upper bits. 
//         Or you do it bitwise. ;-)

L’autre opération arithmétique est analogue. Heck, vous pouvez même utiliser les stl-functors std :: plus et std :: minus, std :: times et std :: divides, ..., mais faites attention. :) Vous pouvez également implémenter la multiplication et la division en utilisant vos opérateurs plus et moins, mais c'est très lent, car cela recalculerait les résultats que vous aviez déjà calculés dans les appels précédents à plus et moins à chaque itération. Il existe de nombreux algorithmes efficaces pour cette tâche simple, utiliser wikipedia ou sur le Web.

Et bien sûr, vous devez implémenter des opérateurs standard tels que operator<< (il suffit de décaler chaque valeur de value_ vers la gauche pour n bits, en commençant par le value_.size()-1 ... oh et rappelez-vous le report :), <= > - vous pouvez même optimiser un peu ici, en vérifiant le nombre approximatif de chiffres avec operator< d’abord. Etc. Ensuite, rendez votre classe utile, par befriendig std :: ostream size().

J'espère que cette approche est utile!

Answer 3

Il existe une section complète à ce sujet: [L’art de la programmation informatique, vol. 2: les algorithmes de séminaire, section 4.3 Arithmétique de précisions multiples, p. 265-318 (éd.3)]. Vous trouverez d’autres documents intéressants au chapitre 4, Arithmétique.

Si vous ne voulez vraiment pas regarder une autre implémentation, avez-vous pensé à ce que vous voulez apprendre? Il y a d'innombrables erreurs à faire et les découvrir est instructif et aussi dangereux. Il est également difficile d'identifier des économies informatiques importantes et de disposer de structures de stockage appropriées pour éviter de graves problèmes de performances.

Une question de défi pour vous: comment comptez-vous tester votre implémentation et comment proposez-vous de démontrer que l'arithmétique est correcte?

Vous voudrez peut-être une autre implémentation à tester (sans regarder comment elle le fait), mais il faudra plus que cela pour pouvoir généraliser sans s'attendre à un niveau de test excrétant. N'oubliez pas de prendre en compte les modes de défaillance (problèmes de mémoire, de pile, de fonctionnement trop long, etc.).

Amusez-vous!

Answer 4

addition devrait probablement être fait dans l'algorithme de temps linéaire standard
mais pour multiplier, vous pouvez essayer http://en.wikipedia.org/wiki/Karatsuba_algorithm

Answer 5

Une fois que vous avez les chiffres du nombre dans un tableau, vous pouvez faire l'addition et la multiplication exactement comme si vous les faisiez à la main.

Answer 6

N'oubliez pas que vous n'avez pas besoin de vous limiter à 0-9 pour les chiffres, c'est-à-dire utiliser des octets en tant que chiffres (0-255) et vous pouvez toujours effectuer un calcul arithmétique à la main longue identique à celui que vous feriez pour les chiffres décimaux. Vous pouvez même utiliser un tableau de long.

Answer 7

Je ne suis pas convaincu que l’utilisation d’une chaîne soit la bonne solution - bien que je n’ai jamais écrit de code moi-même, je pense que l’utilisation d’un tableau de type numérique de base pourrait constituer une meilleure solution. L'idée est que vous étendez simplement ce que vous avez déjà de la même manière que la CPU étend un seul bit en un entier.

Par exemple, si vous avez une structure

typedef struct {
    int high, low;
} BiggerInt;

Vous pouvez ensuite effectuer manuellement des opérations natives sur chacun des & "; chiffres &"; (haut et bas, dans ce cas), en tenant compte des conditions de débordement:

BiggerInt add( const BiggerInt *lhs, const BiggerInt *rhs ) {
    BiggerInt ret;

    /* Ideally, you'd want a better way to check for overflow conditions */
    if ( rhs->high < INT_MAX - lhs->high ) {
        /* With a variable-length (a real) BigInt, you'd allocate some more room here */
    }

    ret.high = lhs->high + rhs->high;

    if ( rhs->low < INT_MAX - lhs->low ) {
        /* No overflow */
        ret.low = lhs->low + rhs->low;
    }
    else {
        /* Overflow */
        ret.high += 1;
        ret.low = lhs->low - ( INT_MAX - rhs->low ); /* Right? */
    }

    return ret;
}

C'est un exemple un peu simpliste, mais il devrait être assez évident de savoir comment étendre à une structure qui a un nombre variable de la classe numérique de base que vous utilisez.

Answer 8

Comme d’autres l’ont dit, faites-le à l’ancienne, mais évitez de le faire en base 10. Je vous conseillerais de le faire en base 65536 et de stocker les objets dans un éventail de longs.

Answer 9

Utilisez les algorithmes que vous avez appris en 1 re à la 4 e année.
Commencez par la colonne des unités, puis les dizaines, etc.>

Answer 10

Si votre architecture cible prend en charge la représentation sous forme de nombres BCD (décimal codé binaire), vous pouvez obtenir une prise en charge matérielle de la multiplication / addition longue que vous devez effectuer. Obtenir que le compilateur émette une instruction BCD est quelque chose que vous devrez lire sur ...

Les puces de la série Motorola 68K l’avaient. Pas que je sois amer ou quoi que ce soit.

Answer 11

Je commencerais par avoir un tableau d'entiers de taille arbitraire, utilisant 31 bits et le 32n'd en débordement.

L'opérateur de démarrage serait ADD, puis MAKE-NEGATIVE, en utilisant le complément à 2. Après cela, la soustraction est triviale et une fois que vous avez ajouté / sub, tout le reste est faisable.

Il existe probablement des approches plus sophistiquées. Mais ce serait l'approche naïve de la logique numérique.

Answer 12

Pourrait essayer d'implémenter quelque chose comme ceci:

http://www.docjar.org/html/ api / java / math / BigInteger.java.html

Vous n'avez besoin que de 4 bits pour un seul chiffre compris entre 0 et 9

Ainsi, une valeur Int permettrait un maximum de 8 chiffres chacun. J'ai décidé de m'en tenir à un tableau de caractères afin d'utiliser deux fois plus de mémoire, mais pour moi, il n'est utilisé qu'une fois.

De même, lorsque vous stockez tous les chiffres dans un seul fichier, cela le complique excessivement et peut même le ralentir.

Je n'ai pas de test de vitesse, mais en regardant la version java de BigInteger, il semble que cela fasse beaucoup de travail.

Pour moi, je fais le dessous

//Number = 100,000.00, Number Digits = 32, Decimal Digits = 2.
BigDecimal *decimal = new BigDecimal("100000.00", 32, 2);
decimal += "1000.99";
cout << decimal->GetValue(0x1 | 0x2) << endl; //Format and show decimals.
//Prints: 101,000.99

Answer 13

soustrayez 48 de votre chaîne d’entier et imprimez-le pour obtenir le nombre de chiffres plus gros. effectuez ensuite l'opération mathématique de base.    sinon, je fournirai une solution complète.