Données Dépassement

Identification

Infoforall

4 - Dépassement sur les entiers


Nous avons vu une première fois le dépassement avec les entiers naturels.

Avec les entiers naturels, il y a dépassement dès qu'on tente d'affecter un bit qui sort de la zone réservée. C'est ainsi que sur un octet, un 255 se transforme en 0 lorsqu'on l'incrémente.

Nous allons voir que l'addition de deux nombres négatifs provoque nécessairement un dépassement de la zone mémoire mais pas un mauvais calcul puisqu'on ne tient pas compte du bit de dépassement.

Alors, comment savoir si un calcul est possible ou non ?

Cette activité est surtout une bonne excuse pour réviser l'encodage des entiers et les fonctions avant le DS !

Documents de cours : open document ou pdf

Logiciel nécessaire : Python ou Thonny, et le module Python matplotlib.

1 - Addition et dépassement de capacité (cas positif)

Un dépassement de capacité est un dépassement des capacités de calculs corrects.

Dans le cas des entiers naturels, un dépassement caractérise toujours un dépassement des capacités de calcul : 255 + 1 donne 0 sur un octet !

Par contre, avec les entiers relatifs, il peut y avoir

  • dépassement sans dépassement des capacités de calculs
  • dépassement des capacités de calculs sans dépassement de la zone mémoire

Du coup, il va falloir être vigilant !

Addition de deux entiers positifs

Nous allons prendre le cas d'entiers signés sur un octet.

Exemple sans dépassement de capacité de calcul

Les bits codent Sig.6432168421
+65 0 1 0 0 0 0 0 1
+33 0 0 1 0 0 0 0 1
(+65) + (+33)
=
+98
Ok 0 1 1 0 0 0 1 0

Exemple avec dépassement de capacité de calcul

Les bits codent Sig.6432168421
+65 0 1 0 0 0 0 0 1
+66 0 1 0 0 0 0 1 0
(+65) + (+33)
=
+131 ?
Echec 1 0 0 0 0 0 1 1

On constate un grave problème : l'addition des bits de la représentation de deux nombres positifs donne un bit de signe à  1  ! L'ordinateur ne parvient donc pas à faire cette addition.

C'est normal : avec un entier signé sur un octet, on dispose de 7 bits pour la valeur. La valeur extrême positive est donc 27 - 1, soit +127.

Comment détecter le dépassement de capacité de calcul lors de l'addition de deux entiers positifs ?

C'est "simple" : lorsqu'on additionne deux nombres positifs signés, il y a dépassement de capacité si le bit de signe change de valeur.

Si les deux nombres qu'on additionne ont un bit de signe à 0, on sait qu'on a un dépassement de capacité s'il passe à 1.

Si on cherche un test de vérification, on pourrait écrire

  • ENTREES : a et b, deux entiers positifs signés
  • On calcule et mémorise c = a + b
  • Si c est positif
    • SORTIE : on renvoie True
  • Sinon
    • SORTIE : on renvoie False

01° On additionne un ensemble d'entiers positifs sur 8 ou 16 bits.

Sans même savoir quels sont les deux entiers positifs, donner les numéros des cas où il y a visiblement eu dépassement de capacités.

  • 1 : 0101 0101 0101 0101
  • 2 : 1101 0101
  • 3 : 1111 1111 1111 1111
  • 4 : 0000 0001
  • 5 : 1000 0000

...CORRECTION...

Il suffit de chercher les résultats pour lesquels le bit de signe est devenu 1.

  • 1 : 0101 0101 0101 0101 : ok
  • 2 : 1101 0101 : dépassement
  • 3 : 1111 1111 1111 1111 : dépassement
  • 4 : 0000 0001 : ok
  • 5 : 1000 0000 : dépassement

Reste à voir l'addition de deux valeurs négatives.

2 - Addition et dépassement de capacité (cas négatif)

Commençons par revoir comment obtenir deux nombres négatifs avec la méthode du complément à deux.

Commençons par un petit rappel sur le complément à deux 

Exemple avec -6

Utilisons la méthode du complément à deux : on part de 6, on inverse et on rajoute de 1 

Code signe 64 32 16 8 4 2 1
Encodage de +6 0 0 0 0 0 1 1 0
Inversion 1 1 1 1 1 0 0 1
Rajout de 1 1 1 1 1 1 0 1 0

Comment obtenir le résultat plus rapidement ? On utilise un octet donc 8 bits. Il y a 256 cas possibles (28). On obtient l'encodage de -6 en réalisant le complément à deux de 6 : 256 - 6 = 250, soit  1111 1010 .

Exemple avec -126

Cherchons l'encodage de -126 en partant de 126, en inversant et en rajoutant 1 :

Code signe 64 32 16 8 4 2 1
Encodage de +126 0 1 1 1 1 1 1 0
Inversion 1 0 0 0 0 0 0 1
Rajout de 1 1 0 0 0 0 0 1 0

Comment obtenir le résultat plus rapidement ? On utilise un octet donc 8 bits. Il y a 256 cas possibles (28). On obtient l'encodage de -6 en réalisant le complément à deux de 6 : 256 - 126 = 130, soit  1000 0010 .

Addition de deux entiers négatifs

Nous allons prendre le cas d'entiers signés sur un octet.

Exemple sans dépassement de capacité de calcul

-6 1 1 1 1 1 0 1 0
-6 1 1 1 1 1 0 1 0
Retenue +1 +1 +1 +1 +1 +1
(-6) + (-6)
=
-12
1 1 1 1 0 1 0 0

On ne tient pas compte du dernier dépassement. Mais est-ce que cela donne bien -12 ?

Pour le savoir, il faut utiliser le complément à deux ! Soit avec la méthode de l'inversion et du plus 1 ou avec la méthode de 256 - la valeur de l'octet si c'était un entier naturel.

1er méthode 

On part de  1111 0100 

Inversion :  0000 1011 

Rajout de 1 :  0000 1100 

Lecture : 8+4 = 12. Il s'agit donc bien de l'encodage de -12.

2e méthode 

On part de  1111 0100 

Le contenu de l'octet lu comme un entier est 128+64+32+16+4 = 244.

On calcule 256 - 244 et on obtient bien 12.

Exemple avec dépassement de capacité de calcul

Les bits codent Sig.6432168421
-6 1 1 1 1 1 0 1 0
-126 1 0 0 0 0 0 1 0
(-6) + (-126)
=
-132 ?
+1 0 1 1 1 1 1 0 0

On ne tient pas compte du dépassement avec cette méthode puisque l'addition de deux nombres négatifs provoque toujours un dépassement.

On constate un grave problème : l'addition des bits de la représentation de deux nombres négatifs donne un bit de signe à  0  ! L'ordinateur ne parvient donc pas à faire cette addition.

On retrouve le problème vu avec les nombres positifs.

Comment détecter le dépassement de capacité de calcul lors de l'addition de deux entiers négatifs ?

C'est "simple" : il y a dépassement de capacité si le bit de signe change de valeur.

Si on cherche un test de vérification, on pourrait écrire

  • ENTREES : a et b, deux entiers négatifs
  • On calcule et mémorise c = a + b
  • Si c est négatif
    • SORTIE : on renvoie True
  • Sinon
    • SORTIE : on renvoie False

02° On additionne un ensemble d'entiers négatifs sur 8 ou 16 bits.

Sans même savoir quels sont les deux entiers positifs, donner les numéros des cas où il y a visiblement eu dépassement de capacités.

  • 1 : 0101 0101 0101 0101
  • 2 : 1101 0101
  • 3 : 1111 1111 1111 1111
  • 4 : 0000 0001
  • 5 : 1000 0000

...CORRECTION...

Il suffit de chercher les résultats pour lesquels le bit de signe est devenu 0.

  • 1 : 0101 0101 0101 0101 : dépassement
  • 2 : 1101 0101 : ok
  • 3 : 1111 1111 1111 1111 : ok
  • 4 : 0000 0000 0000 0001 : dépassement
  • 5 : 1000 0000 : ok

Tout cela nous a permis de faire quelques révisions sur les additions et le complément à deux et on sait maintenant détecter les dépassements éventuels sur les additions. Mais comment les détecter sur les multiplications ? Comment savoir à l'avance qu'il faudra prendre un entier relatif (ou signé) sur 2, 4 ou 8 octets 

3 - Fonction logarithme base 10

Comment connaitre le nombre de chiffre nécessaire à l'écriture d'un nombre dans une base donnée ?

Pour cela, il suffit d'utiliser une fonction mathématique très connue et exploitée, la fonction logarithme.

Logarithme base 10

La fonction logarithme base 10 peut être vue en première approximation comme une fonction qui renvoie la puissance de 10 d'un nombre qu'on écrirait sous la forme N = 10 X.

Ainsi :

log10(0,01) = log10(10-2) = -2

log10(0,1) = log10(10-1) = -1

log10(1) = log10(100) = 0

log10(10) = log10(101) = 1

log10(100) = log10(102) = 2

La fonction logarithme est définie dans ℝ*+ , c'est à dire l'intervalle ] 0 ; +∞ ] .

On peut également rechercher des valeurs qui ne tombent pas juste. Par exemple pour 200 :

log10(200) = 2.3010299956639813...

Cela veut néanmoins dire qu'on peut écrire approximativement 

200 = 102.3010299956639813...

L'intérêt pour le traitement des nombres ? Cette fonction permet facilement de trouver le nombre de chiffres nécessaires pour écrire un nombre en base 10 !

Si on regarde bien :

1 + log10(100) = 1 + log10(102) = 1 + 2 = 3

Le nombre 10010 nécessite bien 3 chiffres en base 10.

On peut faire de même en ne prenant que la partie entière du résultat pour 200 

1 + int(log10(200)) = 1 + int(2.3010299956639813...) = 1 + 2 = 3 !

Ou même plus simplement

int(1 + log10(200)) = int(1 + 2.3010299956639813...) = 3 !

A l'aide d'une simple formule, on parvient donc à trouver que 20010 nécessite 3 chiffres pour s'écrire en base 10.

Voici donc à titre d'exemple une fonction Python utilisant le module math et permettant d'obtenir le nombre de chiffres nécessaires à l'écriture d'un nombre lorsqu'on l'écrit en base 10 

1 2 3 4 5 6 7 8 9 10 11 12 13
# 1 - Importation des modules nécessaires import math # 2 - Déclaration des fonctions def chiffres10(nombre) : '''Renvoie le nombre de chiffres nécessaires pour exprimer nombre en base 10 ::param nombre (int/float) :: Un nombre > 0 ::return (int) :: Le nombre de chiffres nécessaires en base 10 ''' return int(1 + math.log10(nombre))

03° Placer le programme précédent en mémoire dans Thonny ou simplement IDLE Python.

Utiliser ensuite le Shell pour vérifier que la fonction fonctionne avec quelques exemples.

Vous devriez pouvoir obtenir des résultats de ce type 

>>> chiffres_base10(200) 3 >>> chiffres_base10(2000) 4 >>> chiffres_base10(-2000) return 1 + int(math.log10(nombre)) ValueError: math domain error

04° Utiliser le code ci-dessous basé sur le module matplotlib. Il faudra peut-être l'importer dans Thonny. Visualiser les courbes obtenues en traçant la fonction log10 et le nombre de chiffres nécessaires.

Le code est fourni sans plus d'explications car une activité traitera du module matplotlib.

Pour importer un module dans Thonny, il faut aller dans le menu Tools - Manage Packages.

Si vous utilisez directement Python sans passer par Thonny, il est plus que propable que le module ne soit pas importé de base. Dans ce cas, ouvrir votre console Windows ou votre terminal Linux et taper ceci :

C:\Users\moi>python -m pip install --user matplotlib
rv@rv-HP2:~$ python3 -m pip install --user matplotlib
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
# 1 - Importation des modules nécessaires import math import matplotlib.pyplot as plt # 2 - Variables globales xmax = 150 # Valeur maximum du nombre à gérer # 3 - Déclaration des fonctions def chiffres_base10(nombre) : '''Renvoie le nombre de chiffres nécessaires pour exprimer nombre en base 10 ::param nombre (int/float) :: Un nombre > 0 ::return (int) :: Le nombre de chiffres nécessaires en base 10 ''' return int(1 + math.log10(nombre)) # 4 - Programme principal # Création des tableaux de données abscisse = [ valeur/10 for valeur in range(1, xmax*10) ] # Entiers, la borne inférieure doit être >= 1 valeurs_log = [ math.log10(x) for x in abscisse ] # Ordonnée nbr_chiffres = [ chiffres_base10(x) for x in abscisse ] # Ordonnée ymax = max(nbr_chiffres) + 1 # Création des courbes plt.plot(abscisse, valeurs_log, label="log10", color='orange') plt.plot(abscisse, nbr_chiffres, label="Nbr chiffres", color='red') plt.xlabel("Nombre") plt.ylabel("Log10 et nbr de chiffres") plt.title("Courbe du log10 pour en déduire le nombre de chiffres") plt.legend(loc='upper center') plt.axis([0, xmax, 0, ymax]) plt.grid() plt.show() # Affichage à l'écran des courbes

Vous devriez obtenir une application graphique proche de ceci

Log10
Log10

On constate bien qu'on a besoin

  • De 1 chiffre de 1 à 9
  • De 2 chiffres de 10 à 99
  • De 3 chiffres de 100 à 999
  • ...

4 - Fonction logarithme base 2

Comment connaitre le nombre de chiffre nécessaire à l'écriture d'un nombre en base 2 ?

La solution : la fonction logarithme base 2 !

Logarithme base 2

La fonction logarithme base 2 peut être vue en première approximation comme une fonction qui renvoie la puissance de 2 d'un nombre qu'on écrirait sous la forme N = 2 X.

Ainsi :

log2(0,25) = log2(2-2) = -2

log2(0,5) = log2(2-1) = -1

log2(1) = log2(20) = 0

log2(2) = log2(21) = 1

log2(4) = log2(22) = 2

La fonction logarithme est définie dans ℝ*+ , c'est à dire l'intervalle ] 0 ; +∞ ] .

On peut également rechercher des valeurs qui ne tombent pas juste. Par exemple pour 6 :

log2(6) = 2.584962500721156...

Cela veut néanmoins dire qu'on peut écrire approximativement 

6 = 22.584962500721156...

L'intérêt pour le traitement des nombres ? Cette fonction permet facilement de trouver le nombre de chiffres nécessaires pour écrire un nombre en base 2 !

Si on regarde bien :

1 + log2(4) = 1 + log2(22) = 1 + 2 = 3

Le nombre 410 nécessite bien 3 chiffres en base 2 :  100 2.

On peut faire de même en ne prenant que la partie entière du résultat pour 6 

int(1 + log2(6)) = int(1 + 2.584962500721156...) = int(3.584962500721156...) = 3 !

A l'aide d'une simple formule, on parvient donc à trouver que 610 nécessite 3 chiffres pour s'écrire en base 2 :  110 

Le module math contient la fonction log2 qui permet de calculer le log en base 2 de l'argument fourni.

05° Compléter le code de la fonction ci-dessous. Pour l'instant, la fonction renvoie toujours 300.

1 2 3 4 5 6 7 8 9 10 11 12 13
# 1 - Importation des modules nécessaires import math # 2 - Déclaration des fonctions def chiffres2(nombre) : '''Renvoie le nombre de chiffres nécessaires pour exprimer nombre en base 2 ::param nombre (int/float) :: Un nombre > 0 ::return (int) :: Le nombre de chiffres nécessaires en base 2 ''' return 300

06° Utiliser le code ci-dessous basé sur le module matplotlib. Il faudra peut-être l'importer dans Thonny. Visualiser les courbes obtenues en traçant la fonction log2 et le nombre de chiffres nécessaires.

Le code est fourni sans plus d'explications car une activité traitera du module matplotlib.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
# 1 - Importation des modules nécessaires import math import matplotlib.pyplot as plt # 2 - Variables globales xmax = 150 # Valeur maximum du nombre à gérer # 3 - Déclaration des fonctions def chiffres_base2(nombre) : '''Renvoie le nombre de chiffres nécessaires pour exprimer nombre en base 2 ::param nombre (int/float) :: Un nombre > 0 ::return (int) :: Le nombre de chiffres nécessaires en base 2 ''' return int(1 + math.log2(nombre)) # 4 - Programme principal # Création des tableaux de données abscisse = [ valeur/10 for valeur in range(1, xmax*10) ] # Entiers, la borne inférieure doit être >= 1 valeurs_log = [ math.log2(x) for x in abscisse ] # Ordonnée nbr_chiffres = [ chiffres_base2(x) for x in abscisse ] # Ordonnée ymax = max(nbr_chiffres) + 1 # Création des courbes plt.plot(abscisse, valeurs_log, label="log2", color='orange') plt.plot(abscisse, nbr_chiffres, label="Nbr chiffres", color='red') plt.xlabel("Nombre") plt.ylabel("Log2 et nbr de chiffres") plt.title("Courbe du log2 pour en déduire le nombre de chiffres") plt.legend(loc='upper center') plt.axis([0, xmax, 0, ymax]) plt.grid() plt.show() # Affichage à l'écran des courbes

Vous devriez obtenir une application graphique proche de ceci

Log10
Log2

On constate bien qu'on a besoin

  • De 1 chiffre de 0 à 1
  • De 2 chiffres de 2 à 3
  • De 3 chiffres de 4 à 7
  • De 4 chiffres de 8 à 15
  • ...

5 - Prévision des dépassements après multiplication

C'est maintenant que l'utilisation de la fonction logarithme prend tout son sens.

Nbr de bits THEORIQUEMENT nécessaires pour stocker a*b

La fonction logarithme possède la propriété suivante quelque soit la base utilisée :

log2(a*b) = log2(a) + log2(b)

On constate donc que la multiplication se transforme en addition de log.

Lors d'une multiplication, nous aurons donc ceci 

  • Pour le nombre a, le nombre Na de bits est : Na = int( 1 + log2(a) )
  • Pour le nombre b, le nombre Nb de bits est : Nb = int( 1 + log2(b) )
  • Pour le nombre a*b : Na*b = int( 1 + log2(a*b) ) = int( 1 + log2(a) + log2(b) ).

Si on considère le cas le plus favorable : Na*b = Na + Nb - 1

Si on considère le cas le plus défavorable : Na*b = Na + Nb

Bref, ce n'est pas si simple de prévoir à coup sur le nombre de bits qu'il faudra en connaissant juste le nombre de bits pour chacun des nombres de base...

Mais on peut faire plus simple !

Un moyen facile de vérifier si le résultat de la multiplication c = a * b est bon est de tester ceci pour b != 0 :

c / a == b

Si on cherche un test de vérification, on pourrait écrire

  • ENTREES : a et b, deux entiers, b étant non nul
  • On calcule et mémorise c = a * b
  • Si b == c // a
    • SORTIE : on renvoie True
  • Sinon
    • SORTIE : on renvoie False

07° Combien faut-il de bits pour stocker la valeur a = 100 en base 2 ? Répondre en non signé et en signé.

...CORRECTION...

10010 nécessite int(1 + math.log2(100)) chiffres en base 2.

Le calcul donne 7 chiffres.

C'est cohérent avec le fait que 27 donne 128.

Recherche de la décomposition avec 1-2-4-8-16-32-64 qu'on utilisera dans le sens 64-32-16-8-4-2-1:

  • On active 64. Il 100-64 = 36.
  • On active donc 32. Il reste 36-32 = 4.
  • On active 4.

La décomposition de 10010 sur 7 bits est donc 110 0100 2.

Pour un entier signé, il faudrait un bit supplémentaire pour le signe : 0110 0100 2

08° Combien faut-il de bits pour stocker la valeur b = 50 en base 2 ? Répondre en non signé et en signé.

...CORRECTION...

5010 nécessite int(1 + math.log2(50)) chiffres en base 2.

Le calcul donne 6 chiffres.

C'est cohérent avec le fait que 26 donne 64.

Recherche de la décomposition avec 1-2-4-8-16-32 qu'on utilisera dans le sens 32-16-8-4-2-1:

  • On active 32. Il 50-32 = 18.
  • On active donc 16. Il reste 18-16 = 2.
  • On active 2.

La décomposition de 5010 sur 6 bits est donc 11 0010 2.

Pour un entier signé, il faudrait un bit supplémentaire pour le signe : 011 0010

09° Si on considère qu'il faut 7 bits pour stocker la valeur 100 et 6 bits pour stocker la valeur 50, la multiplication risque-t-elle de créer un problème de dépassement sur 16 bits dans le cas d'un entier non signé ? dans un entier signé ?

...CORRECTION...

Pour stocker 500 = 100 * 50, il prendra donc 7 + 6, soit 13 bits pour un entier non signé.

S'il s'agit d'entiers signés, il faudra 14 bits.

Dans les deux cas, utiliser un octet (8 bits) provoquera un débordement.

Dans les deux cas, utiliser deux octets (16 bits) permet d'obtenir le résultat sans problème.

10° On travaille avec des entiers naturels (non signés) encodés sur 2 octets. Peut-on calculer 30000 * 200 ?

...CORRECTION...

1er réponse rapide si on peut calculer le nombre : 30000*200 = 6 000 000.

Or avec 16 bits, on ne peut aller que jusqu'à 216 -1 , soit 65535. La réponse est donc NON.

Si on ne peut pas calculer le résultat final ? Il suffit d'utiliser la formule.

L'encodage de 30000 nécessite 15 bits ( int(1 + math.log2(30000)) ou len(bin(30000)[2:]) ).

L'encodage de 200 nécessite 8 bits ( int(1 + math.log2(200)) ou len(bin(200)[2:]) ).

Stocker le résultat demande en gros 23 bits (15+8).

Voir 24 bits s'il s'agit d'entiers signés.

Sur 2 octets (16 bits), il y aura donc débordement de capacité.

Par contre, sur 4 octets (32 bits), le calcul ne posera pas problème.

Comme Python ne vous permet pas de gérer la taille de vos entiers, voici une courte fonction qui permet de simuler cela (en utilisant la manipulation des strings et les fonctions bin et int).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
def tronque(nombre, nombre_bits): '''Renvoie l'entier non signé décodé lorsqu'on ne gère qu'un nombre limité de bits ::param nombre(int) :: un entier > 0 ::param nombre_bits (int) :: un entier > 0 ::return (int) :: le résultat tronqué par le nombre de bits disponibles ''' bits = bin(nombre) bits = bits[2:] # Permet de supprimer le 0b du début if len(bits) > nombre_bits : calcul = '0b' + bits[-nombre_bits:] # On ne prend que qqs bits depuis la droite return int(calcul,2) else : return nombre

11° Mémoriser la fonction dans Thonny ou IDLE. Lancer les calculs suivants dans le Shell :

>>> tronque(10*10,8) >>> tronque(100*10,8)
Vérification PRATIQUE de non dépassement en cas de multiplication

Dans le cas d'entiers signés de même signe, on peut affirmer qu'il y a dépassement si l'entier obtenu n'a pas le même signe.

Dans le cas d'entiers non signés, on peut vérifier le non-dépassement éventuel de  c = a * b  en vérifiant que  a = c // b . Si on n'obtient pas le bon résultat, c'est que l'opération a provoqué un dépassement.

6 - Tronque et addition

Détection de dépassement par addition

La détection a déjà été vue dans le cas de nombres signés : il y a débordement si l'addition de deux nombres de même signe donnent un entier de signe différent.

L'addition de deux nombres de signes différents ne peut pas donner lieu à de dépassement du fait du mécanisme du complément à deux.

Dans le cas d'entiers non signés, on peut voir l'existence d'un dépassement si a+b est inférieur à a !

12° Mémoriser la fonction dans Thonny ou IDLE. Lancer les calculs suivants dans le Shell :

>>> tronque(250+100,16) >>> tronque(250+100,8)

Bien entendu, en Python ces vérifications sont inutiles puisque l'interpréteur se charge de tout. Mais avec d'autres langages, il va falloir mettre des fonctions de vérifications au point si vous voulez éviter les dysfonctionnements !

C'est le moment de signaler qu'il y a un ensemble d'équivalences de mots anglais-français dans la partie NSI, dans les articles.

Retenue en français donne Carry en anglais.

Dépassement en français donne Overflow.

Activité publiée le 22 10 2019
Dernière modification : 25 10 2019
Auteur : ows. h.