Implémentation personnelle des “BigNumbers”

3216290796_18f53fb0fa_b

Aujourd’hui je vous présente une implémentation personnelle (et naïve) des “BigNumbers” démarrée il y a longtemps (sous forme de stage à l’école et repris à mon compte pendant mon temps libre)

“Diagramme de classe” et principe général d’implémentation

Celle-ci se présente sous forme de 2 classes :

  • BigInt : permet de gérer des entiers à peu près aussi grand que l’on souhaite. (En fait, la limitation technique est de 8589934588 chiffres)
  • BigRat : permet de gérer des rationnels sous forme de fractions de BigInt

La base de cette implémentation est l’écriture du nombre en base 10000 avec stockage de chaque “chiffre” (chiffre allant de 0 à 9999) dans un tableau. Je vous accorde que la notion de chiffre est ici discutable : je souhaitais juste reprendre la notion mathématique associée.

Par exemple, 4578965561230 sera stocké en interne sous forme d’un tableau de 4 éléments:

  • Elément 0 : 1230
  • Elément 1 : 6556
  • Elément 2 : 5789
  • Elément 3 : 4

On a bien 4578965561230  = 4 * (10000 ^ 3) + 5789 * (10000 ^ 2) + 6556 * (10000 ^ 1) + 1230 * (10000 ^ 0).

Réécriture des opérations

Ce qui a été intéressant dans cette réécriture, c’est d’optimiser un minimum le code (même si de base l’implémentation n’est pas la meilleure : Cf. dernier paragraphe).

Ainsi le codage de l’opérateur ++ a été optimisé pour être plus efficace qu’un bête “+1”.

Je vous laisse aussi imaginer la réécriture de la division qui est assez facile à poser mais légèrement plus compliqué à écrire (rien d’impossible mais quelques tâtonnements pour les cas “tordus”)

J’en ai aussi profité pour ajouter des méthodes permettant le calcul :

  • de l’ensemble des diviseurs d’un entier
  • du PPCM de 2 nombres (utilisé pour les simplifications de fractions dans les BigRat)
  • du PGCD de 2 nombres

Surcharge des opérateurs

Le deuxième point aussi très intéressant a été de se pencher sur la surcharge des opérateurs : +, –, *, / de manière classique mais aussi ++, –, les opérateurs de comparaison et pour finir les casts explicites ou implicites.

Exemple d’écriture de surcharge d’opérateurs :

[sourcecode language= »csharp » padlinenumbers= »true »]
// Surcharge de l’opérateur *
public static BigInt operator *(BigInt bi1, BigInt bi2)
{
}

// Surcharge de l’opérateur >> (Shift)
public static BigInt operator >>(BigInt bi, int iCount)
{
}

// Cast explicite d’un BigInt vers un double
// Ex : double d = (double) bi;
public static explicit operator long(BigInt bi)
{
}

// Cast implicite d’un double vers un BigInt
// Ex : BigInt b = 10;
public static implicit operator BigInt(long i)
[/sourcecode]

Optimisations à faire

Bien que fonctionnant correctement et avec des performances acceptables, il serait utile de revoir l’implémentation de base pour profiter au maximum de ce que fournit déjà un ordinateur. A ce titre, je pense que la division fonctionne mais n’est pas du tout optimisée.

Une implémentation qui semblerait pas mal serait :

  1. Soit de continuer à utiliser un tableau contenant cette fois des entiers non signés
  2. Soit de passer par un BitArray pour pouvoir manipuler directement tous ces octets

Je pense qu’en passant par une de ces implémentations tous les calculs seraient accélérés : la complexité passerait alors dans l’écriture en base 10 du résultat.

Si vous avez envie de vous y frotter, allez y : le code est disponible sous codeplex : http://bignumbers.codeplex.com Sourire