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.

[namerif]

Apparemment il s'agit d'un problème ouvert. Il y a un algorithme performant en ce moment, personne ne peut prouver qu'il est (ou non) le meilleur. Et de temps un temps un nouvel algorithme remplace le précédent.

Lorsque vous dites O(k), vous considérez que les opérations de soustractions sont en temps constant ?

[PRomu@ld]

Apparemment il s'agit d'un problème ouvert. Il y a un algorithme performant en ce moment, personne ne peut prouver qu'il est (ou non) le meilleur. Et de temps un temps un nouvel algorithme remplace le précédent.

Tu parles de quel algo ?

Lorsque vous dites O(k), vous considérez que les opérations de soustractions sont en temps constant ?

En fait je considère que la complexité est fonction de k tout simplement. Et oui, je considère la soustraction à temps constant (sur une machine tu peux le considérer comme tel).

[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

[namerif]

Je parle de l'algo de conversion de la base 10 vers la base 2.

Je considère que la soustraction, tout comme l'addition et la simple lecture de l'input, est de complexité O(n), n étant le nombre de bits de l'input. c'est assez arbitraire, mais ça permet de réduire cette complexité en prenant ce fait en compte.



C'est une question générale, savoir quel est l'algorithme le plus performant en ce moment...
à quoi correspond le "(a<<3) + (a<<1)" ?

[PRomu@ld]

Ce sont des décalages de bits (ça revient à des multiplications par 2^p)

Je considère que la soustraction, tout comme l'addition et la simple lecture de l'input, est de complexité O(n),

Dans ce cas sans magie, impossible de faire plus bas, tu es obligé de lire tous les digits du nombre donc tu ne peux pas aller au dessous de O(n).

[namerif]

oui, je sais que je ne peux pas faire mieux que O(n); mais j'aimerais faire mieux que O(n²), qui est la complexté de l'algo de divisions successives par 2.