Double dabble
# 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 :

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 :

Dans le cas du nombre 243, on s'attend à obtenir ceci à gauche du registre :

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 :

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 :

