Double dabble

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

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 4*ceil(n/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

Liens externes

• (en) Explication sur l'algorithme Double Dabble, par C.B. Falconer