Discussion :

[Emcy]

bonjour,

Sur un µC 8 bit, je dois faire une multiplication de 2.833 sur un unsigned int.
Comment faire pour avoir un code optimisé ?

... j'ai commencé par faire une multiplication par x2 mais après je ne vois pas comment faire pour le 0.833...

[Zavonen]

Il me semble qu'il manque deux précisions à ta question:
Les floats sont ils représentés (y-a-t-il un coprocesseur et un jeu d'instructions accessible) ?
Quelle est la précision voulue ?
Sinon, on peut toujours:
définir une représentation des floats sur 4,8,12 octets
implémenter la division par 10 (routine div)
implémenter la multiplication par un chiffre (routine mult (c))
et combiner ces deux routines avec l'addition (routine add)
Mais je ne pense pas qu'il s'agisse d'une optimisation.

[Emcy]

non les floats ne sont pas representés

le resultat represente une tension en mV => je veux une précision à 100mV près
le resultat sera en général compris entre 9000 et 65500 (en dehors de ces plages, la precision peut etre moindre)

PS : je n'ai jamais travaillé sur des floats donc je ne sais pas trop comment ça se gère...

[Ulmo]

Pas besoin d'implémenter des float si le seul que tu utilises est 2.833.
2.833 sécrit en binaire : 10.110101010011111...
Pour la multiplication entière par n, tu vas donc sommer :
n * 2
n / 2
n / 4
n / 16
n / 64
n / 256
n / 2048
n / 4096
n / 8192
n / 16384
n / 32768

L'algorithme ne devrait pas te poser de problème.

[Zavonen]

Pas besoin d'implémenter des float si le seul que tu utilises est 2.833.
2.833 sécrit en binaire : 10.110101010011111...
Pour la multiplication entière par n, tu vas donc sommer :
n * 2
n / 2
n / 4
n / 16
n / 64
n / 256
n / 2048
n / 4096
n / 8192
n / 16384
n / 32768

L'algorithme ne devrait pas te poser de problème.

Ca me parait une excellente idée !
d'autant plus que les divisions par les puissances de 2 ne sont que des itérations de la division par 2
On doit donc rester avec 3 routines:
multiplication par 2 (déjà fait)
division par 2
addition

[Emcy]

ok, merci pour les infos (c'est bete que le compilo ne sache pas faire la convertion tout seul)

[Nemerle]

Pour les * et / tu peux utiliser les décalages à droite et à gauche...

X/8 = x>>3

[Emcy]

quelqu'un connait un bon logiciel gratuit pour convertir des chiffre decimal a virgule en binaire ?

[Ulmo]

La calculette windows n'est pas gratuite mais fait très bien l'affaire.
Tu veux 16 digits, tu multiplies 2.833 par 2^16 :
2.833*65536=185663.488
tu convertis en binaire (ce qui coupe la partie fractionnaire) :
185663(10) = 101101010100111111(2)
tu redivises par 2^16, c'est à dire que tu décales la virgule de 16 places :
10.1101010100111111

[Emcy]

ok merci (désolé pour la question bete => je n'avais pas pensé à multiplier le chiffre auparavant...)

[scr]

Petite question suite a la solution proposée par ulmo :
Les termes à sommer :
n * 2
n / 2
n / 4
n / 16
n / 64
n / 256
n / 2048
n / 4096
n / 8192
n / 16384
n / 32768
sont réels et non entiers !
J'ai un doute sur le résultat si ils sont arrondis a des entiers...

[Emcy]

je n'ai pas trop compris ta question....

Donc ce que je peux te dire c'est que la precision de la conversion de l'exemple de Ulmo est à 2^-15 => si tu as besoins de plus, il faut alors multiplier le nombre (avant de placer la virgule) par une puissance plus élevée.
=> le resultat est un entier

il y a une perte de certains bit pendant la division

ex :
par exemble, si on divise 7 par 4 on aura
111b >> 2 = 1b
=> on perd donc les deux bit de poids faibles

[Jean-Marc.Bourguet]

bonjour,

Sur un µC 8 bit, je dois faire une multiplication de 2.833 sur un unsigned int.
Comment faire pour avoir un code optimisé ?

... j'ai commencé par faire une multiplication par x2 mais après je ne vois pas comment faire pour le 0.833...

Tu peux multiplier par 2833 et diviser par 1000. Ou utiliser une autre fraction qui a la précision nécessaire si ton 2.833 est une approximation (par exemple 17/6=2.83333333...) et que tu as des dépassements à craindre.

[scr]

Donc ce que je peux te dire c'est que la precision de la conversion de l'exemple de Ulmo est à 2^-15 => si tu as besoins de plus, il faut alors multiplier le nombre (avant de placer la virgule) par une puissance plus élevée.
=> le resultat est un entier

il y a une perte de certains bit pendant la division

ex :
par exemble, si on divise 7 par 4 on aura
111b >> 2 = 1b
=> on perd donc les deux bit de poids faibles

Oui c'est bien de ce problème que je voyais...
Une précision de 2^-15 ! sur un résultat entier ! cela m'étonne...
Comment determines tu cette précision ?

[scr]

si je prend un cas concret n=1:

n * 2 = 2
n / 2 = 0
n / 4 = 0
n / 16 = 0
n / 64 = 0
etc...

le résultat est 2 au lieu de 2.833
ca fait une sacrée erreur !

[pseudocode]

si je prend un cas concret n=1 (...) le résultat est 2 au lieu de 2.833. ca fait une sacrée erreur !

Oui... on appelle ca arrondir à l'entier inferieur. C'est une technique pratique quand on doit faire une multiplication dont le résultat est un entier:

Sur un µC 8 bit, je dois faire une multiplication de 2.833 sur un unsigned int.

[Emcy]

La tolerence de 2^-15 que j'annonçais n'etait pas sur le résultat mais sur le multiplicateur.

On perd en précision si le nombre est plus petit que 2^(15 + 1) => si le nombre est trop petit, la subtilité consiste à multiplier le nombre par une puissance de 2 avant de faire le traitement...

exemple avec precision à 2^(-11) :

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
1234 * 2.833 = 3495.922
 
Tolérance => 2^(-11) = 0.00048828125
 
1234 * (2.833 - 0.00048828125) = 3495.319 (résultat avec tolérence)
 
***************************************
 
1234 => 100 1101 0010
 
100 1101 0010 << 1 (*2) =  100 1101 00100 => 2468
100 1101 0010 >> 1 ( /2 ) =  100 1101 001 => 617
100 1101 0010 >> 2 ( /4 ) =  100 1101 00 => 308
100 1101 0010 >> 4 ( /16 ) =  100 1101 => 77
100 1101 0010 >> 6 ( /64 ) =  100 11 => 19
100 1101 0010 >> 8 ( /256 ) =  100  => 4
100 1101 0010 >> 11 ( /2048 ) =  0  => 0
 
2468 + 617 + 308 + 77 + 19 + 4 = 3493
 
**************************************
 
1234 => 100 1101 0010
 
100 1101 0010 << 1  = 1001 1010 0100 (passage à 12 bits)
 
1001 1010 0100 << 1 (*2) =  1001 1010 0100 0 => 4936
1001 1010 0100 >> 1 ( /2 ) =  1001 1010 010 => 1234
1001 1010 0100 >> 2 ( /4 ) =  1001 1010 01 => 617
1001 1010 0100 >> 4 ( /16 ) =  1001 1010  => 154
1001 1010 0100 >> 6 ( /64 ) =  1001 10 => 38
1001 1010 0100 >> 8 ( /256 ) =  1001 => 9
1001 1010 0100 >> 11 ( /2048 ) =  1 => 1
 
4936 + 1234 + 617 + 154 + 38 + 9 + 1 = 6989 => 1 1011 0100 1101
 
1 1011 0100 1101 >> 1 = 1 1011 0100 110 (repassage à 11 bits) = 3494

=> mais la, je ne retrouve pas ma précision de 2^(-11)
=> conclusion : je ne sais pas trop comment determiner la précision du calcul ...lol (je me suis gouré à quelque part ?)

[Emcy]

=> pourquoi tu dis ça ? en quoi est-ce une abération ? quelle solution utiliser alors ? (attention, je suis sur un mirco 8 bits)

[scr]

Merci pour cette illustration qui me conforte dans l'idée que cette solution est assez approximative. La multiplication par 17 puis division par 6 me semble plus precise. Cette version est elle plus rapide ?

[pseudocode]

=> pourquoi tu dis ça ? en quoi est-ce une abération ? quelle solution utiliser alors ? (attention, je suis sur un mirco 8 bits)

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