Discussion :

[namerif]

Bonjour,

j'aimerais savoir quel est le meilleur algorithme de conversion décimal -> binaire.
Je connais celui qui consiste a diviser par deux successivement ledit nombre et de conserver le reste de ces divisions.

Cependant, il me semble qu'il existe un algorithme plus performant, c'est à dire dont la complexité serait inférieure à 0(n²), n étant le nombre de bits du nombre a convertir.

Alex

[PRomu@ld]

En fait tu peux dans certaines conditions travailler à partir de données pré-calculés en 0(k) où k est le nombre de bits maximum dans lequel tu souhaites travailler.

Il suffit de retrancher quand c'est possible la valeur 2^i (en commençant par k) à N, jusqu'à obtenir 0.

Mais ça nécessite tout de même certains pré requis pas toujours disponibles :
- Pourvoir représenter en machine toutes les puissances de 2 que l'on veut jusqu'à k (si k > 32 ça peut commencer à poser problèmes).
- Pouvoir être sur qu'on peut déterminer un k (ne va-t'on pas devoir calculer autre chose de plus grand ?)

[namerif]

Je vois... merci.
donc je peux gagner un peu en complexité en enregistrant certaines puissances de 2.
Effectivement si j'arrive à les enregistrer "toutes", ie jusqu'à un k au dela duquel je n'irai pas, c'est très intéressant.

J'ai lu sur internet qu'on pouvait aussi passer par la base 256 (ou surement une autre), puis revenir en base 2 (256=2^8) simplement. qu'en pensez-vous ?

[PRomu@ld]

J'ai lu sur internet qu'on pouvait aussi passer par la base 256 (ou surement une autre), puis revenir en base 2 (256=2^8) simplement. qu'en pensez-vous ?

En fait, ça ne change pas le problème. il faudra toujours convertir en base 2^n. de plus, le problème de la représentation des suites de base de 2^n est toujours existant.

Néanmoins pour ce qui est de la conversion du nombre en base 2^n en un nombre en base 2 c'est effectivement trivial mais ça n'était pas le problème.

[namerif]

D'accord.
Le principal problème est, comme vous le dites, d'être certain d'avoir enregistré toutes les valeurs utiles (k) dans notre table pour pouvoir faire le calcul efficacement.

La complexité devient-elle O(n) dans ce cas ?

connaissez-vous un algorithme qui puisse s'affranchir du pré-enregistrement de valeurs ?

[PRomu@ld]

La complexité devient-elle O(n) dans ce cas ?

C'est O(k) où k est la plus grande puissance de 2 possible.

connaissez-vous un algorithme qui puisse s'affranchir du pré-enregistrement de valeurs ?

Mis à part la division, je ne vois pas de méthode générale plus efficace pour passer d'une base b à une base p.

[pseudocode]

Cependant, il me semble qu'il existe un algorithme plus performant, c'est à dire dont la complexité serait inférieure à 0(n²), n étant le nombre de bits du nombre a convertir.

C'est une question générale, où c'est pour répondre à un problème spécifique ?

Une méthode parmi d'autres, utiliser le fait que a*10 = a*(8+2) = (a<<3) + (a<<1)

Et donc, par exemple

x = 1537 = 1*1000+5*100 + 3*10 + 7 = ( ( ( ( (1*10) + 5 )*10 ) + 3 )*10 ) + 7

x = 1
x = (x<<3) + (x<<1)
x = x + 5
x = (x<<3) + (x<<1)
x = x + 3
x = (x<<3) + (x<<1)
x = x + 7