Entiers courts et longs

Division euclidienne de deux entiers : si a et b sont deux entiers, a $\geq$ 0, b > 0, il existe un unique couple (q, r) tel que

a = bq + r,    r $$\in$$ [0,| b|[

c'est la division euclidienne. En effet on prend pour q le plus grand entier tel que a - bq > 0.

Nous écrivons les nombres entiers en base 10. Les ordinateurs utilisent des circuits binaires pour stocker les informations, il est donc naturel d'y travailler en base 2. En général, pour trouver l'écriture d'un nombre en base b (par exemple b = 2), on effectue des divisions euclidienne successives par b du nombre puis de ses quotients jusqu'à ce que le quotient soit 0 et on accolle les restes obtenus (premier reste à droite, dernier reste à gauche). Inversement, pour retrouver un entier d à partir de son écriture d_n...d₀, on traduit les divisions euclidiennes successives en

d = (...((d_nb + d_n-1)b + d_n-2)... + d₁)b + d₀

= d_nbⁿ + d_n-1b^n-1 + ... + d₀

Par exemple, vingt-cinq s'écrit en base 16 19 car 25 divisé par 16 donne quotient 1, reste 9. En base 2, on trouverait 00011001 car 25 = 2⁴ +2³ + 1. On peut effectuer les opérations arithmétiques de base (+,-,*, division) directement en base 2 (ou 16). Par exemple la table de l'addition est 0+0=0, 0+1=1+0=1 et 1+1=0 je retiens 1, donc :

  01001111
+ 01101011
----------
  10111010

Les microprocesseurs peuvent effectuer directement les opérations arithmétiques de base sur les entiers ``machine'' (déclinés en plusieurs variantes selon la taille et la possibilité d'avoir un signe). Noter que la division de deux entiers a et b n'a pas la même signification que la division de deux réels, comme elle ne tombe pas forcément juste, on calcule le quotient et le reste entiers.

Ces entiers machines permettent de représenter de manière exacte des petits entiers relatifs par exemple un entier machine signé sur 4 octets est compris entre [- 2³¹, 2³¹ - 1]. Selon le microprocesseur les 4 octets représentant l'entier sont stockés par adresse mémoire décroissante ou croissante (big ou little endian). Sur certains systèmes (dits BCD), on écrit les entiers en base 10, chaque chiffre occupant 4 bits (qui normalement sert à stocker un chiffre en base 16). Les microprocesseurs correspondants ont un flag leur permettant d'effectuer les opérations sur des nombres vu en représentation BCD (base 10) ou hexadécimale (base 16).

Ces entiers machines permettent de faire du calcul exact sur les entiers, mais à condition qu'il n'y ait pas de dépassement de capacité, par exemple pour des entiers 32 bits, 2³¹ +2³¹ renverra 0. Ils sont très utilisés en calcul formel pour les algorithmes dits modulaires (on travaille modulo un entier assez petit). Pour travailler avec des entiers plus grands, on doit utiliser des entiers de taille plus grande, mais il faut alors programmer les opérations de base et décider d'un mécanisme de stockage, par exemple en représentant un entier par une zone mémoire commencant par la taille et suivie par l'écriture à l'aide d'entiers machines de l'entier (en base 2³²). Bien entendu, plus les entiers sont grands, plus les opérations seront longues, par exemple l'addition de deux entiers longs de taille N nécessite un temps proportionnel à N, leur multiplication par l'algorithme élémentaire nécéssite un temps proportionnel à N² (mais il existe des algorithmes plus efficaces, par exemple Karatsuba ou FFT, cf. Knuth, The Art of Computer Programming).

On sait donc représenter les entiers, pour les rationnels, il suffit de les représenter comme un couple d'entiers correspondant à leur écriture sous forme de fraction irréductible avec un dénominateur positif. L'algorithme d'Euclide permet de calculer le PGCD (plus grand commun diviseur) de 2 entiers, écrit ici en syntaxe Xcas :

pgcd(x,y):={
  local r;
  while (y!=0){
    r:=irem(x,y); // reste de x par y
    x:=y; // PGCD(x,y)=PGCD(y,r) donc on decale
    y:=r;
  }
  return x; // c'est le resultat car PGCD(x,0)=x
}

On utilise le fait qu'un nombre divise a et b si et seulement si il divise r = a - bq et b. Le PGCD de a et b est donc le PGCD de b et du reste de la division euclidienne de a par b. Comme le reste est en valeur absolue plus petite que | b|, la taille des variables x,y,r décroit à chaque itération. Arrive un moment où le reste est nul, le PGCD est alors l'entier par lequel on a divisé. On utilise cet algorithme et la division euclidienne pour simplifier une fraction d'entiers par le PGCD du numérateur et du dénominateur pour l'écrire sous forme irréductible.

Les calculs sont maintenant exacts et sans limitation de capacité (ou presque, la taille des entiers longs est bornée parce que la taille du champ mémoire fixant la longueur de stockage est bornée) mais souvent trop lents pour les calculs numériques usuels (par exemple pour calculer la valeur approchée de cosinus 23 degrés 27 minutes). On utilise alors un autre type dont les calculs de base sont gérés par le microprocesseur (ou son coprocesseur arithmétique).