Discussion :

[Emcy]

La methode est bonne. C'est juste qu'il faut utiliser un buffer de 16 bits pour le calcul et ne pas "tronquer" les chiffres de droite lors des décalages de bits.

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
 
1234 * 2.833 <=> 10011010010 * 10.1101010100111111
 
                     ---  16bits  ---
                     1234567890123456
--------------------------------------
10011010010 << 1  =  10011010010     | 39488
10011010010 >> 1  =    10011010010   | 9872
10011010010 >> 2  =     10011010010  | 4936
10011010010 >> 4  =       1001101001 | 1234
10011010010 >> 6  =         100110100| 308
10011010010 >> 8  =           1001101| 77
10011010010 >> 11 =              1001| 9
10011010010 >> 12 =               100| 4
10011010010 >> 13 =                10| 2
10011010010 >> 14 =                 1| 1
10011010010 >> 15 =                  | empty -> stop
 
Total             =  1101101001111011
Division par 16   =  110110100111.1011 = 3495.6875

=> j'avais bien compris le fait de faire le decallage avant de faire le traitement : c'est ce que j'ai fait dans la deuxieme solution de mon avant dernier poste (a part que je n'ai utilisé que 12 bit au lieu de 16).
=> la precision du resultat depend donc de la taille du buffer utilisé ... le problème est que je vois comment pour faire calculer la précision du résultat


scr, je ne vois pas pourquoi diviser par 6 simplifie les choses (ce n'est pas un multiple de puissance de 2). De plus avec ta solution, cela imposse d'avoir un buffer de taille plus grande (car au depart, tu multiplies par 17 au lieu de 2 avec l'autre solution => si le resultat peut etre contenu dans le buffer, alors on peut forcement faire le calcul; ce qui n'est pas le cas avec ta solution)...

[pseudocode]

c'est ce que j'ai fait dans la deuxieme solution de mon avant dernier poste

Oui, tout a fait. Mon post etait en réponse a celui de scr et son exemple de calcul "n=1".

[scr]

ok d'accord et merci pour ces explications
si j'ai bien tout compris il faut:
- utiliser un buffer 16 bits au lieu de 8 pour le calcul
- prétraiter le résultat en le multipliant par 16

pour ce qui est de la solution en multipliant par 17 et divisant par 6, et ben oui on multiplie par 17 et cela risque de déborder du buffer mais dans l'autre on multiplie bien par 16

pour ce qui est de l'erreur a mon avis elle est au maximum a la valeur du dernier bit du buffer soit 1/16 si on prétraite le résultat en le multipliant par 16 (en négligeant l'erreur faite sur le codage en format binaire du mutiplicateur)

[pseudocode]

ok d'accord et merci pour ces explications
si j'ai bien tout compris il faut:
- utiliser un buffer 16 bits au lieu de 8 pour le calcul
- prétraiter le résultat en le multipliant par 16

Heu... non. On ne fait pas de pré-multiplication par une constante.

La division par 16 dans mon exemple vient du fait que le nombre "1234" fait 11 bits de long et que le multiplieur "2.833" necessite un décalage de 1 bit a gauche. Comme le buffer fait 16 bits, les nombres binaires sont décalés de 16-(11+1)=4 bits à gauche. Donc a la fin, il faut faire un décalage de 4 bits a droite (d'ou la division par 2^4=16).

Le décalage final a effectuer est: TailleBuffer - (TailleNombre + DécalageMax)

Exemple pour "n=1":

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
1 * 2.833 <=> 1 * 10.1101010100111111
 
           ---  16bits  ---
           1234567890123456
----------------------------
1 << 1  =  1               | 32768
1 >> 1  =    1             | 8192
1 >> 2  =     1            | 4096
1 >> 4  =       1          | 1024
1 >> 6  =         1        | 256
1 >> 8  =           1      | 64
1 >> 11 =              1   | 8
1 >> 12 =               1  | 4
1 >> 13 =                1 | 2
1 >> 14 =                 1| 1
1 >> 15 =                  | empty -> stop
----------------------------
Total   =  1011010101001111 = 46415
 
Shift = 16-(1+1) = 14 
 
Résult (binaire) = 10.11010101001111 
Résult (decimal) = 46415 / 2^14 = 2.83294677734375

[scr]

ok, quand je disais multiplier par 16 je sous entendais decage de bits mais encore merci pour ces precisions, je n'avais pas vu qu'en plus le decalage était paramétré en fonction de la taille de la valeur a multiplier.

je suppose que l'intérêt de cette solution est sa rapidité d'execution par rapport à une multiplication puis une division ?

en tout cas multiplier par 16 et faire un décalage de 4 bits, le résultat est le même on risque de deborder du buffer de 4 bits...

[pseudocode]

je suppose que l'intérêt de cette solution est sa rapidité d'execution par rapport à une multiplication puis une division ?

C'est surtout que c'est un algo simple pour multiplier deux décimaux sans passer par la représentation IEEE 754.

en tout cas multiplier par 16 et faire un décalage de 4 bits, le résultat est le même on risque de deborder du buffer de 4 bits...

Oui, au pire tu va déborder de 1 bit (a gauche) lors de l'addition et obtenir un résultat sur 17 bits.

Tu peux détecter ce cas au moment de l'addition et faire un décalage de 1 bit a droite de tout le buffer pour te retrouver sur 16 bits (penser a réduire de 1 le shift final).

[scr]

C'est surtout que c'est un algo simple pour multiplier deux décimaux sans passer par la représentation IEEE 754.

C'est pas l'algorithme utilisé par le processeur d'ailleur ?

Oui, au pire tu va déborder de 1 bit (a gauche) lors de l'addition et obtenir un résultat sur 17 bits.
Tu peux détecter ce cas au moment de l'addition et faire un décalage de 1 bit a droite de tout le buffer pour te retrouver sur 16 bits (penser a réduire de 1 le shift final).

Oui effectivement,
Dans ce cas la ne vaut il pas mieux prevoir un bit de sécurité dans le buffer quite a perdre un bit de précision ? Que ferait le processeur ?

[pseudocode]

C'est pas l'algorithme utilisé par le processeur d'ailleur ?

Dans les FPU on multiplie généralement des flottants en représentation IEEE 754. Il sont donc normalisés et on n'a pas besoin de faire de décalage durant la phase de multiplication des mantisses. Par contre il faut faire un décalage après la multiplication pour normaliser le résultat.

http://meseec.ce.rit.edu/eecc250-win...-1-27-2000.pdf

Dans ce cas la ne vaut il pas mieux prevoir un bit de sécurité dans le buffer quite a perdre un bit de précision ? Que ferait le processeur ?

Si c'est une FPU (qui gere les flottants) elle s'occupe de tout. Sinon, les ALU signalent les problèmes dans un registre d'état (bit d'overflow, de retenu, de division par zero, ...). Il suffit de tester ce registre a la fin de l'addition pour savoir s'il y a eu dépassement et ainsi faire le décalage nécéssaire...

http://en.wikipedia.org/wiki/Arithme...ts_and_outputs

[scr]

Ok et encore merci pour ces précisions

[pseudocode]

Ok et encore merci pour ces précisions

De rien... c'etait un plaisir