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.

[Emmanuel Delahaye]

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.

En tout cas, c'est bien d'avoir fait la mesure...

[fearyourself]

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.

C'est intérressant, j'ai moins de différences de temps sur les tests mais en effet, on dirait que la dichotomie ne fait pas mieux que la version itérative. A noter que si on descend la borne maximale, j'ai presque les mêmes temps entre les deux.

Mais en effet, dans le cas présent, cela revient au même.

Jc

[stephl]

A noter que si on descend la borne maximale, j'ai presque les mêmes temps entre les deux.

Les résultats que j'ai donnés ont été obtenus en prenant des nombres aléatoires dans l'intervalle [0,2^31]. J'ai lancé le programme plusieurs fois et j'ai toujours le même écart (à 3 ou 4 secondes près avec 1 milliard d'appels).

[NiamorH]

merci beaucoup à vous deux

[fearyourself]

Les résultats que j'ai donnés ont été obtenus en prenant des nombres aléatoires dans l'intervalle [0,2^31]. J'ai lancé le programme plusieurs fois et j'ai toujours le même écart (à 3 ou 4 secondes près avec 1 milliard d'appels).

Par curiosité, compilé avec quel compilateur, quel OS, quelles options et quel processeur ?


Jc

[Jean-Marc.Bourguet]

J'aurais fait quelque chose comme:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
    unsigned long pwr = ~((unsigned long)-1)>>1);
#if ULONG_MAX / (1U<<16) > (1U<<16)
#if ULONG_MAX / (1U<<32) > (1U<<32)
    if (n <= (pwr >> 64)) { pwr >>= 64; }
#endif
    if (n <= (pwr >> 32)) { pwr >>= 32; }
#endif
    if (n <= (pwr >> 16)) { pwr >>= 16; }
    if (n <= (pwr >>  8)) { pwr >>=  8; }
    if (n <= (pwr >>  4)) { pwr >>=  4; }
    if (n <= (pwr >>  2)) { pwr >>=  2; }
    if (n <= (pwr >>  1)) { pwr >>=  1; }
    return pwr;

Valable jusqu'a 128 bits (pour aller plus loin, il suffit d'ajouter les #if qui vont bien).

[stephl]

Par curiosité, compilé avec quel compilateur, quel OS, quelles options et quel processeur ?

compilateur: Borland C Builder 5.5
OS: WinXP
CPU: Intel Celeron 1.2GHz
commande: bcc32 power2.c

Avec 1 milliard d'appels:

Code :

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

1
2
3
4
C:\Documents and Settings\stephane\Mes documents\Temp>power2 1000
MÚthode fearyourself: 95.407 s
MÚthode Jean-Marc Bourguet: 54.984 s
MÚthode stephl: 66.281 s

Le source:

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
 
 
#define ARRAYSIZE 1000000
 
 
unsigned int number[ARRAYSIZE];
 
 
/****************************************************************************
Solution de fearyourself
****************************************************************************/
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;
}
 
 
/****************************************************************************
Solution de Jean-Marc Bourguet
****************************************************************************/
unsigned int pwrf(unsigned int n)
 {
 unsigned long pwr = ~(((unsigned long)-1)>>1);
#if ULONG_MAX / (1U<<16) > (1U<<16)
#if ULONG_MAX / (1U<<32) > (1U<<32)
    if (n <= (pwr >> 64)) { pwr >>= 64; }
#endif
    if (n <= (pwr >> 32)) { pwr >>= 32; }
#endif
    if (n <= (pwr >> 16)) { pwr >>= 16; }
    if (n <= (pwr >>  8)) { pwr >>=  8; }
    if (n <= (pwr >>  4)) { pwr >>=  4; }
    if (n <= (pwr >>  2)) { pwr >>=  2; }
    if (n <= (pwr >>  1)) { pwr >>=  1; }
    return pwr;
 }
 
 
/****************************************************************************
Solution de stephl
****************************************************************************/
unsigned int power2sup(unsigned int i)
 {
 unsigned int power;
 
 for (power=1;power<i;power<<=1);
 return power;
 }
 
 
/****************************************************************************
Test
****************************************************************************/
void doit(int nbval,int ntimes,unsigned int (*func)(unsigned int),
char *methodname)
 {
 unsigned int starttime,duration,res;
 int i,j;
 
 for (j=0,starttime=GetTickCount();j<ntimes;++j)
  for (i=0;i<nbval;++i)
   {
   res=(*func)(number[i]);
#ifdef OUTPUT
   printf("n=%u\tres=%u\n",number[i],res);
#endif
   }
 duration=GetTickCount()-starttime;
 printf("Méthode %s: %.3f s\n",methodname,(double) duration/1000.0);
 }
 
 
/****************************************************************************
main
Paramètres optionnels pour l'appel du programme: [NB_FOIS] [NB_VALEURS]
****************************************************************************/
#define MAXPOW2 (1U<<((sizeof (int)<<3)-1))
 
 
int main(int argc,char **argv)
 {
 int nbval,i,ntimes;
 
 if (argc<3 || (nbval=atoi(argv[2]))>ARRAYSIZE) nbval=ARRAYSIZE;
 if (argc==1) ntimes=1;
 else ntimes=atoi(argv[1]);
 srand(GetTickCount());
 for (i=0;i<nbval;++i) number[i]=rand()%(MAXPOW2+1);
 doit(nbval,ntimes,pow2sup,"fearyourself");
 doit(nbval,ntimes,pwrf,"Jean-Marc Bourguet");
 doit(nbval,ntimes,power2sup,"stephl");
 return 0;
 }

[fearyourself]

compilateur: Borland C Builder 5.5
OS: WinXP
CPU: Intel Celeron 1.2GHz
commande: bcc32 power2.c

Avec 1 milliard d'appels:

Code :

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

1
2
3
4
C:\Documents and Settings\stephane\Mes documents\Temp>power2 1000
MÚthode fearyourself: 95.407 s
MÚthode Jean-Marc Bourguet: 54.984 s
MÚthode stephl: 66.281 s

Je pense que ton compilateur n'optimise pas très bien ma fonction, car j'obtiens :

$ cat /proc/cpuinfo | head
processor : 0
vendor_id : GenuineIntel
cpu family : 15
model : 3
model name : Intel(R) Pentium(R) 4 CPU 3.00GHz
stepping : 3
cpu MHz : 2993.014
cache size : 1024 KB

$ uname -a
Linux perceval 2.6.17-11-generic #2 SMP Thu Feb 1 19:52:28 UTC 2007 i686 GNU/Linux

$ gcc -v
Using built-in specs.
Target: i486-linux-gnu
Configured with: ../src/configure -v --enable-languages=c,c++,fortran,objc,obj-c++,treelang --prefix=/usr --enable-shared --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --enable-nls --program-suffix=-4.1 --enable-__cxa_atexit --enable-clocale=gnu --enable-libstdcxx-debug --enable-mpfr --enable-checking=release i486-linux-gnu
Thread model: posix
gcc version 4.1.2 20060928 (prerelease) (Ubuntu 4.1.1-13ubuntu5)

$ gcc -O3 test.c
$ ./a.out 1000

Méthode fearyourself: 27.000 s
Méthode Jean-Marc Bourguet: 19.000 s
Méthode stephl: 34.000 s

Comme quoi, le processeur sur lequel tu te trouves, le compilateur et les options de compilations changent beaucoup de choses...

Jc

PS: La seule chose que j'ai changé du code c'est que j'ai virer windows.h et l'appel de temps windows.

[Jean-Marc.Bourguet]

Sur un Intel(R) Xeon(TM) CPU 3.06GHz, j'optiens:

Méthode fearyourself: 27.447 s
Méthode Jean-Marc Bourguet: 18.670 s
Méthode stephl: 56.673 s

Et sur une sparc

Méthode fearyourself: 40.133 s
Méthode Jean-Marc Bourguet: 27.094 s
Méthode stephl: 48.045 s

(Les temps absolus ne sont pas necessairement representatifs de la machine qui etait un peu chargee, mais les temps relatifs devraient etre bons).

Je crois que le processeur joue un role aussi.

[stephl]

...
C'est très étrange. Mon essai me faisait penser que la méthode de fearyourself était moins bonne, alors que c'est le contraire: dans 3 essais sur 4, elle est plus performante que la mienne. Puis-je savoir Jean-Marc.Bourguet quel compilateur vous avez utilisé?
Toujours avec Borland, j'ai essayé sans optimisation et avec optimisation en vitesse, et j'obtiens sensiblement les mêmes temps?!?!
Si vous aviez activé les optimisations lors de vos compilations respectives, pourriez-vous essayer de les désactiver pour voir? De mon côté, je ne peux pas utiliser gcc, mais je vais tout de même essayer avec Visual.
EDIT
Avec Visual sur la même machine:

Code :

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

1
2
3
MÚthode fearyourself: 82.453 s
MÚthode Jean-Marc Bourguet: 52.016 s
MÚthode stephl: 81.937 s