Conversion binaire - Nombre d'octetsRésolu

Question

Bonjour


J'écris en ce moment un programme capable de convertir de grands nombres décimaux en binaire. Connaissant le nombre de chiffres composant le décimal, existe-t-il un moyen de calculer approximativement le nombre d'octets nécessaires à la conversion?


D'avance merci pour vos réponses

Utilisateur anonyme · Accepted Answer

Salut,

Avec des logarithmes :
NbBit = Fix(Log(i) / Log(2) + 1)
__________
  Kenji

cs_Jack · Answer

Salut
Suffit de trouver la puissance de 2 juste supérieure à la valeur de ton nombre.Exemple : 58 se codera avec 6 bits puisque 2^6 64, donc sur 1 octet (puisque 1 octet 8 bits)

Vala
Jack, MVP VB
NB : Je ne répondrai pas aux messages privés

<hr />Le savoir est la seule matière qui s'accroit quand on la partage (Socrate)

Kevin.Ory · Answer

Salut,

Private Function GetNbrOfBits(Value as Integer) as Integer
    For i as Integer = 1 to 32 
        If 2^i > Value Then Return i
    Next i
End Function

Avec la veur 32 tu peux donc tester que des integer (nombres allant jusqu'à un peu plus de 2.1 milliards)
Value est en integer, donc si tu veux tester des plus gros nombre, faut changer son type.
Ca ne fonctionne qu'avec des nombre positifs. Il y a des changements à faire si tu veux tester des nombres négatifs (Math.Abs() par ex).
Si tu veux pas le nombre de bit mais d'octets, tu peux faire For i as Integer = 8 to 32 Step 8 pour ne tester les valeurs que tous les 8 bits et ainsi gagner du temps.

Voilà :)
Une formule en une ligne n'est pas possible que je sache.

cs_casy · Answer

Quelques remarques sur ton code Kevin :

Un Integer (ça dépend du langage) va jusqu'à 2,...millard soit de 0 à (2^31)-1 et non pas 2^32. Un Integer est signé, donc le dernier bit sert de bit de signe.
Mais cela n'est valable qu'en VB2005, ce que laisse suggerer ton code d'ailleurs.

En VB6 (rubrique du sujet) par contre un integer va jusqu'à (2^15)-1, soit 32767

Un Integer en .Net corespond à un Long en VB6.

En .net tu peux aller plus loin avec le long qui va jusqu'à (2^63)-1. Il n'y a pas d'équivalent en VB6
En .Net tu eux aussi aller plus loin pour chaque type en utilisant sa version non-signé. Ex un UInt va jusqu'à (2^32)-1 au lieu du (2^31)-1 de l'integer. Là non plus il n'y a pas d'équivalent en VB6

---- Sevyc64  (alias Casy) ---- # LE PARTAGE EST NOTRE FORCE #

cs_casy · Answer

Pour connaitre le nombre de bits necessaires pour coder un nombre, il faut comme le dit Jack, trouver la puissance de 2 immédiatement suppérieure

En partant de la valeur à analiser, soit une boucle ou à chaque cycle on affecte à une variable le résultat de la division de cette variable par 2. Le nombre de bit sera donné ar le nombre d'itération de la boucle tant que la partie entière du résultat n''est pas égale à 0

----
Public Function nbBits(valeur As Long) As Integer
Dim valtemp As Double

   nbBits =   0
   valtemp = valeur
   While Int(valtemp) > 0
       valtemp = valtemp / 2
       nbBits = nbBits + 1
   Wend

End Function
, ----
, ----
[code.aspx?ID=41455 Coloration Syntaxique pour VB6 By ]

  ---- Sevyc64  (alias Casy) ----  <hr size  ="2" width="100%" /># LE PARTAGE EST NOTRE FORCE #

mJuJu · Answer

J'ai bien compris l'algorithme que vous proposez. 

Mais supposez un nombre de 200 000 chiffres ou plus, le calcul du nombre de bits (ou d'octets, peu importe) nécessaires à la conversion, va demander presque autant de temps que la conversion elle-même. Je cherche donc un calcul beaucoup plus rapide, s'il existe. De mon côté je cherche sur internet une solution à ce problème, mais je n'ai encore rien trouvé

Kevin.Ory · Answer

Re,

En fait si, j'ai eu bcp de peine à m'en souvenir (on m'a aidé):

        Dim Valeur As Integer = 165493
        Dim NbrOfBits As Integer = Math.Ceiling(Math.Log(Valeur, 2))
        Dim NbrOfBytes As Integer = Math.Ceiling(Math.Log(Valeur, 2) / 8)

cs_casy · Answer

Sachant qu'en VB6, le plus grand nombre que tu peut convertir est un Double soit au maxi 1,79769313486232E308 

Mon code s'execute sur mon PC (un P4 d'il y a 5 ans) en une moyenne de 0,24ms avec un delta de +/-0.02ms

Au passage, le résultat c'est 1024 

---- Sevyc64  (alias Casy) ---- # LE PARTAGE EST NOTRE FORCE #

Kevin.Ory · Answer

Oups, je suis confus. J'avais effectivement cru que l'on parlais de .NET 

casy> Oui je sais qu'un Integer en .NET est du 32 bits signé, d'où mon "(nombres allant jusqu'à un peu plus de 2.1 milliards)". Mais effectivement ça ne sert à rien d'aller jusqu'à 32, 31 suffit.

mJuJu> "Mais supposez un nombre de 200 000 chiffres ou plus"  

Ok, dans ce cas tu peux effectivement pas calculer le nombre de bits en fonction de ton nombre. J'imagine mal un processeur de PC faire un calcul sur un tel nombre d'ailleur, même une addition 

Même avec une table précalculé c'est impossible, puisque il est impossible de représenter de tel nombre dans un PC

mJuJu · Answer

Je posterai un jour le source ou j'aditionne de tels nombres. Ce n'est pas très compliqué. Et la rapidité est satisfaisante. 
L'astuce consiste à découper le nombre en morceaux de 8 chiffres et de stocker ces morceaux dans un tableau de longs. Une boucle sert à l'addition des longs en faisant attention aux retenues. Finalement, il ne reste plus qu'à restituer le résultat dans une string.

Je reste sur la formule Fix(Log(val) / Log(2) + 1) qui me va très bien. 
Intuitivement, je sens assez bien l'utilisation des logarithmes. Je vais la tester.

cs_Jack · Answer

Re
Excellent Charles !
Bien sûr, suffisait de se replonger dans les souvenirs ...

Juju : pense à valider (Réponse acceptée) la réponse qui va bien.

Vala
Jack, MVP VB
NB : Je ne répondrai pas aux messages privés

<hr />Le savoir est la seule matière qui s'accroit quand on la partage (Socrate)

mJuJu · Answer

J'ai converti un nombre de 10 000 chiffres :  468928 * 10 ^ 9994. Les propriétés des logarithmes me permet d'écrire :

Log (468928 * 10 ^ 9994) = Log (468928) + Log (10 ^ 9994)
                                          = Log (468928) + 9994 * Log (10)
                                          = 13,0582 + 9994 * 2,3025 
                                          =  23025
Log (2) =  0,6931

Log (Nombre) / Log (2) = 33220 bits soit 1071,61 longs (où seulement 31 bits sont utilisés à cause du bit de signe). En prenant le premier entier immédiatement supérieur, on a donc 1072 longs.  
Ma conversion utilise exactement 1072 longs.  

On pourrait éventuellement généraliser la formule de la façon suivante : 
Soit n le nombre de chiffres. Il peut être au maximum composé de n chiffres 9, nombre qui est immédiatement inférieur à 10^n.

On peut donc calculer la borne supérieure du nombre de bits nécessaires :Log (nombre) / Log (2)  n * (Log (10)  / Log (2) 3,3219281* n 
On prend l'entier immédiatement supérieur.

Pour convertir un nombre de 16 chiffres par exemple il faudra ::
Nb bits = 16 *  3,3219281 = 54 bits
en effet : 9999999999999999 en binaire donne 
100011100001101111001001101111110000001111111111111111
 
Pour un nombre de 10 000 chiffres on a :Nb bits 10 000 * 3,3219281 33 220

Voilà. Qu'en pensez-vous ? Le seul petit problème résiderait éventuellement dans la précision de la valeur Log (10) / Log (2). Mais finalement rien n'empêche de prendre la valeur 3,322 pour être sûr à 100 %.

Kevin.Ory · Answer

Casy: Mon code s'execute sur mon PC (un P4 d'il y a 5 ans) en une moyenne de 0,24ms avec un delta de +/-0.02ms


J'affiche 0.137ms à mon compteur, avec mon Sempron à 1.8GHz  (VB .NET 3.5)

   Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
        Dim start As DateTime = Now

        Dim cnt As Integer = 0
        Dim stepVal As Double = Double.MaxValue / 100000

        For i As Double = 0 To Double.MaxValue Step stepVal
            Dim val As Integer = GetNbrOfBits(i)
            cnt += 1
        Next

        Dim span As TimeSpan = Now - start
        Me.Label1.Text = span.TotalMilliseconds / cnt
    End Sub

    Private Function GetNbrOfBits(ByVal Value As Double) As Integer
        For i As Integer = 1 To 10000
            If 2 ^ i > Value Then Return i
        Next i
    End Function

mJuJu> Si tu veux savoir combiens d'octets ça te prend environ, tu pourrais faire une table qui te donne des interval:
1 chiffre entre 1 et 4 bits 1 octet2 chiffres entre 4 et 7 bits 1 octet3 chiffres entre 7 et 10 bits 1 ou 2 octets4 chiffres entre 10 et 14 bits 2 octets
...10 chiffres  entre 29 et 34 bits 4 ou 5 octets
...100 chiffres entre 329 et 333 bits 42 octets
...

Il faut avant tout faire cette table, mais une fois que tu l'as le calcul est rapide.

En calculant ces valeurs, j'ai trouvé autre chose : 

Nombre de chiffre / Log(2) = Nombre max de bits (arrondis au dessus)
2 / Log(2) = 7
4 / Log(2) = 14
10 / Log(2) = 34 
100 / Log(2) = 333308 / Log(2) 1024  (max pour 308 min pour 309, ça correspond au max du type Double)
309 / Log(2) = 1026 

199'999 / Log(2) = 664'382

200'000 / Log(2) = 664'386

Donc il faut 83'048 ou 83'049 octets pour enregistrer un nombre de 200'000 chiffre après la virgule 

Je crois que j't'ai trouvé une réponse   (reste à vérifer tout de même)

Kevin.Ory · Answer

Voilà. Qu'en pensez-vous ? Le seul petit problème résiderait
éventuellement dans la précision de la valeur Log (10) / Log (2). Mais
finalement rien n'empêche de prendre la valeur 3,322 pour être sûr à
100 %.  



Tout à fait, le seul problème c'est de faire le Log(4.68928e9999) avec le PC.

Mais Log(4.68928e9999) = 10'000 (arrondis au dessus)
Autrement dit, le log retourne le nombre de chiffres 
D'ou ce que j'ai dis avant....

Kevin.Ory · Answer

Dsl de flooder, mais j'ajoute juste encore que pour avoir directement
le nombre d'octet au lieu du nombre de bits, suffit de faire:


NombreDeChiffre / Log(256)


10'000 / Log(256) = 4153 (33'224 bits, ça correspond à ton calcul)

200'000 / Log(256) = 83'049

Conversion binaire - Nombre d'octets

15 réponses

Votre réponse

Discussions similaires