/* Topic des codeurs couche-tard [4] */

grim7reaper · Le 02/03/2011, à 21:43

@Rolinh : Je pensais que le nom de la fonction était assez explicite : la fonction renvoie la première puissance de 2 supérieure au nombre passé en paramètre.
Pour le code complet, bah pour le test c'était juste un main avec un printf comme tu l'as fait. Non, il n'y a pas de valeurs particulières pour le test.
Sinon le résultat obtenu est bien celui attendu, donc c'est bon ça fonctionne bien comme prévu

Pour le contexte, c'est plus ou moins la suite de mon post en haut de cette page (ma première tentative ^^).
En fait c'est pour la construction de ma table de hachage : je prend une taille en 2^n (comme ça je peut utiliser 0,5 pour c1 et c2 dans ma sonde quadratique pour avoir des résultats pas trop mauvais).
Je pourrais avoir des résultats sûrement meilleurs en prenant une taille en nombre premier, mais c'est un peu plus chiant à mettre en place (et comme je l'ai dit, je suis déjà en manque de temps et ma table ne devrait pas atteindre une taille énorme).

Merci de ton retour

@Pylade : Ok, normalement ça devrait fonctionner chez toi aussi (ou alors je suis vraiment passé à côté d'un truc, ce qui est possible vu que je faisait ça pendant un cours ^^)

Dernière modification par grim7reaper (Le 02/03/2011, à 21:46)

Rolinh · Le 02/03/2011, à 21:52

grim7reaper a écrit :

@Rolinh : Je pensais que le nom de la fonction était assez explicite : la fonction renvoie la première puissance de 2 supérieure au nombre passé en paramètre.

Voui, je m'en étais douté ^^
La question était plus dans le sens: "dans quel but/contexte" et est-ce partie intégrante d'autre chose etc. mais tu as répondu à ces questions

grim7reaper a écrit :

Merci de ton retour

De rien

Pylades · Le 02/03/2011, à 22:03

Euh, je suis le seul à être choqué par le truc suivant ?

if(n =! 0)
{
  …
}
else
  n = 0;

grim7reaper · Le 02/03/2011, à 22:06

Ouais en effet, le else est totalement inutile.
Mais bon, j'ai fait ça en suivant un cours en parallèle donc bon j'était pas non plus super attentif ^^

Dernière modification par grim7reaper (Le 02/03/2011, à 22:08)

Rolinh · Le 02/03/2011, à 22:09

je n'y avais même pas fait gaffe ^^

Pylades · Le 02/03/2011, à 22:19

Voici le code que j'ai testé (oui j'ai changé le type car pour un test il n'y a pas de raisons d'avoir de size_t ; et puis ça évite un cast dans le printf) :

#include <stdio.h>
#include <limits.h>

static unsigned long next_highest_power_of_2(unsigned long n)
{
    if(n)
    {
        unsigned long i;

        --n;
        for(i = 1; i < sizeof n * CHAR_BIT; i <<= 1)
            n |= n >> i;
        ++n;
    }

    return n;
}

int main(void)
{
    printf("%lu\n", next_highest_power_of_2(3436357648732626854U));
    return 0;
}

Le résultat est bien celui attendu : 4611686018427387904.

Et on a bien 9223372036854775808 pour 5436357648732626854U.

Dernière modification par Pylade (Le 02/03/2011, à 22:22)

grim7reaper · Le 02/03/2011, à 22:25

\o/

Merci de ton test
(Ptain le coup du else, c'était la lose quand même ^^)

tshirtman · Le 02/03/2011, à 22:37

je sais plus, en C,

if (n)

est pas équivalent à

if (n != 0)

?

grim7reaper · Le 02/03/2011, à 22:40

Si, c'est pareil.

Dernière modification par grim7reaper (Le 02/03/2011, à 22:40)

tshirtman · Le 02/03/2011, à 22:44

ah oui, je viens de voir que pylade avait fait le changement aussi

tshirtman · Le 02/03/2011, à 22:49

@T'Man : Tiens d'ailleurs, c'est VS 2010 Ultimate obligatoire dans mon cours... [ah ben faut bien que ça serve le MSDNAA de l'école <_<' ] exit vim/Mono!
Pourtant j'étais parti pour essayer.. Mais nooon, je l'ai bien profond!

hmmm… bon courage?

franchement moi je m'en foutrais de ce qu'ils imposent, je bosse sur ma machine s'il le faut, mais je bosse comme je veux.

(bon, je suppose qu'il faut rendre un fichier de projet visual studio, et s'assurer que ça compile dessus, mais monodevelop sait faire)

grim7reaper · Le 02/03/2011, à 23:00

Ptain, faut vraiment que je nettoie mon code…
Parce que si le prof (ou quelqu'un d'autre) tombe là-dessus, il risque de se poser des questions

[…]
fputs("Fuck that! That one has a Mana bar!\n", stderr);
[…]
fputs("All your base are belong to us\n", stderr);
[…]
fputs("Herp Derp!\n", stderr);
[…]
fputs("The consequences will never be the same\n", stderr);
[…]
fputs("The cake is a lie!!\n", stderr)

Dernière modification par grim7reaper (Le 02/03/2011, à 23:01)

Pylades · Le 02/03/2011, à 23:15

Tiens, j'ai fait une version avec laquelle je suis plus rapide que toi pour les grands nombres.

unsigned long next_highest_power_of_2(unsigned long n)
{
    unsigned long i;
    for (i = ULONG_MAX/2+1; i; i>>=1)
        if (i < n)
            return i<<1;
    return 1U;
}

(Ouais, l'initialisation de ma boucle n'est pas super élégante.)
(Et oui, moi je retourne un quand on me donne zéro, car zéro n'est pas une puissance de deux.)

Dernière modification par Pylade (Le 02/03/2011, à 23:16)

grim7reaper · Le 02/03/2011, à 23:49

Mouais bof. C'est loin d'être meilleur (sauf cas particuliers, donc bof quoi).

Sur un 1UL en 64 bits, tu vas bouffer 64 itérations. Moi en 6 itérations c'est plié, et pour n'importe quel nombre en 64 bits.
Mon algo a un nombre d'itérations constant : log2(nombre de bits), et ça c'est classe.

Sur 32 bits, tu deviens meilleur que moi à partir de 268 435 457.
Si j'applique ton algo de 0 à UCHAR_MAX (8 bits) tu fais 6 661 itérations, moi 765.
Si j'applique ton algo de 0 à USHRT_MAX (16 bits) tu fais 1 179 661, moi 262 140.
…
Le choix est vite vu

Et cerise sur le gâteau : je peux rendre mon code générique (moyennant l'ajout de quelques contraintes sur la localisation de son utilisation, je l'admet mais rien n'est parfait) en le « templatisant » (non, je n'utilise pas le C++, je reste en C), toi non (vu que tu utilises ULONG_MAX dans tout les cas)

Sinon moi je retourne 0 car si le mec m'a passé une taille de 0, bah ça reste 0 (mais sinon, dans l'absolu je suis d'accord avec ton retour de 1).

Dernière modification par grim7reaper (Le 03/03/2011, à 00:07)

Kanor · Le 03/03/2011, à 00:04

grim7reaper a écrit :

Ptain, faut vraiment que je nettoie mon code…
Parce que si le prof (ou quelqu'un d'autre) tombe là-dessus, il risque de se poser des questions
[…]
fputs("Fuck that! That one has a Mana bar!\n", stderr);
[…]
fputs("All your base are belong to us\n", stderr);
[…]
fputs("Herp Derp!\n", stderr);
[…]
fputs("The consequences will never be the same\n", stderr);
[…]
fputs("The cake is a lie!!\n", stderr)

Moi je résiste pour ne pas écrire des commentaires trop "vulgaire"

Pylades · Le 03/03/2011, à 00:20

Ouais, le gain est plus flagrant en 64 bits…

Mais je ne suis pas obligé d'utiliser ULONG_MAX/2+1 ; je peux aussi très bien faire 1 << (sizeof i * CHAR_BIT - 1).

Dernière modification par Pylade (Le 03/03/2011, à 00:43)

grim7reaper · Le 03/03/2011, à 00:28

Ouais, et là tu pourras « templatiser » ton code.
Bon, ça resteras une daube dans le cas général (cf. mes tests), mais ça sera un peu mieux quand même.

Avec du code « templatisé » tu peux ecrire des trucs comme ça :

generic_next_highest_power_of_2(unsigned short, 777);
generic_next_highest_power_of_2(unsigned, 131030U);
generic_next_highest_power_of_2(unsigned long, 4398046511062UL);

Tiens, faudra que je ponde un article là dessus (je vois bien le truc en 3 parties : approche naïve, optimisation, généricité).

Dernière modification par grim7reaper (Le 03/03/2011, à 00:33)

Pylades · Le 03/03/2011, à 00:32

What?!

grim7reaper · Le 03/03/2011, à 00:39

Le C, c'est beau et puissant
Le C c'est bon, mangez-en

Et ça, quasiment sans modifier le code de la fonction.

Bon, ça a aussi des inconvénients hein, faut pas croire. Il n'y a pas de miracles.
Comme je le disais dans un de mes précédents posts ça ajoute quelques contraintes sur la localisation de son utilisation et ce n'est pas applicable à toute les fonctions (enfin si, mais des fois c'est vraiment contre-productif de le faire). Mais bon, en général le prix à payer est faible comparé au gain.

Sur ce, il faut que j'aille un peu préparer mon exam de demain (oral + écrit).

Dernière modification par grim7reaper (Le 03/03/2011, à 00:43)

Pylades · Le 03/03/2011, à 00:46

Ouais, ben je veux bien un article là-dessus ; car là je n'y comprends rien.

(Et puis mon morceau de code n'avait pas pour vocation d'être pertinent, mais juste de me permettre de me la ramener en disant que je suis plus rapide sur les grands nombres. )

Et bonne chance pour demain !

Dernière modification par Pylade (Le 03/03/2011, à 00:46)

Kanor · Le 03/03/2011, à 00:48

Maitre du C vous pensez quoi de ce bouquin
http://framabook.org/c20h.html

Pylades · Le 03/03/2011, à 00:50

Ah, oui, je vois : c'est une macro. Ça explique le unsigned long qui se balade tout seul en temps qu'argument…

Kanor a écrit :

Maitre du C vous pensez quoi de ce bouquin
http://framabook.org/c20h.html

Je ne suis pas un maître du C ; et je ne l'ai pas lu, pour ma part…

Dernière modification par Pylade (Le 03/03/2011, à 00:51)

tshirtman · Le 03/03/2011, à 01:22

aujourd'hui, quelques articles m'ont donnés envie de me mettre au lisp

Кຼزດ · Le 03/03/2011, à 01:23

Pylades · Le 03/03/2011, à 01:33

Bon, qu'est-ce que je pourrais bien mettre dans mon README ? Grande question…

Ubuntu-fr

Navigation

Liens de recherche

Annonce

#126 Le 02/03/2011, à 21:43

Re : /* Topic des codeurs couche-tard [4] */

#127 Le 02/03/2011, à 21:52

Re : /* Topic des codeurs couche-tard [4] */

#128 Le 02/03/2011, à 22:03

Re : /* Topic des codeurs couche-tard [4] */

#129 Le 02/03/2011, à 22:06

Re : /* Topic des codeurs couche-tard [4] */

#130 Le 02/03/2011, à 22:09

Re : /* Topic des codeurs couche-tard [4] */

#131 Le 02/03/2011, à 22:19

Re : /* Topic des codeurs couche-tard [4] */

#132 Le 02/03/2011, à 22:25

Re : /* Topic des codeurs couche-tard [4] */

#133 Le 02/03/2011, à 22:37

Re : /* Topic des codeurs couche-tard [4] */

#134 Le 02/03/2011, à 22:40

Re : /* Topic des codeurs couche-tard [4] */

#135 Le 02/03/2011, à 22:44

Re : /* Topic des codeurs couche-tard [4] */

#136 Le 02/03/2011, à 22:49

Re : /* Topic des codeurs couche-tard [4] */

#137 Le 02/03/2011, à 23:00

Re : /* Topic des codeurs couche-tard [4] */

#138 Le 02/03/2011, à 23:15

Re : /* Topic des codeurs couche-tard [4] */

#139 Le 02/03/2011, à 23:49

Re : /* Topic des codeurs couche-tard [4] */

#140 Le 03/03/2011, à 00:04

Re : /* Topic des codeurs couche-tard [4] */

#141 Le 03/03/2011, à 00:20

Re : /* Topic des codeurs couche-tard [4] */

#142 Le 03/03/2011, à 00:28

Re : /* Topic des codeurs couche-tard [4] */

#143 Le 03/03/2011, à 00:32

Re : /* Topic des codeurs couche-tard [4] */

#144 Le 03/03/2011, à 00:39

Re : /* Topic des codeurs couche-tard [4] */

#145 Le 03/03/2011, à 00:46

Re : /* Topic des codeurs couche-tard [4] */

#146 Le 03/03/2011, à 00:48

Re : /* Topic des codeurs couche-tard [4] */

#147 Le 03/03/2011, à 00:50

Re : /* Topic des codeurs couche-tard [4] */

#148 Le 03/03/2011, à 01:22

Re : /* Topic des codeurs couche-tard [4] */

#149 Le 03/03/2011, à 01:23

Re : /* Topic des codeurs couche-tard [4] */

#150 Le 03/03/2011, à 01:33

Re : /* Topic des codeurs couche-tard [4] */

Pied de page des forums