Sujet Précédent Sujet Suivant

VITESSE ALGO, CONCOURS POUR TOUS

BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019 - 28 févr. 2005 à 19:22
CriPpLe Messages postés 78 Date d'inscription lundi 26 juillet 2004 Statut Membre Dernière intervention 26 avril 2005 - 7 mars 2005 à 00:52
DWORD __fastcall Puiss2SupEgal_C(DWORD d)
{
DWORD r, n;
if(!d) return 0;
if(d & 1) d++;
r = 0x80000000;
n = d;
if(d & 0x80000000) goto verifInf;
do {
r >>= 1;
d <<= 1;
} while(!(d & 0x80000000));
verifInf:
if(r < n) r <<= 1;
if(!r) r = 0xFFFFFFFF;
return r;
}

Cette fonction retourne la plus proche puissance de 2 >= au param.
Si param == 0 doit retourner 0.
Si param > (2 puiss 31) doit retourner 0xFFFFFFFF;

Voila, je suis ouvert à toute proposition plus rapide, prog de test est fait.
Pas de table précalculée ni série de 32 'if' ou chose de ce genre pour cause de taille de code.
J'ai deja fait version ASM (dispo sur demande), est 6 fois + rapide que celle ci mais je voudrais savoir si vous avez des idées d'amélioration en C.

Toutes les propositions seront mesurées.
A vos claviers et merci de votre participation.

ciao...
BruNews, MVP VC++

30 réponses

Précédent
  • 1
  • 2
Réponse 21 / 30
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
1 mars 2005 à 12:05
Très bien, pourrai-tu stp le mettre en comment sur la source, que chacun puisse accéder à la meilleure solution finale, merci d'avance.

ciao...
BruNews, MVP VC++
0
Réponse 22 / 30
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
1 mars 2005 à 12:30
la version 1 est + lente mais la 2 est nettement mieux, je la mets sur la source.

ciao...
BruNews, MVP VC++
0
Réponse 23 / 30
cs_JCDjcd Messages postés 1138 Date d'inscription mardi 10 juin 2003 Statut Membre Dernière intervention 25 janvier 2009 4
1 mars 2005 à 13:15
la condition "Si param > (2 puiss 31) doit retourner 0xFFFFFFFF;

" n'est pas repectee, mais il suffit de rajouter un if a la fin (cas negatif non pris en compte car unsigned)

Pourquoi faire simple quand on peut faire compliqué ?
0
Réponse 24 / 30
steve_clamage Messages postés 475 Date d'inscription dimanche 3 octobre 2004 Statut Membre Dernière intervention 11 août 2006 5
1 mars 2005 à 18:10
unsigned ge_pow2( unsigned u )

{

unsigned m;

int p;



if( !(u & (u-1)) )

return u;



if( u <= 0x80000000 )

{

m = 1;

p = 32;



while( !(u & 0x80000000) )

{

u <<= 1;

--p;

}



return m <<= p;

}



return 0xffffffff;

}
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
Réponse 25 / 30
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
1 mars 2005 à 19:55
presque 2 fois plus lent que celle de JCDjcd, j'ai l'impression qu'il sera dur à battre.

ciao...
BruNews, MVP VC++
0
Réponse 26 / 30
steve_clamage Messages postés 475 Date d'inscription dimanche 3 octobre 2004 Statut Membre Dernière intervention 11 août 2006 5
1 mars 2005 à 20:09
désolé, j'avais pas vu son code !
0
Réponse 27 / 30
cs_JCDjcd Messages postés 1138 Date d'inscription mardi 10 juin 2003 Statut Membre Dernière intervention 25 janvier 2009 4
1 mars 2005 à 22:32
moi sur 32bits la methode en O(log(n)) est plus rapide que celle en O(log(log(n))), mais par contre en 64bits, elle le bat avec un facteur 4.

Pourquoi faire simple quand on peut faire compliqué ?
0
Réponse 28 / 30
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
1 mars 2005 à 23:30
Matt67 vient d'en proposer un sur la source équivalent à celui de JCDjcd.

ciao...
BruNews, MVP VC++
0
Réponse 29 / 30
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
2 mars 2005 à 18:04
JCDjcd > voudrait-tu jeter un oeil ici
http://www.cppfrance.com/code.aspx?ID=29847
paraitrait que ta version ne donne pas les résultats en conformité avec le cahier des charges.
Je précise que je n'ai pas eu du tout le temps de vérifier.

ciao...
BruNews, MVP VC++
0
Réponse 30 / 30
CriPpLe Messages postés 78 Date d'inscription lundi 26 juillet 2004 Statut Membre Dernière intervention 26 avril 2005
7 mars 2005 à 00:52
Code proposé par une de mes connaissances, Silex:



,
<NOBR>unsigned __fastcall mine(unsigned d)
{
// Same control shit
if(!d) return 0;
if((d & d-1) == 0)
return d;

if(d > 0x80000000)
return 0xFFFFFF;

// What should be faster (constant time)
return log((double)d)/log(2.0);
</NOBR>
0

Discussions similaires

script jeu concours
webide -
webide -

2 réponses
Calcul d'une vitesse
vanelotof -
aziz36 -

5 réponses
Algo championnat de foot
cs_yukiharu -
billou_13 -

2 réponses
[j2me] Vitesse des boucles pour un dessin
Twub -
DARKSIDIOUS -

8 réponses
les algorithme genetique
maximus888 -
awatifaaa -

6 réponses
Rejoignez-nous