Programmation Java/Nombre de taille arbitraire

Collections

Tags Javadoc

Programmation Java

Version imprimable

[ Modifier le sommaire ]

Collections

Tags Javadoc

Java permet de manipuler des nombres de taille arbitraire pour utiliser de l'arithmétique multiprécision. Ces nombres permettent d'aller au-delà des limites des types numériques primitifs, sans perte de précision, ou avec perte contrôlée. Ils sont utilisés dans des domaines où le calcul avec tous les chiffres est nécessaire (la finance, calcul mathématique de précision, calcul de clés cryptographiques, ...).

Deux classes du paquetage java.math sont utilisées pour représenter deux types de nombres de taille arbitraire :

La classe BigInteger représente un nombre entier de taille arbitraire,
La classe BigDecimal représente un nombre réel de taille arbitraire.

La précision est arbitraire mais reste soumise aux contraintes du système :

La quantité de mémoire limite le nombre de chiffres stockable. Même si cette limite peut sembler haute, il ne faut pas oublier de multiplier par le nombre d'instances utilisées à un instant donné pour se rendre compte de la quantité de mémoire utilisée.
La vitesse du processeur limite la quantité de calcul sur les nombres de très grande précision. Les algorithmes de calcul comme l'addition ou la soustraction s'effectuent de manière linaire par rapport à la précision employée ; mais d'autres calculs comme la multiplication, la division, le calcul de racine, ... ont besoin de confronter chaque chiffre à chacun des autres, et le temps de calcul est alors quadratique ou exponentiel par rapport à la précision employée.

Nombre entier

La classe BigInteger représente un nombre entier de taille arbitraire. Un tel entier peut être créé à partir d'une chaîne de caractères, comme dans l'exemple suivant :

// À partir de la représentation en décimal :
BigInteger nombre_d_atomes = new BigInteger("7312154503213716790123144675124456301892787921502480260380150468277");
// À partir de la représentation en hexadécimal :
BigInteger cle = new BigInteger("A87B31697C6A9d9363B275E610F245C246A932B14569D273AE54CEC171CAFEFADE", 16);

Il peut aussi être créé à partir d'un tableau d'octets d'une représentation en complément à deux, dans l'ordre big-endian : l'octet le plus significatif est le premier.

// À partir d'un tableau d'octets de la représentation
// en complément à deux du nombre -17179869184 :
BigInteger nombre = new BigInteger(new byte[]{ 0xFC, 0x00, 0x00, 0x00, 0x00 });

Il peut aussi être créé à partir d'un nombre de type long en utilisant la méthode statique valueOf. Comme les instances sont immuables, la méthode statique permet de retourner la même instance pour les valeurs fréquemment utilisées.

// À partir d'un nombre de type long :
BigInteger total_heures = BigInteger.valueOf(24L);

La classe définit aussi quelques instances comme membres statiques pour les valeurs classiques :

BigInteger.ZERO pour le nombre zéro,
BigInteger.ONE pour le nombre un,
BigInteger.TEN pour le nombre dix.

Opérations arithmétiques

Les opérateurs en Java ne s'appliquent qu'aux types primitifs, excepté le plus + permettant de concaténer des chaînes de caractères. Pour effectuer des opérations sur des instances de BigInteger, il faut appeler les méthodes résumées dans le tableau ci-dessous. Une instance de BigInteger étant immuable, les méthodes ne modifie pas l'objet lui-même mais retournent une nouvelle instance pour le résultat. Si ce n'était pas le cas, il serait possible de modifier la valeur de BigInteger.ONE par exemple, ce qui fausserait les calculs utilisant la constante.

Méthodes pour les opérateurs arithmétiques
Opérateur équivalent	`BigInteger a.`	Description
`-`	negate()	Retourne le résultat de l'inversion de signe `-a`
`+`	add(BigInteger b)	Retourne le résultat de l'addition `a+b`
`-`	subtract(BigInteger b)	Retourne le résultat de la soustraction `a-b`
`*`	multiply(BigInteger b)	Retourne le résultat de la multiplication `a*b`
`/`	divide(BigInteger b)	Retourne le résultat de la division `a/b`
`%`	remainder(BigInteger b)	Retourne le reste de la division `a%b`
	mod(BigInteger b)	Retourne le modulo de a et b. Par rapport au reste de la division, le modulo n'est jamais négatif.
`/ %`	divideAndRemainder(BigInteger b)	Retourne un tableau de deux `BigInteger` : le quotient et le reste de la division `{a/b},` `a%b}`

Comme les expressions complexes sur ces nombres entraînent la création de multiples instances, il n'est pas utile de garder les résultats intermédiaires, sauf de manière temporaire pour déboguer l'expression. Il est donc courant d'enchaîner les méthodes :

BigInteger
    a = new BigInteger("1500000000"),
    b = new BigInteger("578000057"),
    c = new BigInteger("1234567");

//  d  =  ( a+b ) * c / 10
BigInteger d = a.add(b).multiply(c).divide(BigInteger.TEN);

Autres opérations arithmétiques sur ces nombres :

Autres opérations arithmétiques
`BigInteger a.`	Description
abs()	Retourne la valeur absolue `Math.abs(a)`
signum()	Retourne le signe sous la forme d'un entier `Math.signum(a)` (-1 négatif, 0 zéro, +1 positif)
gcd(BigInteger b)	Retourne le plus grand diviseur commun entre les valeurs absolues des deux nombres.
max(BigInteger b)	Retourne le plus grand des deux nombres.
min(BigInteger b)	Retourne le plus petit des deux nombres.
pow(int n)	Retourne le calcul de la puissance n du nombre $a^{n}$ .

Opérations sur les bits

Les bits des entiers de taille arbitraire peuvent aussi être manipulés.

Méthodes pour les opérateurs sur les bits
Opérateur équivalent	`BigInteger a.`	Description
`~`	not()	Retourne le résultat de l'inversion de bits `~a`
`&`	and(BigInteger b)	Retourne le résultat du et bit à bit `a & b`
`& ~`	andNot(BigInteger b)	Retourne le résultat du et bit à bit avec inversion `a & ~b`. Cette méthode est un raccourci pour la combinaison des opérateurs `&` et `~` pour le masquage de bits.
`\|`	or(BigInteger b)	Retourne le résultat du ou bit à bit `a \| b`
`^`	xor(BigInteger b)	Retourne le résultat du ou exclusif bit à bit `a ^ b`
`<<`	shiftLeft(int n)	Retourne le résultat du décalage de n bits vers la gauche `a << n`
`>>`	shiftRight(int n)	Retourne le résultat du décalage de n bits vers la droite `a >> n`

Autres opérations sur les bits de ces nombres :

Autres opérations sur les bits
`BigInteger a.`	Description
bitLength()	Retourne le nombre minimal de bits pour la représentation en complément à deux, sans le bit de signe.
bitCount()	Retourne le nombre de bits différents du bit de signe, c'est-à-dire le nombre de 1 pour un nombre positif, le nombre de 0 pour un nombre négatif.
clearBit(int n)	Retourne le nombre avec le bit n mis à zéro.
setBit(int n)	Retourne le nombre avec le bit n mis à un.
flipBit(int n)	Retourne le nombre avec le bit n inversé.
testBit(int n)	Retourne un booléen indiquant si le bit n est à un.
getLowestSetBit()	Retourne le numéro du bit à 1 de plus faible poids, ou -1 si aucun (pour le nombre zéro).

Opérations arithmétiques modulaires

La classe BigInteger a également des méthodes pour l'arithmétique modulaire. Le modulo m détermine l'intervalle des entiers utilisés : de 0 (inclus) à m (exclus).

Opérations arithmétiques modulaires
`BigInteger a.`	Description
mod(BigInteger m)	Réduit le nombre par reste de la division par m et retourne un nombre entier positif ou nul inférieur à m.
modPow(BigInteger exponent, BigInteger m)	Retourne le calcul de $a^{exponent}{\pmod {m}}$
modInverse(BigInteger m)	Retourne l'inverse du nombre modulo m $a^{-1}{\pmod {m}}$ . Multiplier le résultat par le nombre `a` donne 1 modulo m. Une exception de type `java.lang.ArithmeticException` peut être lancée si $m\leq 0$ ou si le nombre n'est pas premier relativement à m.

Générer un nombre probablement premier

Les algorithmes de cryptographie utilisent souvent des problèmes mathématiques difficiles à résoudre en un temps raisonnable, dont celui de la décomposition des grands nombres entiers en facteur premiers.

new BigInteger(int bitLength, int certainty, Random rnd): Crée un nombre positif, probablement premier.; La probabilité que le nombre créé soit premier est : $p>1-{\frac {1}{2^{certainty}}}$
BigInteger.probablePrime(int bitLength, Random rnd): Retourne un nombre positif, probablement premier.; La probabilité que le nombre créé soit premier est : $p>1-{\frac {1}{2^{100}}}$

Paramètres :

bitLength est le nombre de bits voulu.
certainty représente la mesure d'incertitude sur la primalité tolérée. Plus sa valeur est grande, plus le calcul prend du temps.
rnd est une instance de la classe java.util.Random pour la génération des nombres dont la primalité est testée.

Conversions

La classe BigInteger est une sous-classe de Number, comme les classes englobant les nombres primitifs. Elle possède donc les mêmes méthodes de conversions, qui tronque le résultat s'il ne loge pas dans le type demandé :

byte byteValue(),
short shortValue(),
int intValue(),
long longValue(),
float floatValue(),
double doubleValue().

Pour les types entiers, il y a également une variante retournant une valeur exacte ou une exception de type java.lang.ArithmeticException si le nombre ne loge pas dans le type demandé :

byte byteValueExact(),
short shortValueExact(),
int intValueExact(),
long longValueExact().

Nombre décimal

La classe BigDecimal représente un nombre décimal de taille arbitraire défini par un entier de taille arbitraire (type BigInteger) et un nombre entier de type int définissant la position de la virgule. Il y a donc une limite (celle du type int 32 bits) sur l'échelle.

// À partir de la représentation en décimal :
BigDecimal pi = new BigDecimal("3.14159265358979323846264338327950288419716939937510582097494459230781640628");

Il est possible de créer une instance de BigDecimal à partir d'une valeur de type double. Cependant, il peut y avoir une perte de précision :

BigDecimal un_dixieme = new BigDecimal(0.1D);
// 0.1000000000000000055511151231257827021181583404541015625

L'utilisation de la méthode statique valueOf permet d'éviter cette perte de précision car la valeur est convertie en chaîne de caractère en appelant la méthode Double.toString :

BigDecimal un_dixieme = BigDecimal.valueOf(0.1D); // 0.1
// Équivalent :
BigDecimal un_dixieme = new BigDecimal(Double.toString(0.1D)); // 0.1

Cependant la précision possible du nombre construit par ce moyen est limitée par celle du type double.

La classe définit aussi quelques instances comme membres statiques pour les valeurs classiques :

BigDecimal.ZERO pour le nombre zéro,
BigDecimal.ONE pour le nombre un,
BigDecimal.TEN pour le nombre dix.

Précision et échelle

La méthode precision() retourne la précision, c'est-à-dire le nombre de chiffres décimaux du nombre. La méthode scale() retourne la position de la virgule par rapport au dernier chiffre de précision. La méthode unscaledValue() retourne l'entier de type BigInteger représentant la valeur entière sans échelle ; son nombre de chiffres vaut precision().

Exemples :

Nombre	`.precision()`	`.scale()`	`.unscaledValue()`
`new BigDecimal("1250000")`	`7`	`0`	`1250000`
`new BigDecimal("125E4")`	`3`	`-4`	`125`
`new BigDecimal("0.000125")`	`3`	`6`	`125`
`new BigDecimal("0.0001250000")`	`7`	`10`	`1250000`

La valeur représentée par un nombre de type BigDecimal est donc $unscaledValue\times 10^{-scale}$ .

Contexte

La classe MathContext est utilisée par plusieurs méthodes comme contexte pour spécifier la précision voulue et le mode d'arrondi à appliquer.

Arrondi

La méthode round(MathContext mc) arrondit le nombre selon le mode et à la précision indiqués dans l'objet MathContext donné en argument.

La précision spécifie le nombre total de chiffres voulu, quel que soit la position de la virgule.

BigDecimal a = new BigDecimal("12345.6789")
    .round(new MathContext(2, RoundingMode.HALF_EVEN));
a.toPlainString()  //  12000
a.scale()          //     -3

Tandis que la méthode setScale(int new_scale, RoundingMode rounding_mode) change l'échelle du nombre :

BigDecimal a = new BigDecimal("12345.6789")
    .setScale(2, RoundingMode.HALF_EVEN);
a.toPlainString()  //  12345.68
a.scale()          //      2

La modification directe de la position de la virgule avec une grande différence allouera une énorme quantité de mémoire pour ajouter les zéros, peut détériorer les performances du processeur. Il faut donc veiller à ne pas faire de grand changements d'échelle.

Opérations arithmétiques

Les opérateurs en Java ne s'appliquent qu'aux types primitifs, excepté le plus + permettant de concaténer des chaînes de caractères. Pour effectuer des opérations sur des instances de BigDecimal, il faut appeler les méthodes résumées dans le tableau ci-dessous. Ces méthodes sont similaires à celles de la classe BigInteger, avec une variante acceptant un objet MathContext pour arrondir le résultat, et un comportement différent pour la division. Une instance de BigDecimal étant immuable, les méthodes ne modifie pas l'objet lui-même mais retournent une nouvelle instance pour le résultat. Si ce n'était pas le cas, il serait possible de modifier la valeur de BigDecimal.ONE par exemple, ce qui fausserait les calculs utilisant la constante.

Méthodes pour les opérateurs arithmétiques
Opérateur équivalent	`BigDecimal a.`	Description
`-`	negate()	Retourne le résultat de l'inversion de signe `-a`
`-`	negate(MathContext mc)	Retourne le résultat arrondi de l'inversion de signe `-a`
`+`	plus()	Retourne le nombre `+a` (méthode pour la symétrie avec negate)
`+`	plus(MathContext mc)	Retourne le nombre arrondi `+a`
`Math.round`	round(MathContext mc)	Retourne le nombre arrondi `Math.round(a)`.
`+`	add(BigDecimal b)	Retourne le résultat de l'addition `a+b`
`+`	add(BigDecimal b, MathContext mc)	Retourne le résultat arrondi de l'addition `a+b`
`-`	subtract(BigDecimal b)	Retourne le résultat de la soustraction `a-b`
`-`	subtract(BigDecimal b, MathContext mc)	Retourne le résultat arrondi de la soustraction `a-b`
`*`	multiply(BigDecimal b)	Retourne le résultat de la multiplication `a*b`
`*`	multiply(BigDecimal b, MathContext mc)	Retourne le résultat arrondi de la multiplication `a*b`
`/`	divide(BigDecimal b)	Retourne le résultat de la division `a/b`. Comme cette opération n'effectue aucun arrondi, si le résultat génère un nombre infini de chiffres, une exception ArithmeticException est lancée.
`/`	divide(BigDecimal b, MathContext mc)	Retourne le résultat arrondi de la division `a/b`
`%`	remainder(BigDecimal b)	Retourne le reste de la division `a%b`
`%`	remainder(BigDecimal b, MathContext mc)	Retourne le reste arrondi de la division `a%b`
`/ %`	divideAndRemainder(BigDecimal b)	Retourne un tableau de deux `BigInteger` : le quotient et le reste de la division `{a/b, a%b}`
`/ %`	divideAndRemainder(BigDecimal b, MathContext mc)	Retourne un tableau de deux `BigInteger` : le quotient et le reste arrondis de la division `{a/b, a%b}`

Comme les expressions complexes sur ces nombres entraînent la création de multiples instances, il n'est pas utile de garder les résultats intermédiaires, sauf de manière temporaire pour déboguer l'expression. Il est donc courant d'enchaîner les méthodes :

BigDecimal
    a = new BigDecimal("1500000000"),
    b = new BigDecimal("5780.00057"),
    c = new BigDecimal("12345.67");

//  d  =  ( a+b ) * c / 10     Arrondi à 8 chiffres de précision
BigDecimal d = a.add(b).multiply(c).divide(BigDecimal.TEN, 8, BigDecimal.ROUND_HALF_EVEN);

Si la division génère un nombre infini de chiffres, il faut préciser l'arrondi voulu :

BigDecimal.ONE.divide(BigDecimal.valueOf(5L));
// --> 0.2

BigDecimal.ONE.divide(BigDecimal.valueOf(7L));
// --> java.lang.ArithmeticException: Non-terminating decimal expansion; no exact representable decimal result.

BigDecimal.ONE.divide(BigDecimal.valueOf(7L), 8, BigDecimal.ROUND_HALF_EVEN);
// --> 0.14285714

// Ou en utilisant un contexte d'arrondi réutilisable :
MathContext mc = new MathContext(8, RoundingMode.HALF_EVEN);
BigDecimal.ONE.divide(BigDecimal.valueOf(7L), mc);
// --> 0.14285714

Autres opérations arithmétiques sur ces nombres :

Autres opérations arithmétiques
`BigDecimal a.`	Description
abs()	Retourne la valeur absolue `Math.abs(a)`
signum()	Retourne le signe sous la forme d'un entier `Math.signum(a)` (-1 négatif, 0 zéro, +1 positif)
max(BigDecimal b)	Retourne le plus grand des deux nombres.
min(BigDecimal b)	Retourne le plus petit des deux nombres.
pow(int n)	Retourne le calcul de la puissance n du nombre $a^{n}$ .
pow(int n, MathContext mc)	Retourne le calcul arrondi de la puissance n du nombre $a^{n}$ .

Comparaison

La comparaison avec la méthode equals compare tous les champs des objets BigDecimal, et peut retourner false même si les deux nombres comparés représentent la même valeur.

Exemple :

BigDecimal a = new BigDecimal("1");   // entier = 1, scale = 0
BigDecimal b = new BigDecimal("1.0"); // entier = 10, scale = 1
a.equals(b)            // false  <!>
a.compareTo(b) == 0    // true

La méthode compareTo est celle qu'il faut utiliser pour comparer les nombres de type BigDecimal.

Appel de la méthode `compareTo`	Comparaison équivalente pour les types primitifs
`a.compareTo(b) == 0`	`a == b`
`a.compareTo(b) < 0`	`a < b`
`a.compareTo(b) > 0`	`a > b`

Conversions

La classe BigDecimal est une sous-classe de Number, comme les classes englobant les nombres primitifs. Elle possède donc les mêmes méthodes de conversions, qui tronquent le résultat s'il ne loge pas dans le type demandé :

byte byteValue(),
short shortValue(),
int intValue(),
long longValue(),
float floatValue(),
double doubleValue().

Pour les types entiers, il y a également une variante retournant une valeur exacte ou une exception de type java.lang.ArithmeticException si le nombre ne loge pas dans le type demandé :

byte byteValueExact(),
short shortValueExact(),
int intValueExact(),
long longValueExact().

Performances

Comme expliqué en introduction, la précision est arbitraire mais reste soumise aux contraintes du système et a un impact sur les performances de l'application.

Plus la précision est grande, plus la quantité de mémoire utilisée est importante. Cela impacte aussi la vitesse d'exécution des opérations car elle est dépendante de la précision employée (temps proportionnel/quadratique/exponentiel).

Dans les expressions longues, certaines opérations peuvent augmenter la précision des résultats. Il peut être important de réduire la précision des résultats intermédiaires avant de poursuivre les opérations, afin de réduire la mémoire utilisée et permettre un temps d'exécution moindre.

Notes