VITESSE ALGO, CONCOURS POUR TOUS

Question

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++

cs_Matt67 · Answer

Bonsoir, J'essaie : unsigned Puiss2SupEgal_C(unsigned d) { unsigned Depart = 0x80000000; // Difficile de faire mieux if(!d) return 0; // Ca tombe pile poil if((d & d-1) == 0) return d; // Trop grand if(d > Depart) return 0xFFFFFF; while((Depart & d) == 0) Depart >>= 1; Depart <<= 1; return Depart; } Matt...

BruNews · Answer

Merci je teste, r&#233;sultats sous peu.

ciao...
BruNews, MVP VC++

BruNews · Answer

598283328 ticks la mienne
599283328 la tienne
on peut dire &#233;quivalent, je n'ai pas v&#233;rifi&#233; les r&#233;sultats de la fonction.

ciao...
BruNews, MVP VC++

cs_Matt67 · Answer

Bonsoir,



(Bien essay&#233; Matt)

Ok, je vais voir si on peut faire mieux,


Matt...

cs_Matt67 · Answer

Une petite modif dans la boucle while (je ne pense pas que ca change grand chose mais bon) unsigned Puiss2SupEgal_C(unsigned d) { unsigned Depart = 0x80000000; // Difficile de faire mieux if(!d) return 0; // Ca tombe pile poil if(!(d & d-1)) return d; // Trop grand if(d > Depart) return 0xFFFFFF; while(((Depart >>1) & d) 0); Depart <<= 1; return Depart; } Matt...

BruNews · Answer

identique.

Le souk c'est qu'on a pas d'op&#233;rateur de scann bits en C, on est oblig&#233; de boucler.

ciao...
BruNews, MVP VC++

cs_Matt67 · Answer

Je ne vois pas trop comment faire autrement.

Si quelqu'un trouve un autre algo !!!

Bonne soir&#233;e,
Matt...

steve_clamage · Answer

une version avec une lookup table:



unsigned Puiss2SupEgal_C( unsigned u )

{

    static const unsigned mask [] =

    {

        0x00000000,

        

        0x00000001,

        0x00000002,

        0x00000004,

        0x00000008,

        

        0x00000010,

        0x00000020,

        0x00000040,

        0x00000080,

        

        0x00000100,

        0x00000200,

        0x00000400,

        0x00000800,

        

        0x00001000,

        0x00002000,

        0x00004000,

        0x00008000,

        

        0x00010000,

        0x00020000,

        0x00040000,

        0x00080000,

        

        0x00100000,

        0x00200000,

        0x00400000,

        0x00800000,

        

        0x01000000,

        0x02000000,

        0x04000000,

        0x08000000,

        

        0x10000000,

        0x20000000,

        0x40000000,

        0x80000000,

        

        0xffffffff

    };

    

    const int *p = mask;

 

    while( *p < u)

       p++;

    return *p;

}

Hylvenir · Answer

salut,



1 doit renvoyer 2 ou 1  ? vaut deux fonctions ne sont pas d'accord.



bizarre sur les perfs, je trouve quasiment deux fois plus rapide pour la fonction de Matt ?

Je vais essayer avec cl pour voir.


Ma participation &#224; la saturation du net:
http://hylvenir.free.fr

steve_clamage · Answer

faute de frappe, il faut mettre

const unsigned*p = mask;

BruNews · Answer

1 doit renvoyer 2, d&#233;sol&#233; si je n'&#233;tais pas assez pr&#233;cis.

Pas de table pr&#233;calcul&#233;e, la taille du prog augmente trop vite, ici deja 128 octets alors quand je porterai en 64 bits...

ciao...
BruNews, MVP VC++

Hylvenir · Answer

Ok, apr&#232;s r&#233;glage, les fonctions se valent en gros.

Steve, ta fonction est plus lente, j'ai l'impression.



C'est pas s&#251;r qu'on puise faire beaucoup mieux en C.

l'asm a ces avantages dans ce genre de situation en tout cas ;)

Ma participation &#224; la saturation du net:
http://hylvenir.free.fr

BruNews · Answer

steve_clamage > je viens malgr&#233; tout de tester, c'est 2 fois plus lent que les autres versions C.

ciao...
BruNews, MVP VC++

steve_clamage · Answer

Hylvenir, oui mais ca depend du jeu d'essai,
logiquement en dessous de 0x00010000 ca devrais etre plus rapide (plus
tant que le nombre tant vers 0, sur les petits nombres j'obtiens
jusqu'&#224; x10) sinon c'est plus lent, dans ce sens une solution optimale
serais d'avoir deux lkt (une normale et une reverse) et tester si le
nombre est < 0x00010000.



BruNews, tu veux vraiment avoir une solution performante et peut couteuse en m&#233;moire ? on doit souvent faire le choix, non ?

steve_clamage · Answer

moi avec un nombre < 2048 non puissance de 2 c'est plus rapide, avec
une version avec deux tables on gagnera aussi sur les grands nombres.

BruNews · Answer

non pas forc&#233;ment, en calcul intensif on doit forc&#233;ment passer par ASM.
Voila o&#249; j'en &#233;tais, je verrai si encore 1 ou 2 cycles trainent mais devrait pas y avoir plus.
Le truc c'est qu'il n'y a aucun bouclage:

__declspec(naked) DWORD __fastcall Puiss2SupEgal_ASM(DWORD d)
{
  __asm {
    mov     eax, ecx
    cmp     eax, 1
    jb      short ramExit
    ja      short nbrOK
    inc     eax
nbrOK:
    mov     edx, eax
    bsr     ecx, eax
    mov     eax, 1
    shl     eax, cl
    cmp     eax, edx
    jae     short ramExit
    shl     eax, 1
    jnz     short ramExit
    mov     eax, -1
ramExit:
    ret     0
  }
}

en fait je m'&#233;tais gourr&#233;, le benf n'est que de 3 fois sur les grands calculs mais bon c'est d&#233;ja &#231;a.

ciao...
BruNews, MVP VC++

ciao...
BruNews, MVP VC++

steve_clamage · Answer

je veux dire avec un nombre  < 4096 non puissance de 2 c'est plus rapide, et avec la version avec deux tables ca sera bon pour >65536 et <2048

cs_JCDjcd · Answer

Je suis aussi de dire que tout cela depend a la fois du test de comparaison (si n est uniforme alors repondre 31 a une probabilite de 0.5, repondre 30 de 0.25, ect ... alors que si c'est le resultat qui est aleatoire "genre 1< n); return i; } } // MaxPow2_v1() //-------------------------------------------- TYPE MaxPow2_v2(TYPE n) { int i = 0; int di = N>>1; do { if(n >= (((TYPE)1) << (i+di))) { i += di; } }while((di >>= 1) > 0); return i; } // MaxPow2_v2() la notation est mauvaise : les fonctions devraient etre nommees MinPow2, mais bon ... La seconde methode consiste en une dichotomie sur la place du bit 1 le plus a gauche, d'ou on en deduit la complexite. Pourquoi faire simple quand on peut faire compliqué ?

BruNews · Answer

Salut,
je viens de mettre ici:
http://www.cppfrance.com/code.aspx?ID=29847
chacun pourra proc&#233;der aux tests directement et j'esp&#232;re qu'on aura ainsi des trouvailles int&#233;ressantes, rien de tel que la forme 'concours' pour stimuler les neurones.

ciao...
BruNews, MVP VC++

cs_JCDjcd · Answer

Chez moi, mes deux fonctions battent ta version C, mais pas ASM.
Il faudrait aussi faire les testes en 64 bits.

Pourquoi faire simple quand on peut faire compliqu&#233; ?

VITESSE ALGO, CONCOURS POUR TOUS

30 réponses

Votre réponse

Discussions similaires