Mutiplication binaire qui beugue

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour à tous,

J'ai écrit un algo qui multiplie deux nombres entiers non-signés et < 256 en se basant sur leur forme binaire. Il n'utilise que des opérations binaires comme le décalage de bits, etc.

Mon algo fonctionne (vous pouvez le lancer en ligne, cf. un peu plus bas), mais pas pour certains nombres. Quelques exemples de ce qu'il retourne :

  • 0*0 = 0 donc OK

  • 1*15 = 15 OK

  • 88*2 = 176 OK

  • 17*7 = 119 OK

  • 255*255 = 32767 PAS BON

  • 255*10 = 2046 PAS BON

  • 15*15 = 127 PAS BON

  • 1*255 = 255 OK

Vous pouvez le tester en ligne (notez qu'une archive des sources est disponible à la fin de ce message) : http://goo.gl/NZFuOT (compilez et exécutez, boutons en haut à gauche). (bug résolu)

Je ne vois vraiment pas d'où peut venir le problème. Le pire c'est que j'ai lancé mon débogueur, et je n'ai rien détecté d'anormal : mon programme semble faire exactement ce que je lui dis de faire et ne fait pas une action que je n'avais pas prévue.

EDIT : même les calculs simples (88*2) effectués sur le site juste au-dessus ne sont pas bons… mais sur mon ordi ils sont bel et bien OK.

Les types de variables seraient-ils mis en cause ?

Merci d'avance !

Voici mon code.

 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <stdio.h>

void typeTwoIntegers(unsigned int*, unsigned int*);
int getBitTheMostAtRight(unsigned int);

const int number_of_bits_in_4_octets = sizeof(unsigned int)*8; // Un unsigned int est codé sur 4 octets donc possède 4*8 = 32bits

int main(){
    unsigned int op1 = 0, op2 = 0, original_op2_value;
    typeTwoIntegers(&op1, &op2); // Affecte les valeurs à op1 et à op2
    original_op2_value = op2; // op2 sera amené à changer de valeur (à cause de décalages de bits)

    unsigned int array_temporary_products[sizeof(unsigned int)*8]; // Cet array contiendra les produits intermédiaires
    unsigned int op1_copy = 0;
    int i = 0;
    for (i = 0; i < number_of_bits_in_4_octets; i++) {
        int tmp_bit = getBitTheMostAtRight(op2);
        if (tmp_bit == 1) { // Si le bit le plus à droite de op2 est un 1, on inscrit op1 dans le tableau des produits intermédiaires sinon on écrit 0
            // Il faut décaler les bits de ce produit intermédiaire (sauf ceux du premier : i=0 donc pas de décalage) (toujours afin de "simuler" un produit fait à la main)
            op1_copy = op1 << i;
            array_temporary_products[i] = op1_copy;
        }
        else {
            array_temporary_products[i] = 0;
        }

        op2 >>= 1; // On décale les bits d'op2 d'une position (ie. : d'un seul bit) ("simuler" un produit fait à la main)
    }


    // Maintenant qu'on a effectué les décalages nécessaires, on va pouvoir calculer le résultat final.
    unsigned int array_temporary_additions_and_final_result[sizeof(unsigned int)*8]; //  Cet array contiendra les additions intermédiaires (cf. la suite du code) et, en guise de dernier élément, le résultat final.

    for (i = 0; i < number_of_bits_in_4_octets; i++) {
        if (i == 0) { // Première itération : la première addition intermédiaire est égale aux deux premiers produits intermédiaires additionnés entre eux
            array_temporary_additions_and_final_result[i] = (array_temporary_products[i] + array_temporary_products[i + 1]);
        }
        else { // Les autres additions intermédiaires sont égales à l'addition intermédiaire qui vient tout juste d'être effectuée + le produit intermédiaire suivant
            if (i + 1 < number_of_bits_in_4_octets) {
                // Il ne faut pas aller plus loin que la 32-ième case d'`array_temporary_products` (cf. commentaire suivant)
                array_temporary_additions_and_final_result[i] = (array_temporary_additions_and_final_result[i - 1] + array_temporary_products[i + 1]);
            }
            else {
                // (cf. commentaire précédent) Si pourtant c'est le cas, on affecte à la 32-ième case d'array_temporary_additions_and_final_result le résultat du produit
                array_temporary_additions_and_final_result[i] = (array_temporary_additions_and_final_result[i - 1]);
            }
        }
    }

    printf("Le produit de %u et %u est : %u", op1, original_op2_value, array_temporary_additions_and_final_result[i-1]); // i-1 car i = sizeof(unsigned int)*8 puisque situé après la boucle !

    return 0;
}

int getBitTheMostAtRight(unsigned int val) {
    return val & 1;
}

void typeTwoIntegers(unsigned int* op1, unsigned int* op2) {
    do {
        printf("\n");
        printf("Saisissez la première opérande : \n");
        scanf("%u", op1);
        printf("Saisissez la dernière opérande : \n");
        scanf("%u", op2);
        printf("\n");
    } while (*op1 >= 256 || *op2 >= 256);
}

Archive des sources

  1. Premier code source : http://goo.gl/SsCcgr

  2. 2-ième code source : http://goo.gl/RmL6tY (modifications par-rapport à la version précédente : code plus compact, lisible et optimisé niveau rapidité d'exécution)

  3. Dernier code-source : http://goo.gl/NZFuOT (modifications par-rapport à la version précédente : correction du bug en procédant à des additions décimales au lieu de OU logiques, commentaires mis-à-jour)

Édité par The-Aloha-Protocol

Université de Bretagne-Sud <3

+0 -0

Cette réponse a aidé l'auteur du sujet

Bonjour,

Tu as sizeof(unsigned int)*8 qui traîne vraiment partout, ça pourrait être intéressant d'en faire une constante histoire de rendre le code un peu plus lisible et que l'on sache directement ce que ça représente.

De même, il ne serait pas plus de remplacer (val & 1) == 1 ? 1 : 0 par val & 1?

Tu utilises une variable différente pour chaque boucle, pourquoi?

Est-ce qu'il est vraiment utile d'initialiser ton tableau array_temporary_unsigned_int plutôt que de mettre soit 0 soit op1 dans ta deuxième boucle?

Dans ta boucle ligne 33, pourquoi ne pas aller de 1 à sizeof(unsigned int)*8 plutôt que de toujours mettre k+1. Du coup, ça devrait rendre ta condition inutile (elle l'est d'ailleurs déjà probablement). Au passage, il n'est pas forcément utile d'éviter le cas k=0 puisque le décalage ne fera rien. Ça rendra ton code plus simple (toutes les boucles de 0 à sizeof(unsigned int)*8) et le compilateur simplifiera de toute manière très probablement.

Ligne 42 : encore une fois, pourquoi initialiser ton tableau si tu le remplis directement après?

Finalement, de ce que j'ai vu, il est plus que probable que l'erreur se situe dans ta dernière boucle. En effet, tu fais un OU qui te donnera 1 si tu as 1 et 1 au lieux de 10. D'ailleurs, ton calcul ne correspond pas à ce qui est fait à la main : on fait l'addition colonne par colonne en gardant une retenue. Il te faut donc deux boucles (et une retenue).

Globalement, ton code pourrait être très fortement simplifié. Le calcul de array_temporary_unsigned_int peut être simplifié en une unique boucle. L'addition finale devrait, elle, se faire en deux boucles imbriqués.

Edit : autrement, pour l'addition finale, tu peux aussi te contenter d'additionner tous les éléments de array_temporary_unsigned_int si tu n'as pas trop envie de t'embêter.

Édité par Berdes

+1 -0

Cette réponse a aidé l'auteur du sujet

Salut.

Quand tu as un bug de ce genre, ton premier réflexe doit être de vérifier si tu n'as pas de comportement indéfini quelque part. En l'occurrence, valgrind me dit ceci pour ton programme (uniquement si les optimisations sont désactivées, pense donc à réaliser tes tests sans celles-ci, pour éviter de cacher des comportements indéfinis) :

1
2
3
4
5
6
7
Use of uninitialised value of size 8
  at 0x4E753AB: _itoa_word (in /usr/lib/libc-2.22.so)
  by 0x4E78AA2: vfprintf (in /usr/lib/libc-2.22.so)
  by 0x4E7FDA8: printf (in /usr/lib/libc-2.22.so)
  by 0x400835: main (main.c:57)
Uninitialised value was created by a stack allocation
  at 0x400560: main (main.c:6)

Après un peu plus de recherche, on se rend compte que cela vient de ton accès à array_results[z-1] dans le printf. Je te recommande de chercher l'origine précise du problème avec un débugger.

De plus, ton algorithme ne prend pas en compte l'endianness, cela peut être la cause des valeurs fausses. Dernier détail : attention aux comparaisons signé/non signé dans tes boucles.

Mon Github | Mantra : Un Entity-System en C++

+1 -0

Quand tu as un bug de ce genre, ton premier réflexe doit être de vérifier si tu n'as pas de comportement indéfini quelque part.

Praetonus

Je suis clairement pas d'accord avec ça. Le premier réflexe est de vérifier que la logique du code est bonne (et ce n'est pas le cas ici). D'autant que le bug n'est pas du tout aléatoire : sur certaines valeurs, ça fonctionne et sur d'autres, ça ne fonctionne pas, mais on obtient toujours le même résultat. Le bug est parfaitement reproductible, ce qui ne colle pas bien avec un comportement indéterminé.

De plus, ton algorithme ne prend pas en compte l'endianness, cela peut être la cause des valeurs fausses. Dernier détail : attention aux comparaisons signé/non signé dans tes boucles.

Praetonus

La norme C spécifie que l'utilisation des opérateurs bits à bits camoufle l'endianness de l'hôte. Lorsque tu fais 1 << 2, tu obtiens toujours 4, que tu sois sur une machine big-endian, little-endian ou wtf-endian. Il faut faire attention à l'endianness lorsque tu récupères uniquement une partie d'une variable, par exemple quand tu fais *((char*)&a) lorsque a est plus grand qu'un char (un int par exemple).

+0 -0

Je suis clairement pas d'accord avec ça. Le premier réflexe est de vérifier que la logique du code est bonne (et ce n'est pas le cas ici). D'autant que le bug n'est pas du tout aléatoire : sur certaines valeurs, ça fonctionne et sur d'autres, ça ne fonctionne pas, mais on obtient toujours le même résultat. Le bug est parfaitement reproductible, ce qui ne colle pas bien avec un comportement indéterminé.

Berdes

Ok, j'ai peut être pris un raccourci ici, mais il n'empêche qu'il s'agit bien d'un comportement indéterminé. Le programme compilé sans optimisations (avec clang et gcc) donne un résultat aberrant pour toutes les valeurs et fait hurler valgrind.

La norme C spécifie que l'utilisation des opérateurs bits à bits camoufle l'endianness de l'hôte. Lorsque tu fais 1 << 2, tu obtiens toujours 4, que tu sois sur une machine big-endian, little-endian ou wtf-endian. Il faut faire attention à l'endianness lorsque tu récupères uniquement une partie d'une variable, par exemple quand tu fais *((char*)&a) lorsque a est plus grand qu'un char (un int par exemple).

Berdes

Au temps pour moi, j'aurai appris quelque chose aujourd'hui.

Mon Github | Mantra : Un Entity-System en C++

+0 -0
Auteur du sujet

Bonjour,

Tu as sizeof(unsigned int)*8 qui traîne vraiment partout, ça pourrait être intéressant d'en faire une constante histoire de rendre le code un peu plus lisible et que l'on sache directement ce que ça représente.

De même, il ne serait pas plus de remplacer (val & 1) == 1 ? 1 : 0 par val & 1?

Tu utilises une variable différente pour chaque boucle, pourquoi?

Est-ce qu'il est vraiment utile d'initialiser ton tableau array_temporary_unsigned_int plutôt que de mettre soit 0 soit op1 dans ta deuxième boucle?

Dans ta boucle ligne 33, pourquoi ne pas aller de 1 à sizeof(unsigned int)*8 plutôt que de toujours mettre k+1. Du coup, ça devrait rendre ta condition inutile (elle l'est d'ailleurs déjà probablement). Au passage, il n'est pas forcément utile d'éviter le cas k=0 puisque le décalage ne fera rien. Ça rendra ton code plus simple (toutes les boucles de 0 à sizeof(unsigned int)*8) et le compilateur simplifiera de toute manière très probablement.

Ligne 42 : encore une fois, pourquoi initialiser ton tableau si tu le remplis directement après?

Finalement, de ce que j'ai vu, il est plus que probable que l'erreur se situe dans ta dernière boucle. En effet, tu fais un OU qui te donnera 1 si tu as 1 et 1 au lieux de 10. D'ailleurs, ton calcul ne correspond pas à ce qui est fait à la main : on fait l'addition colonne par colonne en gardant une retenue. Il te faut donc deux boucles (et une retenue).

Globalement, ton code pourrait être très fortement simplifié. Le calcul de array_temporary_unsigned_int peut être simplifié en une unique boucle. L'addition finale devrait, elle, se faire en deux boucles imbriqués.

Edit : autrement, pour l'addition finale, tu peux aussi te contenter d'additionner tous les éléments de array_temporary_unsigned_int si tu n'as pas trop envie de t'embêter.

Berdes

Salut Berdes,

Je viens de mettre à jour mon code-source en tenant compte de tes remarques. C'est sûr qu'il est bien plus lisible, maintenant ! Le nouveau code est accessible dans l'OP (j'ai mis l'ancien en archive, dans l'OP, juste au cas où).

Je n'ai pas compris la nécessité d'une retenue dans le cadre des opérations bits à bits. Certes, 18x2 en requiert une (2x8=16 je retiens 1, etc.). Mais pourquoi en avoir besoin dans un OU logique ? Je ne vois pas non plus pourquoi il faudrait un for imbriqué.

Je vais faire à la main, en suivant mon algo, les calculs qui ne retournent pas le résultat escompté. Je verrai mieux ce qui cloche dans mon programme.

Je te tiens au courant ! Cependant, si tu en as le temps et l'envie, n'hésite pas à me donner un autre coup de pouce dès maintenant :).

Bonjour.

1
while (*op1 >= 265 || *op2 >= 256);

Il n'y aurait pas une erreur ici ? C'est 265 ou 256 qui doit être inférieur ou égal à la valeur pointée par op1 ?

30b830e7

Salut, oui en effet c'est bien 256 mais ce n'est pas du tout le problème ! :)

Salut.

Quand tu as un bug de ce genre, ton premier réflexe doit être de vérifier si tu n'as pas de comportement indéfini quelque part. En l'occurrence, valgrind me dit ceci pour ton programme (uniquement si les optimisations sont désactivées, pense donc à réaliser tes tests sans celles-ci, pour éviter de cacher des comportements indéfinis) :

1
2
3
4
5
6
7
Use of uninitialised value of size 8
  at 0x4E753AB: _itoa_word (in /usr/lib/libc-2.22.so)
  by 0x4E78AA2: vfprintf (in /usr/lib/libc-2.22.so)
  by 0x4E7FDA8: printf (in /usr/lib/libc-2.22.so)
  by 0x400835: main (main.c:57)
Uninitialised value was created by a stack allocation
  at 0x400560: main (main.c:6)

Après un peu plus de recherche, on se rend compte que cela vient de ton accès à array_results[z-1] dans le printf. Je te recommande de chercher l'origine précise du problème avec un débugger.

De plus, ton algorithme ne prend pas en compte l'endianness, cela peut être la cause des valeurs fausses. Dernier détail : attention aux comparaisons signé/non signé dans tes boucles.

Praetonus

Ok, je vais voir du côté de ce printf.

Edit important :

Je viens de faire 5x5 en binaire à la main et j'obtiens 21, comme mon programme. Donc en fat je ne sais pas multiplier des suites de bits… Quelqu'un serait-il disposé à m'expliquer comment faire ? Je ne vois pas pourquoi il faut une retenue…

J'ai compris ! Ce n'est pas du tout des OU que je dois faire avec les produits intermédiaires, mais des additions, et par ailleurs comme 1+1=0 avec une retenue, il faut que je tienne compte de cette dernière. Je vais voir comment mettre ça en place :) .

Édité par The-Aloha-Protocol

Université de Bretagne-Sud <3

+0 -0
Auteur du sujet

Re tout le monde,

J'ai finalement décidé de ne pas réinventer la roue, et ainsi d'additionner tous les produits intermédiaires entre eux avec leur forme décimale (une fois les décalages de bits effectués). J'aurais peut-être pu faire ça en additionnant directement les bits (donc en manipulant leur forme binaire), avec un système de retenue, etc. mais ça me semble long et fastidieux.

Le nouveau code-source est disponible dans l'OP, dites-moi s'il vous semble bien écrit. :)

J'ai quand même une petite question à vous poser… J'ai réservé la 32-ième case de mon tableau contenant les additions intermédiaires pour le résultat final (le produit, donc). Est-ce que vous trouvez ça bon ? Je pars du principe que la 32-ième case ne peut pas servir à stocker une addition intermédiaire, puisque les deux opérandes de la multiplication sont codées sur 32bits. S'il existait une 32-ième addition intermédiaire, ça voudrait dire, si je ne m'abuse, que l'opérande-multiplicatrice serait codée sur 33bits. Mais ce n'est pas le cas ! Du coup la 32-ième case serait toujours inutilisée, donc autant y placer quelque chose d'utile, comme le résultat final de la multiplication.

Qu'en pensez-vous ?

Édité par The-Aloha-Protocol

Université de Bretagne-Sud <3

+0 -0

Cette réponse a aidé l'auteur du sujet

Le code est en effet beaucoup mieux, mais pourrait sans problèmes être encore simplifié.

Par exemple, quel est l'intérêt de op1_copy puisque tu ne l'utilises qu'une seul fois et que sa valeur est aussi rapide à écrire que son nom.

De même, la fonction getBitTheMostAtRight est sincèrement largement assez courte pour pouvoir être intégré dans le code, d'autant qu'elle n'est appelé qu'à un seul endroit.

Il est aussi possible de ne pas modifier op2 dans ta première boucle ;)

Finalement, est-ce que tu conserves les résultats intermédiaires des additions volontairement? Si ce n'est pas le cas, tu pourrais très bien avoir une variable dans laquelle tu peux ajouter au fur et à mesure les résultats des multiplications intermédiaires.

+1 -0
Auteur du sujet

Le code est en effet beaucoup mieux, mais pourrait sans problèmes être encore simplifié.

Par exemple, quel est l'intérêt de op1_copy puisque tu ne l'utilises qu'une seul fois et que sa valeur est aussi rapide à écrire que son nom.

De même, la fonction getBitTheMostAtRight est sincèrement largement assez courte pour pouvoir être intégré dans le code, d'autant qu'elle n'est appelé qu'à un seul endroit.

Il est aussi possible de ne pas modifier op2 dans ta première boucle ;)

Finalement, est-ce que tu conserves les résultats intermédiaires des additions volontairement? Si ce n'est pas le cas, tu pourrais très bien avoir une variable dans laquelle tu peux ajouter au fur et à mesure les résultats des multiplications intermédiaires.

Berdes

Pas faux du tout, je modifierai le code un peu plus tard :) !

Université de Bretagne-Sud <3

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte