Algorithme de conversion décimal vers binaire

Une façon possible pour convertir un nombre entier N en base décimal vers la base binaire consiste à réaliser une succession de divisions euclidiennes par 2 et de noter les restes de ces divisions au fur et à mesure.
Le dividende de la 1ère division est N, puis le dividende de chaque nouvelle division est le quotient de la division précédente.
On arrête les divisions lorsque le quotient vaut 0.
Le nombre binaire est alors constitué des restes successifs notés dans l’ordre inverse (du dernier obtenu au premier).

Exemple : Conversion de 37₁₀ :
37 = 18 x 2 + 1
18 = 9 x 2 + 0
9 = 4 x 2 + 1
4 = 2 x 2 + 0
2 = 1 x 2 + 0
1 = 0 x 2 + 1
On obtient ainsi : 37₁₀ = 100101₂

Implémentation en Python

Une implémentation possible de cet algorithme en langage Python est la suivante :

def dec2bin(n): """ Renvoie une liste des bits de la conversion de l'entier n (base 10) en binaire """ binaire = [] while n != 0: binaire.insert(0, n % 2) # insertion du reste en début de liste n //= 2 # quotient de la division euclidienne par 2 return binaire # Exemple : >> dec2bin(37) out : [1, 0, 0, 1, 0, 1] >> bin(37) # fonction intégrée de conversion du langage out : '0b100101'

Ici on a choisi de créer une liste de bits qui correspondent au nombre binaire mais bien entendu d’autres choix de représentation du nombre binaire sont possibles (comme par exemple la fonction du langage bin).

Additionner pour multiplier

Si l’on s’interdit la multiplication directe, effectuer une multiplication peut alors se réduire à une succession d’additions !

Exemple : 37 x 19 = 19 + 19 + ... + 19 avec 37 additions du nombre 19 !

Le produit des 2 facteurs est transformé en une somme de termes.

Algorithme égyptien (antique !)

Il est possible de développer un algorithme beaucoup plus rapide en s’autorisant seulement les multiplications ou divisions par 2 : ce qui reste très accessible, même pour un Égyptien à l’époque antique.
Wikipédia nous dit que « Cette technique est notamment connue grâce au papyrus Rhind, papyrus hiératique écrit au XVIIe siècle av. J.-C. (env. -1650) où le sage Ahmès expose les connaissances mathématiques de son temps. »

 Voyons cet algorithme en action à travers un exemple :
Nous désirons multiplier 37 par 19.
À chaque étape de l’algorithme, on divise le multiplicateur par 2 (pour obtenir le quotient de la division euclidienne) et on multiplie par 2 le multiplicande. Ceci est répété jusqu’à obtenir un multiplicateur égal à 1.
A la fin de ces opérations, on fait la somme de tous les multiplicandes qui correspondent à un multiplicateur impair pour avoir le résultat global de la multiplication. (magique ? sans doute pas...)

37 x 19
18 x 38 (division euclidienne : 37 = 18 x 2 + 1)
9 x 76
4 x 152
2 x 304
1 x 608

Ici, les multiplicateurs impairs sont 37, 9 et 1.
Donc le résultat de la multiplication est : 37 x 19 = 19 + 76 + 608 = 703 !

Une petite explication

Les divisions euclidiennes par 2 successives du multiplicateur reviennent à chercher sa conversion en binaire.
Dans l’exemple précédent, on a obtenu :
37 = 100101₂ = 2⁵ + 2² + 2⁰ = 32 + 4 + 1.
Et pour effectuer la multiplication de 37 par 19, plutôt que d’additionner 37 fois 19, on va additionner 32 fois 19 (608) avec 4 fois 19 (76) et avec 1 fois 19 (19).
Et voilà, le tour est joué !

Transformation de l’algorithme de conversion décimal/ binaire en multiplication égyptienne

Une légère modification de l’algorithme précédent permet d’obtenir l’algorithme de multiplication égyptienne.
Une implémentation possible en Python est la suivante :

def multiplication(n, p): """ Renvoie le produit de n par p """ produit = 0 while n != 0: if n % 2 == 1: # multiplicateur impair produit += p n //= 2 # division euclidienne par 2 du multiplicateur p *= 2 # multiplication par 2 du multiplicande return produit # Exemple : >> multiplication(37, 19) out : 703

Activité NSI

Cet article pourra sans doute inspirer les collègues à développer une activité dans le cadre des cours NSI (particulièrement bien adapté au niveau 1ère ). En effet plusieurs notions sont abordées ici, comme la représentation des données, l’algorithmique et les langages de programmation.

On pourra même utiliser des opérateurs de décalage de bits pour effectuer la multiplication ou la division par 2.
Il suffit de modifier les lignes 7 et 8 de l’algorithme précédent :

def multiplication(n, p): """ Renvoie le produit de n par p """ # préconditions : n et p sont des entiers produit = 0 while n >= 1: if n % 2 == 1: produit += p n >>= 1 p <<= 1 return produit