Discussion :

[NiamorH]

Bonjour,

j'ai besoin d'une fonction avec un entier non signé en parametre qui me renvoie la puissance de deux superieure.

Cette fonction sera appellée souvent donc je cherche à reduire au maximum sa complexité.
En fait j'ai deja trouvé quelque chose mais je suis sur qu'il y a mieux. Voila ce que j'ai :

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
20
21
22
23
24
25
26
27
28
29
int main()
{
  char rep = 'y';
 
  while (rep == 'y')
  {
    unsigned long test, puissance;
    int nb_bits = 0;
 
    cout << "Entrez un nombre" << endl;
 
    cin >> test;
	--test;
 
    while (test > 0)
    {
      test >>= 1;
	  ++nb_bits;
    }
 
    puissance = (unsigned long)pow((double)2.,(double)nb_bits);
 
    cout << puissance << endl;
    cout << "encore ? y or n" << endl;
 
    cin >> rep;
  }
  return 0;
}

Avez vous des idees ?

[fearyourself]

Bonjour,

j'ai besoin d'une fonction avec un entier non signé en parametre qui me renvoie la puissance de deux superieure.

Cette fonction sera appellée souvent donc je cherche à reduire au maximum sa complexité.
En fait j'ai deja trouvé quelque chose mais je suis sur qu'il y a mieux. Voila ce que j'ai :

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
20
21
22
23
24
25
26
27
28
29
int main()
{
  char rep = 'y';
 
  while (rep == 'y')
  {
    unsigned long test, puissance;
    int nb_bits = 0;
 
    cout << "Entrez un nombre" << endl;
 
    cin >> test;
	--test;
 
    while (test > 0)
    {
      test >>= 1;
	  ++nb_bits;
    }
 
    puissance = (unsigned long)pow((double)2.,(double)nb_bits);
 
    cout << puissance << endl;
    cout << "encore ? y or n" << endl;
 
    cin >> rep;
  }
  return 0;
}

Avez vous des idees ?

C'est quoi ces cin et cout ? Tu veux faire du C++, car c'est à côté le C++...

Jc

[stephl]

Je pense que ceci est légèrement plus efficace (notamment pas d'appel à pow()):

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
 
 
int main(void)
 {
 unsigned int i,power;
 
 scanf("%u",&i);
 for (power=1;power<i;power<<=1);
 printf("i=%u\tpuissance de 2 supérieure: %u\n",i,power);
 return 0;
 }

[NiamorH]

ne sois pas agressif, les cin et cout ne me servaient qu'a recuperer des valeurs pour mes tests.

voila une version plus C :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
uint puissanceSuperieure(uint nombre)
{
  int nb_bits = 0;
 
  --nombre;
 
  while (nombre > 0)
  {
	nombre >>= 1;
	++nb_bits;
  }
 
  return (unsigned long)pow((double)2.,(double)nb_bits);
}

[NiamorH]

merci stephl, ça marche bien et c'est effectivement plus rapide.

[fearyourself]

C'est une question plus algorithmique qu'autre chose. Ce qu'on cherche ici est une recherche avec un critére bien défini.

La meilleure solution est donc la recherche dichotomique.

Fait rapidement mais cela semble fonctionner correctement :

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
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
 
unsigned int pow2sup(unsigned int nbr)
{
    int bs,bi;
    int min = 0;
    int max = 31;
 
    int mid = (min + max)/2;
 
    /* Borne inferieure */
    if(nbr <= 1) {
        return 1;
    }
 
    /* Borne superieure */
    if( nbr > (1<<30)) {
        return (1<<31);
    }
 
    do 
    {
        bs = (1<<mid);
        bi = (1<<(mid-1));
 
        if(nbr < bi) {
            max = mid;
            mid = (min+max)/2;
        }
        else {
            if(nbr > bs) {
                min = mid;
                mid = (min+max)/2;
            }
            else {
                if(bi == nbr) {
                    return bi;
                }
                return bs;
            }
        }
    }while(min != max);
    return 0;
}
 
int main(void)
{
    int i;
    unsigned int nbr,sol;
 
    srand(time(NULL));
    for(i=0;i<30;i++) {
        nbr = rand();
        sol = pow2sup(nbr);
        if((sol >= nbr) && (sol/2 < nbr)) {
            printf("%u -> %u \n",nbr,sol);
        }
        else {
            printf("Erreur avec %u -> %u\n",nbr, sol);
        }
    }
    return EXIT_SUCCESS;
}

J'ai supposé que les nombres seraient compris entre [0, 1<<31[.
Pour 0, je retourne 1.

Jc

[stephl]

Personnellement, je pense que tous les calculs induits par la méthode dichotomique vont faire perdre plus de temps qu'autre chose. Mais je peux me tromper, alors je vais comparer...

[NiamorH]

en fait l'etendue des puissances n'est pas aussi grand.

cela ne dépassera pas 2^13 mais la grande majorité si ce n'est la totalité ne depassera en fait pas 2^12.

donc je pense que faire douze shift au max, avec un test par iteration sera cool pour moi.

[fearyourself]

en fait l'etendue des puissances n'est pas aussi grand.

cela ne dépassera pas 2^13 mais la grande majorité si ce n'est la totalité ne depassera en fait pas 2^12.

donc je pense que faire douze shift au max, avec un test par iteration sera cool pour moi.

J'aurais une tendance à dire que la version dichotomique serait tout de même plus rapide.

Pour gagner encore plus de performances, rien ne t'empêche de modifier la borne supérieure si tu sais que ton programme ne dépasse pas une certaine limite.

Jc

[stephl]

Voici les résultats que j'ai obtenus en testant 1000 répétitions sur un tableau de 1 million de nombres aléatoires (soit 1 milliard d'appels):

Code :

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

1
2
MÚthode par dichotomie: 95.015 s
MÚthode sÚquentielle: 65.625 s

La différence n'est pas aussi grande que je l'aurais crue . La méthode par dichotomie serait -je pense- sans doute gagnante si on manipulait des entiers codés sur davantage de bits. Mais bon, ce n'est pas le cas ici.