Discussion :

[Razgriz]

Salut à tous,

voilà je cherche à trouver une fonction qui étant donné un nombre me retourne la pluissance entière de 2 la plus proche.

Par exemple (appellons cette fonction f)

f(0.65) = 1/2 car 2^{-1} <= 0.65 <= 2^0 et 0.65 est plus proche de 1/2 que de 1.

(=> Quand je parle de puissance entière j'entends pas entier ici -1 et 0)

De la même manière,
f(2.6) = 2
f(3.1) = 4
...


Voilà ça a 'air bête mais je n'y arrive pas... comment construire une telle fonction?

[titoumimi]

Tu as une limite pour le nombre à comparer, ou potentiellement, tu peux avoir un nombre à 495 chiffres ?

Sinon, je voit bien une méthode bien violente avec un tableau associatif qui te stocke la puissance et la valeur associée :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
1=>2,
2=>4
3=>8
...

jusqu'à ta valeur max, et ensuite tu cherches quelles puissances encadrent ton nombre par dichotomie, et il ne te reste plus qu'à comparer en soustrayant (avec une valeur absolue) laquelle est la plus proche de ton nombre...

[Zavonen]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
def closest_pow_2(x):
    i=0
    p=1
    while(p<x):
        p=p*2
        i=i+1
    if (p-x)<(x-p/2):
        return i
    else:
        return i-1

[Jedai]

Zavonen : Ca ne marche pas pour les puissances négatives.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
f(x)
  p <- floor(log(x)/log(2))
  r <- 2^p
  Si x - r < 2r - x
  Alors :
    Return r
  Sinon :
    Return 2r

--
Jedaï

[alex_pi]

Sinon, je voit bien une méthode bien violente avec un tableau associatif qui te stocke la puissance et la valeur associée :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
1=>2,
2=>4
3=>8
...

Euh, sachant qu'une puissance de 2 se calcule en un tour de proc par décalage (allez, ptet 3 ou 4 suivant les cas), c'est quoi l'intéret de devoir faire un déréférencement mémoire pour aller chercher la valeur dans une case de tableau ?

[titoumimi]

Euh, sachant qu'une puissance de 2 se calcule en un tour de proc par décalage (allez, ptet 3 ou 4 suivant les cas), c'est quoi l'intéret de devoir faire un déréférencement mémoire pour aller chercher la valeur dans une case de tableau ?

Je pensait que ça rendrait la recherche plus facile J'suis pas très doué en temps de calcul

[Ulmo]

Tu peux aussi utiliser les logarithmes. L'entier que tu cherches est une valeur arrondie de log(x)/log(2).

[Jedai]

Tu peux aussi utiliser les logarithmes. L'entier que tu cherches est une valeur arrondie de log(x)/log(2).

Incorrect, par exemple log2(0.72) est plus proche de 0 que de -1, mais 0.72 est plus proche de 0.5 que de 1. Je ne sais pas à quoi servira cette fonction, mais selon les spécifications un simple arrondi du log2 ne suffira pas. L'algorithme que j'ai donné plus haut fonctionne par contre.

--
Jedaï

[Zavonen]

Zavonen : Ca ne marche pas pour les puissances négatives.

Faut bien qu'il reste un petit qqch à faire. Les puissances négatives sont les puissances positives de l'inverse, non ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def closest_pow_2_p(x):
    i=0
    p=1
    while(p<x):
        p=p*2
        i=i+1
    if (p-x)<(x-p/2):
        return i
    else:
        return i-1
 
def closest_pow_2_n(x):
    return -closest_pow_2_p(1/x)
 
def closest_pow_2(x):
    if x>=1:
        return closest_pow_2_p(x)
    else:
        return closest_pow_2_n(x)

[Jean-Marc.Bourguet]

Ce serait si simple en manipulant la représentation. On peut presque y arriver si le langage fournit les primitives adéquates, quelque chose comme (non teste)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
double f(double v) {
   int exp;
   double mant = frexp(v, &exp);
   return lexp(floor(mant*2+0.5), exp-1);
}

(Mais le floor est du gâchis, ce qu'on voudrait c'est masquer les bits; enfin, les cas où c'est utile de faire de telles manip sont rares au point que je me demande ce que ca couterait de faire le masquage en terme de rupture de communication entre unites flottante et entieres).

[Razgriz]

Parfait, l'algorithme de Jedai fonctionen très bien, que la force soit avec lui (lol d'accord elle était nulle la feinte ;-))

[Zavonen]

dixit Jean Marc Bourquet

Ce serait si simple en manipulant la représentation.

et il a parfaitement raison!
OK! l'algo de Jedaï résoud le pb de façon satisfaisante, inutile de chercher plus loin. Mais il y a là quelque chose d'illogique.
On reconstruit la représentation d'un flottant à base des logarithmes de base 2 alors que de façon interne on a déjà cette représentation.
Prenons le cas des floats sur 32 bits.
les premiers 23 bits représentent la mantisse
les 8 bits suivants l'exposant augmenté de 127
le bit de poids fort le signe
Il suffit d'isoler la mantisse
de déterminer la position du bit de poids fort (n)
de remplacer la mantisse par 1
d'ajouter n à l'exposant
et on aura la représentation float du nombre cherché.
Bien sûr c'est plus ch. à écrire que la solution Jedaï, qui masque une grande complexité par deux appels à une fonction transcendante de la bibliothèque.

[Razgriz]

Sans compter que le language de programmation dans lequel on va vouloir implémenter ta solution dans le cas où il n'est pas possible de manipuler les nombres binairement par mantisse (sans compter le fait que dans mon cas je ne me restreint pas aux puissances de 2) risque de rendre l'algorithme moins performant que la solution de Jedai.

Mais je note l'idée, pas mal du tout...

[Nemerle]

J'ai le temps encore de proposer une solution, rapide???

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
x=y-1    '=== y est le nombre de départ 
x=x|(x>>16)
x=x|(x>>8)
x=x|(x>>4)
x=x|(x>>2)
x=x|(x>>1)
 
x=x+1  '=== x contient la puissance de 2 juste supérieure à y
z= x>>1 '=== x contient la puissance de 2 juste inférieure à y
 
si (x-y<y-z) alors afficher y sinon afficher z

Y-a plus rapide?

[Jedai]

Y-a plus rapide?

Y a surtout le problème qu'on ne travaille pas avec des entiers mais avec des flottants... Ca doit être possible d'y arriver malgré cela, mais plus compliqué.

De plus Razgriz a précisé qu'il voulait aussi pouvoir le faire avec d'autres puissances que 2.

--
Jedaï

[Nemerle]

oups, sorry, j'avais pas lu... m'enfin, les flottants, ici, t'as juste à les tronquer

Concernant les autres puissances, j'ai vu des méthodes via décalage pour 3 et 5...

[Jedai]

oups, sorry, j'avais pas lu... m'enfin, les flottants, ici, t'as juste à les tronquer

Concernant les autres puissances, j'ai vu des méthodes via décalage pour 3 et 5...

Ouais, par exemple on tronque 1e50... Non, faut extraire la mantisse et l'exposant et faire quelques calculs.

Et effectivement y a des méthodes par décalage pour 3 et 5 mais c'est pas forcément très pratique, ni performant, ni généraliste. Et puis tu fais quoi comme équivalent de tes masques ?

--
Jedaï