Calculer Log2(n)

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour tout le monde ! Dans le cadre de la résolution de sudoku, j'aurais besoin de calculer Log2(n) ! :)

Pour ceux qui ne savent pas à ce que cela correspond, c'est tout bêtement : La puissance nécessaire à 2 pour faire n

Dans le monde normal, on utilise souvent ln ou Log10. Dans les deux cas il s'agit juste d'un changement de base (dans ma phrase précédente, changer 2 en e (le chiffre) ou 10). Mais en informatique ca peut être pratique pour savoir quel est le bit à un.

Exemple : Mon nombre est 16 (donc 00010000 en binaire sur 1 octets) et je voudrais passer de 16 à 4 (qui est Log2(n) ou encore le poids du bit à 1).

Maintenant que vous savez mon problème, voici deux solutions que j'ai trouvé et j'aimerais savoir si vous en connaissez une plus rapide ! :)

Première solution : Ln(n)/Ln(2)

C'est la définition mathématique de Log2(n) Problème : le calcul de ln est très très lent et je vais en avoir souvent besoin !

Deuxième solution :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int log2(int n){
    if(!isAPowerOfTwo(n))
        return -1;        // Valeur pour dire qu'il y a un bug

    int i = 0;
    while( (n % 2) == 0){
        ++i;
        n >> 1;          // Fonctionnerai aussi en faisant n /= 2
    }
    return i;
}

Merci d'avance ! :)

Édité par Ricocotam

+0 -0

Cette réponse a aidé l'auteur du sujet

Il y a plusieurs façon de calculer le Log2(n), j'en ai trouvé une particulièrement en utilisant la spécification IEEE d'un double sur 64 bits.

1
2
3
4
5
6
7
8
int v; // 32-bit integer to find the log base 2 of
int r; // result of log_2(v) goes here
union { unsigned int u[2]; double d; } t; // temp

t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] = 0x43300000;
t.u[__FLOAT_WORD_ORDER!=LITTLE_ENDIAN] = v;
t.d -= 4503599627370496.0;
r = (t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] >> 20) - 0x3FF;

Tout d'abord, il faut savoir ce qu'est un union pour comprendre ce code. En effet, en créant un union entre un int[2] et un double, nous pouvons manipuler cette valeur comme un int[2] ou un double. C'est notamment très utilisé entre un int et un float, on peut profiter de la représentation mémoire d'un int ou d'un float pour une même valeur - ce qui est le cas pour Quake III Arena lors de la sérialisation des données.

Il faut ensuite savoir que les 12 premiers bits d'un double concerne le signe (sur un bit) et l'exposant. Au début, on mets l'exposant à 252. Dans le reste de notre double, on mets la valeur. Ceci est possible grâce à l'union mais il faut aussi faire attention à l'endianess de nos valeurs pour pas se tromper de sens. En effet, selon l'endianess de l'ordinateur, l'exposant est à la fin du double donc à la case [1] de notre tableau de int. Le test retournant 0 ou 1 selon l'endianess nous permet de nous abstraire de cette contrainte.

Ensuite, on enlève à notre valeur (entant que double) la valeur 252. Grâce à ce calcul, l'ordinateur (concernant la manipulation des double) va nous mettre l'exposant sur une puissance de 2 nécessaire à notre valeur de départ. Ensuite, il suffit de manipuler nos 12 premiers bits (donc un décalage de 20 bits - 32-12) et le soustraire par le maximum de l'exposant possible sur un double, à savoir 1023 (donc 0x3FF).

En vrai, ce calcul n'est pas très efficient sur une processeur normal. Peut être qu'avec la technologie CUDA peut mieux s'en tirer, je pense. De plus, il faut faire attention à l'endianess.

Ensuite, tu as la technique utilisant les indices de De Bruijn qui pourrait être plus rapide mais il se fait tard et je pense qu'il faudrait un peu plus sur l'explication de celui-ci !

Édité par Dinosaure

Auteur du sujet

J'ai pas compris dans le détail mais en général ouai :)

Le truc c'est que j'en aurait besoin pour un bit de poids 9 maximum, du coup, est-ce toujours aussi pertinent ? Je vais voir le lien et merci de ta réponse ! :)

+0 -0
Auteur du sujet

Le but est de résoudre des sudokus et plus ça va vite, meilleur est ma note :p En fait j'en ai besoin pour trouver le poids du most significant bit. Mais ce matin j'ai pensé à faire une table où je peux retrouver assez facilement la corrélation puisque les traitements sont dans cet ordre :

  • Chiffres de 1 à 9 => transformer en nombre de 20 à 28

  • Traitements diverses pour résoudre le sudoku

  • Passage des 2x en chiffres de 1 à 9 Donc je pourrais bêtement stocker dans une structure associative :)

Édité par Ricocotam

+0 -0

Une solution générique, pour le type unsigned short int.

1
2
// File log2.h
unsigned short int log2(unsigned short int m);
 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
// File log2.cpp
#include <climits>
#include <cassert>

unsigned short int init_ushort_max_power2()
{
  unsigned short int u = USHRT_MAX;
  u >>= 1;
  ++u;
  return u;
}

const unsigned short int ushort_max_power2 = init_ushort_max_power2();

unsigned short int log2(unsigned short int m)
{
  unsigned short int n = ushort_max_power2;
  while(n > 0 && n != m)
    n >>= 1;
  if(n > 0)
  {
    unsigned short int r = 0;
    while(n >>= 1)
      ++r;
    return r;
  }
  else
    assert(false);
}

Tu peux adapter à ton cas en simplifiant :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
unsigned short int log2(unsigned short int m)
{
  unsigned short int n = 256;
  while(n > 0 && n != m)
    n >>= 1;
  if(n > 0)
  {
    unsigned short int r = 0;
    while(n >>= 1)
      ++r;
    return r;
  }
  else
    assert(false);
}

Et alors t'as la solution dégueux, mais qui est sans doute la plus rapide dans ton cas spécifique :

 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
unsigned short int log2(unsigned short int m)
{
  if(m < 16)
  {
    if(m < 4)
    {
      if(m == 1)
        return 0;
      if(m == 2)
        return 1;
      assert(false);
    }
    else
    {
      if(m == 4)
        return 2;
      if(m == 8)
        return 3;
    }
  }
  else
  {
    if(m < 64)
    {
      if(m == 16)
        return 4;
      if(m == 32)
        return 5;
      assert(false);
    }
    else
    {
      if(m == 64)
        return 6;
      if(m == 128)
        return 7;
      if(m == 256)
        return 8;
      assert(false);
    }
  }
}

Édité par Caduchon

Zestons !

+1 -0

Tu as décrété que le calcul de ln est lent, mais qu'en sais-tu vraiment ? Sais-tu comment il est calculé ? Il est possible que le log soit fait avec une instruction spéciale du CPU, directement en hardware… Si c'est le cas, tu vas avoir du mal à battre ce genre de performances !

En plus, ta boucle ne va pas faire que des calculs de log, elle va faire beaucoup d'autres choses. Il est très peu probable que le log soit la fonction qui ralentit toute ta boucle.

La morale de l'histoire est : n'essaie jamais de deviner ce qui est lent ou pas. Même les meilleurs experts n'y arrivent pas. Fais des mesures. Chronomètre le temps d'exécution (sous BSD/Linux/Mac, la commande console time permet de faire ça), utilise un profiler, fais des tests, mais ne te fie pas à ton intuition.

Et quand bien même tu arriverais à mesurer que ton algo est trop lent à cause de trop nombreux calculs de logs, ça voudrait simplement dire que tu devrais revoir ton algo. Le calcul de log est un truc méga-optimisé, tu n'arriveras pas à gagner dessus.

Bon courage pour ton sudoku ! :)

GuilOooo


EDIT :

Et alors t'as la solution dégueux, mais qui est sans doute la plus rapide dans ton cas spécifique :

C'est même pas clair. Ta solution fait beaucoup de tests, et les tests c'est lent. La fonction log standard, même calculée naïvement, se contente de faire quelques multiplications et quelques additions. Même si ce sont des calculs flottants, il est possible (j'en sais rien, j'ai pas mesuré) que ce soit plus rapide.

Édité par GuilOooo

Canis Lupus pour vous servir

+4 -0

Effectivement, GuilOooo. Il n'y a que les tests qui peuvent vraiment déterminer quelle fonction est la plus rapide. Cependant, il devrait être possible de faire plus rapide en se ramenant à des short int, mais peut-être bien en asm seulement. :-p

Zestons !

+0 -0
Staff

Au pire une lookuptable doit pouvoir renvoyer un résultat tres rapidement si, comme dans le cas présent, le nombre de cas à tester à faible. Mais dans l'absolus je pense que c'est de l'optimisation prématuré. Je suis peu convaincu que c'est sur ce genre de calcul que tu va gagner du temps de calcul. Il faut déjà faire fonctionner le code et ensuite prendre un profiler pour trouver où sont les fonctions qui prennent du temps.

+0 -0

Bon, je me suis amusé à tester. La différence est tout de même éloquente ! Par contre j'ai eu un mal fou à empêcher l'optimiseur du compilo à vraiment exécuter le code…

Sur base du code de test ci-dessous, chaque fois compilé avec g++ -O3, j'obtiens (en moyenne sur 5 runs) ceci :

  • Solution 1 : 906 ms
  • Solution 2 : 141 ms
  • Solution 3 : 3964 ms
  • Solution 4 : 3375 ms
  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
#include <climits>
#include <cassert>
#include <cmath>
#include <iostream>

//*  Solution 1
unsigned short int init_ushort_max_power2()
{
    unsigned short int u = USHRT_MAX;
    u >>= 1;
    ++u;
    return u;
}

const unsigned short int ushort_max_power2 = init_ushort_max_power2();

inline
unsigned short int log_2(unsigned short int m)
{
    unsigned short int n = ushort_max_power2;
    while(n > 0 && n != m)
        n >>= 1;
    if(n > 0)
    {
        unsigned short int r = 0;
        while(n >>= 1)
            ++r;
        return r;
    }
    else
        return 100;
}
//*/

//* Solution 2
inline
unsigned short int log_2(unsigned short int m)
{
    if(m < 16)
    {
        if(m < 4)
        {
            if(m == 1)
                return 0;
            if(m == 2)
                return 1;
            return 100;
        }
        else
        {
            if(m == 4)
                return 2;
            if(m == 8)
                return 3;
            else
                return 100;
        }
    }
    else
    {
        if(m < 64)
        {
            if(m == 16)
                return 4;
            if(m == 32)
                return 5;
            return 100;
        }
        else
        {
            if(m == 64)
                return 6;
            if(m == 128)
                return 7;
            if(m == 256)
                return 8;
            return 100;
        }
    }
}
//*/

//* Solution 3
inline
unsigned short int log_2(unsigned short int m)
{
    return (unsigned short int)round(log((double)m)/0.693147180559945);
}
//*/

//* Solution 4
inline
unsigned short int log_2(unsigned short int m)
{
    return (unsigned short int)round(log2((double)m));
}
//*/

int main(int argc, char** argv)
{
    unsigned short int x = 32;
    for(unsigned long int i = 0; i < 10000000; ++i)
    {
        x += log_2(x);
        x += log_2(x);
        x += log_2(x);
        x += log_2(x);
        x += log_2(x);
        x += log_2(x);
        x += log_2(x);
        x += log_2(x);
        x += log_2(x);
    }
    std::cout << x << std::endl;

    return 0;
}

Édité par Caduchon

Zestons !

+0 -0

En fait j'en ai besoin pour trouver le poids du most significant bit.

Ricocotam

Donc en fait ce n’est pas vraiment $log_2$ qui t’intéresse. Tu as vu ce sujet sur SO ?

Sinon tu devrais suivre les conseils de David et GuilOooo, ce n’est pas en y allant à l’aveugle que tu va réussir à optimiser quoique ce soit.

La répétition est la base de l’enseignement. — ☮ ♡

+0 -0
Staff

Sinon tu devrais suivre les conseils de David et GuilOooo, ce n’est pas en y allant à l’aveugle que tu va réussir à optimiser quoique ce soit.

D'autant que resoudre un sudoku est typiquement le genre de problème où c'est surtout le choix de l'algo qui va impacter les perfs, plus qu'un pauvre calcul de log2 ou de most significant bit

Édité par Kje

+0 -0
Auteur du sujet

Merci pour toute ces réponses !

J'espère réussir à n'oublier personne..
Effectivement je n'ai pas encore fini de coder, mais j'ai vraiment réfléchi à comment chercher etc, et entre deux pauses sur l'algo principal (qui utilise des fonction du genre "c'est une puissance de deux ?" ou encore "quels sont les possibilités ?") je cherche un petit peu ces fonctions, pour ne pas perdre trop de temps et prendre un peu l'air ^^.

Je vais prendre le temps d'étudier chacune de vos solutions, mais je crois que j'avais mal identifier le problème. Puisque au départ j'ai le poids du bit, que je code après en binaire, il me suffirait de sauvegarder dans une table et j'ai rien à calculer du coup…

Merci à GuilOooo pour m'avoir appris à ne pas trop penser avant et aux autres aussi !

Je vous fait un poste d'ici deux trois jours pour vous dire où j'en suis ;)


PS : J'ai utilisé qu'une seule fois un profiler, c'était Sleepy. M'en conseillez vous un autre ? Parce que ce dernier était très simple et pratique pour du c++, hors je suis en Java cette fois.. Merci d'avance !

+0 -0

Plein d'algo sur une page de référence sur le sujet: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious.

Mais tu n'auras rien de plus rapide que ce que tu peux obtenir avec les séries des fonctions builtins comme __builtin_clz . NB: l'équivalent existe chez les autres compilos (même noms avec clang, mais d'autres noms chez VC++ p.ex.). Maintenant si tu es en Java … ça existe peut-être, mais je ne sais pas si ce langage a ça en builtin.

+0 -0

Caduchon : pour ta solution 3, ce n'est pas le log lui-même qui prend du temps, mais plutôt la conversion entier → flottant (et vice-versa) que tu te paies à chaque fois. On manque de contexte par rapport au problème original pour savoir s'il faut compter la conversion ou non…

Juste pour préciser : un log + une conversion entier → flottant prend un temps négligeable sur toute la boucle de l'algo. Aussi il vaut mieux privilégier la simplicité et la lisibilité sur l'optimisation à tout prix pour une si petite chose.

Canis Lupus pour vous servir

+0 -0
Auteur du sujet

Voilà, c'est fini ! Enfin presque, je ne résoud que les sudokus de niveaux 1 et 2, le reste devrait être fait dans la journée. Finalement j'ai opté pour une méthode avec une map come ceci :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
        puissance2_entier = new HashMap<Integer, Integer>();
        puissance2_entier.put(0, 0);

        for(int i = 0; i < grille.length; ++i)
            for(int j = 0; j < grille[i].length; ++j){
                if(grille[i][j] == 0)
                    casesVide.add(new Coord(i, j));

                    this.grille[i][j] = toPowerTwo(grille[i][j]);

                    if(!puissance2_entier.containsKey(this.grille[i][j]))
                        puissance2_entier.put(this.grille[i][j], grille[i][j]);
                }

J'essaie de trouver un profiler pour java sous unix, mais j'en trouve pas qui ne soient pas galère d'utilisation, des idée ?

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte