Double dabble
Un article de Wikipédia, l'encyclopédie libre.
Le double dabble est un algorithme utilisé pour convertir des nombres d'un système binaire vers un système décimal. Pour des raisons pratiques, le résultat est généralement stocké sous la forme de décimal codé en binaire (BCD).
[modifier] Principe
On considère un nombre à convertir de n bits qui est initialement stocké dans un registre. La taille du registre est suffisante pour contenir le résultat en BCD, soit n + 4n / 3 bits. On admet deux ensembles dans le registre : les bits constituant le nombre à convertir et le reste des bits qui sont initialement à zéro. Par exemple, avec le nombre 11110011 (243 en base 10), le registre se présenterait au début comme suit :
ORIGINAL
0000 0000 0000 11110011
La suite de 0 à gauche du nombre va progressivement recevoir le résultat du calcul qui sera codé en BCD. Chaque nibble (4 bits) constitue une décimale, par exemple le nombre 127 est codé comme suit :
1 2 7 0001 0010 0111
Dans le cas du nombre 243, on s'attend à obtenir ceci à gauche du registre :
2 4 3 0010 0100 0011
En partant du registre initial, l'algorithme effectue n itérations (soit 8 dans l'exemple). À chaque itération, le registre est décalé d'un bit vers la gauche. Avant d'effectuer cette opération, la partie au format BCD est analysée, décimale par décimale. Si une décimale en BCD (4 bits) est plus grande que 4 alors on lui ajoute 3. Cette incrément permet de s'assurer qu'une valeur de 5, après incrémentation et décalage, devient 16 et se propage correctement à la décimale suivante.
Les étapes complètes dans le cas de 243 :
0000 0000 0000 11110011 Initialisation 0000 0000 0001 11100110 Décalage 0000 0000 0011 11001100 Décalage 0000 0000 0111 10011000 Décalage 0000 0000 1010 10011000 Ajouter 3 à la première décimale BCD, puisque sa valeur était 7 0000 0001 0101 00110000 Décalage 0000 0001 1000 00110000 Ajouter 3 à la première décimale BCD, puisque sa valeur était 5 0000 0011 0000 01100000 Décalage 0000 0110 0000 11000000 Décalage 0000 1001 0000 11000000 Ajouter 3 à la seconde décimale BCD, puisque sa valeur était 6 0001 0010 0001 10000000 Décalage 0010 0100 0011 00000000 Décalage
Au total, 8 décalages ont été effectués et la partie de droite s'est vidée. À gauche du registre, on obtient le résultat en BCD comme attendu :
2 4 3 0010 0100 0011 00000000
[modifier] Liens externes
- (en) Explication sur l'algorithme Double Dabble, par C.B. Falconer
