Discussion :

[LeFredd]

Bonjour,

Je ne comprend pas comment résoudre l'exercice 2.1.4 du livre introduction to algorithms de Cormen :

2.1-4
Consider the problem of adding two n-bit binary integers, stored in two n-element arrays A and B. The sum of the two integers should be stored in binary form in an (n+1) element array C . State the problem formally and write pseudocode for adding the two integers.

Déjà je ne comprend pas pourquoi le tableau C doit faire n + 1 element.

Ensuite j'ai trouvé cette solution mais qui ne m'éclaire pas du tout :

Input: An array of booleans A=⟨a1,a2,…,an⟩, an array of booleans B=⟨b1,b2,…,bn⟩, each representing an integer stored in binary format (each digit is a number, either 0 or 1, least-significant digit first) and each of length n.

Output: An array C=⟨c1,c2,…,cn+1⟩ that such that C′=A′+B′, where A′, B′ and C′ are the integers, represented by A, B and C

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
ADD-BINARY(A, B):
C = new integer[A.length + 1]
 
carry = 0
  for i = 1 to A.length
      C[i] = (A[i] + B[i] + carry) % 2  // remainder
      carry = (A[i] + B[i] + carry) / 2 // quotient
  C[i] = carry
 
return C

Je ne comprend pas pourquoi il se base sur la longueur du tableau A, car si A = 101 et B = 1001101 son code n'est pas bon. Dans l'énoncé il est juste spécifié que chacun de ces tableaux comporte n éléments et pas les 2 tableaux doivent comporter le même nombre d'éléments.

Si quelqu'un aurai la gentillesse de m'expliquer

[yahiko]

Exercice utile pour comprendre la représentation des nombres dans un ordinateur et pour implémenter les calculs en précision arbitraire.

[dourouc05]

Déjà je ne comprend pas pourquoi le tableau C doit faire n + 1 element.

Réfléchis déjà en base 10 : la somme de deux nombres à un chiffre donne un nombre au plus à deux chiffres. Le pire cas : 9 + 9 = 18. Même chose en binaire : 1 + 1 = 10. Conclusion : la déclaration du tableau de bits de la solution que tu as trouvée est fausse, à moins d'ajouter l'hypothèse que A est le plus grand des deux nombres en entrée.

[Flodelarab]

Bonjour,

car si A = 101

A ne sera pas égal à cela car A est un tableau de taille n. Il représente le nombre A'. Si tu tiens absolument à utiliser A plutôt que A' alors A=0000101 et B=1001101 et du coup, plus de problème de taille de tableau.

[LeFredd]

Merci pour votre aide mais C a n + 1 élément ne me parle qu'à moitié.

Flodelarab

A ne sera pas égal à cela car A est un tableau de taille n. Il représente le nombre A'

oui je voulais dire A = [1, 0, 1]

Maintenant je ne fais que suivre l'exercice et il faut que j'additionne ces 2 tableaux A et B. Je suis tout a fais d'accord pour avoir un tableau A qui soit A = [0, 0, 0, 1, 0, 1] pour avoir la même longueur que B

Voici ma compréhension du problème :

-Il faut additionner deux entiers en représentation binaire qui sont stockés sur n bits.

un entier A' stocké sur n bits = 110
un entier B' stocké sur n bits = 101100

-Ils sont rangés dans deux tableaux A et B à n éléments.

A = [1, 1, 0]
B = [1, 0, 1, 1, 0, 0]

-La somme des deux entiers doit être stockée sous forme binaire dans un tableau C à n + 1 éléments.

A' + B' = C'

110 + 101100 = 110010

C' = 110010

C = [n, n, … n+1 ]

donc :

C = [1, 1, 0, 0, 1, 0, ?] // ? = n+1

Par contre je ne vois pas du tout comment faire pour l'algorithme
Déjà comment faire pour stocker mes 2 entiers dans des tableaux tout en n'oubliant pas de mettre des 0 dans les premières cases de A pour rattraper la longueur de B ?

Des pistes ? Merci

[Flodelarab]

Tu as l'air fâché avec lez zéros inutiles. Quand, à gauche de l'écriture de ton nombre, tu ne sais pas quoi mettre, tu peux toujours mettre un zéro. Que ce soit dans A ou C.

Après, la réponse de dourouc05 est excellente. Tu sembles oublier la retenue. 9+9=18. 1111₂ + 1111₂ = 11110₂. Il y a plus de chiffres dans les sommes que dans les termes.

[LeFredd]

Non je ne suis pas faché avec les 0 en plus

C'est juste que si on imagine une fonction qui prendrait en argument 2 tableaux A et B de longueur n, on peut imaginer qu'on récupère ces 2 tableau d'un système tiers, et que ces 2 tableaux à la base n'aient pas la même longueur n. Donc comme dans mon exemple :

A = [1, 1, 0]
B = [1, 0, 1, 1, 0, 0]

Maintenant moi en tant que programmeur, pour les additionner et mettre le résultat dans un tableau C sous la même forme (un bit par case), il faudrait que mes 2 tableaux est la même longueur donc effectivement en rajoutant des 0 (ici au tableau A: A = [0, 0, 0, 1, 1, 0])

Mais déjà comment faire ça en algo ?

Et pour ce fameux tableau C pourquoi avoir besoin de préciser n + 1 ? On s'en fiche, les additions des cases des 2 tableaux viendront nourrir le tableau C donc sa taille c'est pas grave de ne pas la connaitre au départ, et pour les retenues : une variable qui les retienne et qu'on ajoute à la prochaine addition.

Maintenant c'est pour mettre tous ça en algo, je ne vois pas trop par ou commencer ni comment m'y prendre, je suis débutant.

[yahiko]

Imagine toi en taille fixe. C'est comme ça que cela se passe dans la machine.

[Flodelarab]

+1. Soit tu alloues de la mémoire, soit tu n'en alloues pas. Mais si tu n'en réserves pas, tu ne pourras pas faire ton calcul sereinement.

Les "tiroirs" dans lesquels tu places tes chiffres (0, 1 ou indéfini) existent! Indépendamment de savoir ce qu'il y a dedans. Donc, ici, n+1 tiroirs dans la commode C.

[yahiko]

Enfin, il serait plus clair de dire que cet exercice est une analogie avec le fonctionnement de l'additionneur dans le processeur.

Les variables A et B doivent être vues comme les registres ayant un nombre fixes et prédéterminés de bits (par exemple 16 bits, 32 bits, etc) et il existe un bit au sein de l'unité arithmétique et logique (UAL) pour la gestion de la retenue (carry over). D'où le "+1" dans "n+1".

Si on a à disposition des registres (variables) de 16 bits, il est donc possible d'additionner deux nombres ayant jusqu'à 15 bits significatifs sans perdre d'information.

[LeFredd]

Ok je comprend un peu mieux.
Donc si je reprend ton analogie, mes 2 tableaux de bits A et B en entrée, (en principe ) auront une taille identique par exemple de 16bits.

Donc pour cet exercice les nombres A' et B', sans prendre des nombres de 16 bits car je préfère faire court, pourront être :

un entier A' stocké sur n bits = 110111
un entier B' stocké sur n bits = 101100

Effectivement ils sont tous deux égaux en taille. Ils sont donc stockés dans tableau de n bits

A = [1, 1, 0, 1, 1, 1]
B = [1, 0, 1, 1, 0, 0]

-La somme des deux entiers doit être stockée sous forme binaire dans un tableau C à n + 1 éléments.

A' + B' = C'

110111 + 101100 = 1100011

C' = 1100011

C = [n, n, … n+1 ]

donc :

C = [1, 1, 0, 0, 0, 1, 1 ]

Je vais tenter de reprendre la correction que j'ai trouvé pour m'aider à avancer :

Le début je suis d'accord :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
37
38
39
40
 
ADD-BINARY(A, B):
C = new integer[A.length + 1]   // sauf ici pourquoi new integer ? On passe bien en argument 2 tableaux dont la somme doit être un tableau C et non un integer, j'aimerai comprendre cette syntaxe
 
Par contre la suite :
 
carry = 0
// C'est la retenue ?
 
  for i = 0 to A.length
      C[i] = (A[i] + B[i] + carry) % 2  // remainder
      // Première boucle :
      // C[0] = (A[0] + B[0] + 0) % 2    // 10 % 2 = 0
      // Donc C[0] = 0
 
      carry = (A[i] + B[i] + carry) / 2 // quotient
      // carry = (A[0] + B[0] + carry) / 2
      // Donc carry = 0
 
  C[i] = carry  // Je ne comprend pas ici, on est encore dans la boucle ? Si oui alors C[0] = 0 puis on reprend à for i = 1
 
Je continue la boucle :
2ème passage :
 
for i = 1 to A.length 
      C[i] = (A[i] + B[i] + carry) % 2  // remainder
      // 2ème boucle :
      // C[1] = (A[1] + B[1] + 0) % 2    // 1 % 2 = 1
      // Donc C[1] = 1
 
      carry = (A[i] + B[i] + carry) / 2 // quotient
      // carry = (A[1] + B[1] + 0) / 2       // 1 / 2 = 0,5  
 
     // Donc carry = 0,5 !!! L' algo est mort ??? Ou c'est ma compréhension qui faille ? Je doute qu'en binaire 1 / 2 donne ce résultat
 
  C[i] = carry  // Si on continue alors C[1] = 0,5 puis on reprend à for i = 2
 
...
Quand j'aurai compris cet algo je pourrai retourner C
return C

Une petite aide serait la bien venue

[yahiko]

Quand on représente des nombres, que ce soit à l'écrit ou dans une machine, il est important de connaître le sens de lecture.
Si X est un tableau représentant un nombre décimal à trois chiffres tel que X = [4, 7, 1], cela peut être interprété de deux façons.
Soit on considère que X = 471, car on considère que dans le tableau le chiffre de poids fort (les centaines) est en tête.
Soit on considère que X = 174, car on considère que dans le tableau le chiffre de poids faible (les unités) est en tête.

En représentation binaire, c'est la même chose. Il faut savoir dans quelle convention on se place.
En regardant la fonction ADD-BINARY, la boucle parcourant le tableau des digits est croissante. Le premier digit du tableau étant le premier digit à être additionné.
Autrement dit, les nombres A et B de ton exemple doivent être interprétés "à l'envers".

A = [1, 1, 0, 1, 1, 1] ==> 111011 en notation usuelle (59).
B = [1, 0, 1, 1, 0, 0] ==> 001101 en notation usuelle (13).

A + B = C = [0, 0, 0, 1, 0, 0, 1] ==> 1001000 en notation usuelle (72=59+13).

Quand au pseudo-code voici quelques précisions,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
carry = 0 // retenue
 
for i = 1 to A.length // parcours des n digits de A et B du poids le plus faible i=0 au poids le plus fort i=n-1
      C[i] = (A[i] + B[i] + carry) % 2  // modulo 2
      carry = (A[i] + B[i] + carry) / 2 // division ENTIERE par 2
 
C[i] = carry // le dernier (n+1 ième) bit (le poids le plus fort) est égal à la retenue

[LeFredd]

Merci beaucoup yahiko, donc j'ai compris que pour effectuer cette addition et retourner le tableau C, il faut que les tableaux A et B soient d'abord triés à l'envers, puis effectuer l'addition pour obtenir le tableau C qu'il faudra mettre à l'endroit pour obtenir le résultat. Est ce qu'il faut inclure le tri des tableaux (endroit -> envers pour A et B) puis (envers -> endroit pour C) au sein de l'algo ? Sinon à quel moment.

Pour l'addition binaire il faut que je me fasse à l'idée d'utiliser le modulo 2 et la division 2, c'est un peu déroutant. Est ce une convention pour ce genre de cas ?

Merci.

[yahiko]

Le plus simple est de tout considérer dans l'ordre inversé. C'est à dire, définir dès le départ A et B de façon à ce qu'ils soient interprétés correctement dans l'algo.
Pour avoir la valeur décimale pour te rassurer, tu peux implémenter une autre fonction qui prend un nombre binaire (tableau) en paramètre et renvoie sa valeur décimale. Ca peux te faire un bon exo d'ailleurs.

[LeFredd]

Ok je vais continuer à travailler là dessus.

Merci pour tous vos conseils