Mutiplication binaire qui beugue

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)

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é.

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).

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.

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

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 :).

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

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 .

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 ?

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