Calculer Log2(n)

Bonjour tout le monde ! Dans le cadre de la résolution de sudoku, j'aurais besoin de calculer Log₂(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 Log₁₀. 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 Log₂(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 Log₂(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 !

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 !

La vrai question étant as tu besoin des performances pour être obligé de recoder log_2 ?

Tu as des benchs+profiling pour étayer tes besoins ?

Le but est de résoudre des sudokus et plus ça va vite, meilleur est ma note 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 2⁰ à 2⁸

• Traitements diverses pour résoudre le sudoku

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

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);
    }
  }
}

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.

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.

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.

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;
}

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.

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 log₂ ou de most significant bit

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 !

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.

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.

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 ?