C'est l'approche informatique la plus classique.
Plutôt que d'utiliser des nombres réels on va se contenter d'une
approximation. Cette approche est conforme au calcul
numérique que l'on peut faire à la main dans lequel un nombre
est représenté sous la forme d'un nombre décimal.
Ici on utilise une représentation avec des chiffres binaires.
La norme IEEE 754 [IEE85]
spécifie exactement les formats possibles
pour représenter de tels nombres ainsi que les règles
d'arrondis à appliquer pour obtenir le résultat d'un calcul.
Un nombre flottant double précision (double en java)
est représenté par 64 bits. Sur ces 64 bits
se répartissent comme suit :
1 bit s, 52 bits m et 11 bits e représentent
le nombre (-1)s ⋅ 0.1m ⋅ 2e-1024 en notation
normalisée.
La notation normalisée signifie que l'on choisit l'exposant
pour que la mantisse soit comprise entre 1/2 et 1,
son développement binaire commence donc toujours par 0.1 et il
n'est pas nécessaire de représenter ces deux chiffres.
Les nombres représentables en machines sont donc régulièrement espacé
avec des intervalles de 2p-52 entre 2p et 2p+1.
Lorsque l'on se rapproche de zéro cette notation permet donc,
lorsque e=0 de représenter les nombres de [2-1025,2-1024]
avec des écarts de 2-1077 mais pas du tout les nombres entre
0 et 2-1025 pour pallier à ce trou dans les nombres représentables
on utilise lorsque e=0 la représentation dénormalisée.
Si e=0, la valeur du nombre représentée est
(-1)s ⋅ 0.m ⋅ 2-1024 on peut ainsi représenter
les nombres de l'intervalle [0,2-1024] avec des écarts réguliers
de 2-1076.
Si on a deux nombres flottants a et b
le résultat d'une opération arithmétique sur ces nombres,
la multiplication pour fixer les idées, n'est en général
pas un nombre représentable.
Si on appelle s et s' les deux nombres représentables
qui encadrent la vrai valeur de a⋅b.
La valeur calculée par la machine comme le résultat de a*b
est alors s ou s' (s<s') selon le mode d'arrondi choisi.
La norme IEEE 754 propose quatre modes d'arrondi :
au plus près, vers +∞, vers -∞ et vers 0.
En mode «au plus près» a*b est arrondi au plus proche flottant
représentable, il faut donc comparer la valeur exacte
a⋅b avec s+s'/2.
En mode vers +∞ on utilise s'.
En mode vers -∞ on utilise s.
Et en mode vers 0 on utilise s si a⋅b<0 et s' sinon.
Il important de noter que la notion d'arrondi est définie très précisément.
La valeur utilisée pour a*b est parfaitement définie par la norme
afin d'assurer la portabilité sur différents processeurs.
Cette norme définissant l'arrondi avec précision s'applique
au quatre opérations +,-,*,/ et à la racine carré.
Il faut parfois utiliser certaines options de compilation
pour que le processeur se conforme à la norme.
Des travaux pour étendre ce type de norme définissant l'arrondi
avec précision à d'autres fonctions telles que sinus, exponentielle...existent. La difficulté résidant dans le fait qu'il ne suffit pas
de calculer une approximation précise de la valeur recherchée,
mais qu'il faut comparer exactement cette valeur avec les bornes
des intervalles ce qui peut s'avérer très délicat quand on est très près de
ces bornes.
Les propriétés de l'arithmétique machine ne sont pas celle des réels,
la propriété la plus cruciale étant l'associativité.
Commutativité
L'addition et la multiplication sont commutatives.
a+b=b+a et a*b=b*a.
Monotonicité
L'arrondi préserve l'ordre respectif de deux nombres, toutefois les
inégalités strictes deviennent large. En effet il est clair que deux
nombres différents peuvent avoir le même arrondi.
a⋅b < c⋅d
a*b ≤ c*d.
Compatibilité soustraction et comparaison
La soustraction et la comparaison sont bien compatible
on a
a==b ⇔ a-b == 0
Cette propriété est liée à l'usage des nombres dénormalisés
qui garanti que l'écart entre deux nombres représentables
est également un nombre représentable.
Exactitude
Comme on l'a vu, le résultat d'un calcul est toujours arrondi
à un nombre représentable, mais si on peut garantir que le
résultat exact est représentable, alors les nombres flottants
font en fait du calcul exact.
Les flottants double précision font ainsi d'excellents entiers sur
53 bits avec les avantages suivants :
--- gestion plus facile des débordements (hors de l'intervalle
[-253,253]). En effet le calcul sur les entiers machines est fait
modulo le plus grand entier, il n'est donc pas immédiat de savoir si une
multiplication a débordé.
--- possibilité de travailler dans les multiples de 2k (k∈ ZZ)
directement, sans faire explicitement les multiplications
par 2-k pour repasser aux entiers.
--- sur certaines architectures, le calcul sur les flottants double précision
est plus rapide que sur les entiers 64 bits voire même plus rapide que
les entiers 32 bits.
Associativité
Le caractère associatif est perdu, les bits les moins significatifs
du résultat d'une opération disparaissent.
On peut parfois utiliser cette non associativité, par exemple
l'arrondi entier d'un nombre a∈[-251,251] peut être obtenu par
Ea = (a + CST) - CST où CST vaut 3⋅ 251.
La démonstration que cette opération fonctionne bien
peut être effectuée comme suit :
La valeur exacte de a + CST appartient à l'intervalle
[252,253], dans cet intervalle les nombres représentables
exactement (double) coïncident avec les entiers puisqu'un
tel nombre s'écrit en binaire 253 ⋅ 0.1…
et que le 53ème chiffre derrière la virgule correspond bien à
une unité.
La valeur calculée de a + CST est donc l'arrondi entier au plus proche
de la valeur réelle.
La valeur calculée de (a + CST) - CST est alors l'arrondi entier
au plus proche de a puisque le résultat exact de la soustraction
est nécessairement un nombre représentable.
On peut ensuite récupérer la partie fractionnaire par da = a - Ea,
le résultat réel de cette opération est un nombre exactement représentable,
cette soustraction sera donc calculée exactement.
La seule opération a être non exacte est donc la première addition
a + CST, mais grâce aux spécifications exactes des
règles d'arrondi, on contrôle parfaitement le résultat.
On peut représenter un grand nombre entier par une liste de
chiffres en base 252, chacun de ces chiffres étant représenté
par un double.
On s'inspire ici d'un travail de Priest [Pri91]
qui représente lui des grands flottants.
Écrire une telle classe MyBigInt.
Écrire pour cette classe les fonctions d'addition,
soustraction, multiplication, comparaison et affichage
static MyBigInt add(MyBigInt x, MyBigInt y)
static MyBigInt sub(MyBigInt x, MyBigInt y)
static MyBigInt mult(MyBigInt x, MyBigInt y)
static boolean isGreater(MyBigInt x, MyBigInt y)
static void ecrit(MyBigInt x)
Pour l'écriture de ces fonctions, on utilisera les propriétés
de l'arithmétique IEEE 754 (tel que l'arrondi expliqué plus haut)
pour programmer les opérations intermédiaires.
Les algorithmes utilisés seront les algorithmes
de l'école primaire.
Par exemple pour l'addition, à une étape
donnée on disposera de deux chiffres x et y ainsi que d'une retenue r.
On commencera par calculer x+y+r et à l'arrondir correctement pour
trouver la retenue R à passer pour le chiffre plus à gauche,
ensuite on calculera (-R)+x+y+r pour déterminer le chiffre du résultat
avant de passer au chiffre suivant.
On contrôlera (sur le papier, pas dans le programme) que le calcul flottant
ne fait pas d'arrondi non voulu.
Pour la fonction d'affichage (en base 10),
on pourra programmer une division par les puissances de 10,
ou plus simplement précalculer les puissances de 10
dans un tableau et procéder par comparaison.
Calculer factorielle, jusqu'au débordement de capacité
des nombres flottants.
Comparer avec Maple pour être sur de l'exactitude des calculs.
Le test de cocyclicité consiste à évaluer
le signe du déterminant
½
½
½
½
½
xp
xq
xr
xt
yp
yq
yr
yt
xp2 + yp2
xq2 + yq2
xr2 + yr2
xt2 + yt2
1
1
1
1
½
½
½
½
½
.
Le signe de ce déterminant décrit si le point t
est à l'intérieur ou à l'extérieur du cercle circonscrit
au triangle pqr (supposé direct).
Comment programmer ce test pour des grands entier en effectuant
le moins de calcul possible, c'est à dire que si il est possible de conclure
sur le signe sans calculer tous les chiffres du résultat,
on souhaite le faire.
Donner des exemples de telles situation, et de situation où il faut
pousser les calculs dans le cas où les coordonnées des points
ont un seul chiffre significatif en base 252
(ces nombres s'écrivent x (252)p où x∈[-252,252]
et p est une (petit) entier).