Et donc, c’est quoi un logarithme ?

Publié le par Balise

Je soupçonne que je vais avoir besoin, dans ma série d’articles d’informatique théorique, de logarithmes. Pourquoi ? Parce que c’est une des fonctions « utiles » lorsque l’on parle de complexité algorithmique. Donc, pour être sûr que tout le monde soit sur la même page, je fais un cours de rattrapage sur les logarithmes. Les gens qui ont de mauvais souvenirs de leurs maths de lycée ont probablement aussi de mauvais souvenirs des logarithmes, et pourtant, les logarithmes, c’est chouette.

En parlant de logarithmes, je ne sais pas comment ils ont été introduits dans vos cours de maths respectifs ; pour ma part, je suis à peu près sûre qu’on me l’a défini à partir de l’intégrale de la fonction inverse. RESTE ICI, C’EST PAS CE QUE JE VAIS FAIRE. Enfin pas tout de suite. Je vais commencer par essayer de donner une intuition du bidule.

arbre

Considérons la figure que je viens d’insérer avec brio dans mon billet. Je suis partie d’un point, à partir de ce point j’ai fait deux branches, au bout desquelles j’ai ajouté un point ; sur chacun de ces points, j’ai ajouté deux branches, au bout desquelles j’ai ajouté un point, et ainsi de suite. J’aurais pu continuer comme ça longtemps, conceptuellement – je vais avoir des problèmes de place et des problèmes de fatigue (ça va être pénible très vite d’ajouter des ptits points), mais conceptuellement, je pense qu’on peut tous imaginer un arbre comme celui-ci avec autant de niveaux qu’on le souhaite.  Supposons aussi, parce qu’on fait de l’informatique, que la « racine » de l’arbre (le tout premier point que j’ai ajouté sur ma figure) soit au niveau 0. Si je « retourne » l’arbre, ça peut avoir une certaine logique, c’est le « rez-de-chaussée », et le niveau suivant est le « premier étage ». Supposons maintenant que je veuille compter le nombre de « feuilles » de mon arbre, c’est-à-dire le nombre de points que j’ai sur le dernier niveau de mon arbre.

Il est assez clair que le nombre de feuilles dépend du niveau auquel j’arrête mon arbre, et qu’il augmente à chaque niveau. Si je m’arrête au niveau 0, j’ai 1 feuille. Si je m’arrête au niveau 1, je multiplie ça par deux (parce que je fais deux branches), ça fait 2. Si je m’arrête au niveau 2, je multiplie le nombre de feuilles du niveau 1 par deux encore, ça fait 4. Et à chaque niveau, je prends le nombre de feuilles du niveau précédent et je le multiplie encore par deux. Au niveau 3, j’aurai donc 2*2*2 = 8 feuilles et, au niveau 4, 2*2*2*2 = 16 feuilles. Pour connaître le nombre de feuilles au niveau numéro n, où n est le numéro de mon niveau, je fais n multiplications de 2 par lui-même, ce qui s’écrit 2^n (et se lit « deux à la puissance n »).

Supposons à présent que je ne veuille pas connaître le nombre de feuilles correspondant à un niveau, mais le nombre de niveaux correspondant à un nombre de feuilles donné. Par exemple, j’ai 2 feuilles : ça correspond au niveau 1. 16 feuilles : ça correspond au niveau 4. Si j’en ai 32, ça correspond au niveau 5. Et si j’ai 128 feuilles, ça correspond au niveau 7. Bon, évidemment, ça se complique un peu si j’ai, mettons, 20 feuilles. 20 feuilles, ça correspond à un niveau « 4 et des poussières » – j’ai dessiné jusqu’au niveau 4, j’ai commencé à dessiner le niveau 5, et j’ai eu la flemme de finir. Cette opération, qui est l’opération réciproque de l’opération précédente, c’est un logarithme. Je dis que c’est l’opération réciproque, parce qu’elle me permet de « défaire » l’opération précédente. Je prends un nombre n, j’en prends la puissance de 2, ça me donne 2^n, et si je reprends le logarithme de ça, j’ai

\log(2^n)= n

De la même manière, si j’ai un nombre n, que j’en prends le logarithme, et que j’en reprends la puissance de 2, j’ai

2^{\log n} = n

Bon, c’est bien gentil, tout ça, mais qu’est-ce qu’il se passe, si au lieu de faire deux branches à chaque étape, j’en fais 3 ? Selon le même raisonnement que précédemment, au niveau n, j’ai 3*3*…*3 feuilles, c’est à dire 3^n. Et, bon, ben de la même manière, je peux définir un logarithme qui soit la réciproque de ce 3^n. Mais, bon, je veux pouvoir les distinguer – donc je mets la puissance à laquelle ils correspondent en indice, comme ceci :

\log_2, \log_3

avec

3^{log_3 n} = n

et

\log_3(3^n) = n

L’indice de mon logarithme, on appelle ça la « base » du logarithme. J’en profite pour faire une petite remarque sur le logarithme en base 10 (c’est aussi valable pour les autres bases, au moins entières, de logarithmes, mais je ne rentre pas là-dedans). Il est très facile d’avoir une évaluation « à la louche » du logarithme en base 10 d’un nombre. C’est le nombre de chiffres du nombre en question, moins 1. On a \log_{10}(10) = 1, \log_{10}(100) = 2 (parce que 10^2 = 100); tous les nombres entre 10 et 100 ont un logarithme en base 10 entre 1 et 2. De la même manière, on peut estimer que le logarithme en base 10 de 14578 est entre 4 et 5. Pour voir ça, il suffit de voir que 14578 est compris entre 10000 = 10^4 et 100000 = 10^5, ce qui permet de conclure sur la valeur du logarithme. (Je passe un certain nombre de choses sous le tapis ici, en particulier les raisons qui font qu’on peut effectivement conclure ça.)

Bon, cela dit, maintenant que j’ai défini des bases de logarithme, qu’est-ce qui m’empêche d’utiliser des bases « exotiques » pour mes logarithmes ? La réponse est « rien ». Je peux définir un logarithme en base 3.5 (qui correspond à la puissance à laquelle j’élève 3.5 pour obtenir le nombre dont je prends le logarithme en base 3.5), \frac 5 3 (qui correspond à la puissance à laquelle j’élève \frac 5 3 pour obtenir le nombre dont je prends le logarithme en base \frac 5 3), ou même \pi (qui correspond à… bon, ça ira, peut-être) si ça me chante. C’est moins « intuitif » si je considère mon explication avec les arbres et le nombre de niveaux (parce que c’est difficile de faire \pi branches), mais en considérant la réciproque des fonctions puissance, ça me paraît raisonnablement clair.

La question suivante qu’on peut se poser, c’est si tous ces logarithmes en différentes bases ont un lien entre elles, ou plus exactement si on peut les exprimer d’une façon commune. La réponse est « oui ». C’est ici que j’introduis le logarithme népérien, aussi appelé logarithme naturel, dénoté \ln. Le logarithme népérien est un logarithme en base e \approx 2.71828. On peut exprimer n’importe quel logarithme dans n’importe quelle base a comme ceci :

\log_a(x) = \frac{\ln x}{\ln a}

Ce qui veut aussi dire qu’on peut passer d’un logarithme d’une base a à un logarithme d’une base b comme ça :

\log_a(x) = \frac{\ln x}{\ln a} = \frac{\ln x}{\ln b} \times \frac{\ln b}{\ln a} = \frac{\ln b}{\ln a}\log_b(x)

(Et oui, c’est typiquement le genre de chose que j’ai dans mon formulaire d’examen, parce que je me souviens jamais dans quel sens c’est !)

L’important à retenir, ici, c’est que tous les logarithmes sont égaux « à une constante près » ; ils ont le même « comportement asymptotique » (j’introduis les termes ici, mais je ferai un billet spécifique sur le sujet, parce que c’est un peu long à expliquer). C’est intéressant dans le domaine qui nous préoccupe ici, parce qu’on s’intéresse surtout à l’estimation des comportements « à une constante près » quand on parle de temps d’exécution ou d’occupation mémoire d’un algorithme. Encore une fois, j’y reviendrai – prenez ça comme un « spoiler » des prochains épisodes 🙂

J’en arrive à la relation entre le logarithme népérien et la fonction inverse. Formellement, on écrit que

\ln(x) = \int_1^x \frac 1 t \text{d}t

Et voilà ce que ça veut dire, graphiquement :

log

La courbe rouge est la courbe de la fonction x \mapsto 1/x. La zone grise correspond ici à l’intégrale de 1 à 6 ; l’aire de cette zone est égale à ln(6). Et on peut représenter le logarithme népérien de n’importe quelle valeur (supérieure à 1) par l’aire de la surface située entre l’axe des x et la courbe x \mapsto 1/x, prise entre 1 et cette valeur. Remarquons au passage que cette aire est égale à 1 lorsqu’on la considère entre 1 et e, e étant la base du logarithme népérien (parce que ln(e) = 1).

Et pour finir, une propriété intéressante de la fonction logarithme : on peut écrire (dans n’importe quelle base du logarithme)

\log(a \times b) = \log(a) +\log (b)

\log(a/b) = \log(a) - \log(b)

En tant que réciproque de la fonction puissance, c’est assez clair de voir ça. Étant entendu que si deux puissances d’un même nombre sont égales, alors l’exposant l’est aussi, on a d’une part :

2^{\log_2(a \times b) } = a \times b

et d’autre part

2^{\log_2 a + \log_2 b} = 2^{\log_2 a}\times 2^{\log_2 b} = a \times b

On peut dériver la deuxième égalité de la même manière – hop, exercice 😛

Notons au passage que c’est à cause de ce genre de propriété que les logarithmes ont été utilisés au départ. Si on a une grosse table avec plein de correspondances « nombre/logarithme », et qu’on veut multiplier deux nombres facilement, on regarde dans la table les logarithmes des deux nombres, on les ajoute (ce qui est vachement plus facile que de les multiplier), et on regarde la valeur correspondante du logarithme (on utilise la table dans l’autre sens) pour avoir la valeur des deux nombres initiaux multipliés. Historiquement, ce genre de tables est apparu au XVIIe siècle (on remerciera M. Napier) pour faciliter les calculs astronomiques ; la règle à calcul fonctionne également sur ce principe ; et tout ça n’a été détrôné que par l’arrivée, plutôt récente, des machines à calculer et des calculatrices…

Bref, les logarithmes, c’est cool. Et j’espère que vous en êtes à présent aussi persuadés que moi 🙂

14 commentaires sur « Et donc, c’est quoi un logarithme ? »

  1. Bonnes explications !

    Note qu’introduire le logarithme népérien n’est pas nécessaire pour les changements de base de logarithmes. On peut juste écrire :

    log_a(x) = log_b(x) / log_b(a)

    Réponse

    1. Toutafé. J’avouerai que j’ai presque pensé le truc dans l’autre sens, sur le « bon et maintenant comment j’introduis le népérien ? » 😛 Et passer par là me paraissait le plus « logique » dans le flux de raisonnement.

      Réponse

  2. Les logarithmes, c’est clair (alors que c’était resté confus à l’école) (et pourtant, j’étais bonne en fonctions) (et même que j’aimais ça).

    Par contre, ce qui n’est pas clair, c’est comment tu as su que j’allais partir quand j’ai lu « l’intégrale de la fonction inverse » ?

    Réponse

  3. Sans surprise, je n’ai rien appris par cet article 😉

    Par contre, je me suis plusieurs fois demandé dans quelle mesure il serait didactiquement intéressant de présenter le logarithme (et en même l’exponentielle) comme un isomorphisme de (R+*, ×) dans (R, +), mais pas dit comme ça, évidemment. Genre en partant de la règle à calcul ou des tables.

    Il me semble que s’il ne fallait en retenir qu’une propriété, ce serait justement celle là (dans un contexte général, car le contexte particulier de l’info’ théorique exige peut-être plus d’importance entre les éléments de R+* et de R qui sont ainsi reliés).

    Dans un tout autre registre, je m’interrogeais aussi sur présenter le fait que le logarithme népérien pour attendre…

    Réponse

    1. C’est possible que dans un contexte général ça aide. Je sais pas. Dans le contexte qui m’intéresse là tout de suite, j’ai besoin de logs, en gros, pour expliquer après le runtime d’un binary search ou d’un sort, et donc le susdit isomorphisme est presque anecdotique. Enfin disons que c’est pas ça qui fait piger pourquoi ya un log qui vient s’inviter dans l’affaire.

      J’allais dire que ta dernière phrase ne parsait pas. Et entre temps j’ai compris. Tu népérien pour attendre non plus.

      Réponse

  4. « en considérant la réciproque des fonctions puissance, ça me paraît raisonnablement clair. »

    Et là tu paumes tous ceux qui n’ont pas le réflexe (logique ? scientifique ?) de se dire que si on a une fonction on peut faire la même chose en sens inverse. C’est pas forcément évident. P’t’être pour ça que présenter les logs comme l’intégrale de la fonction inverse c’est plus intuitif pour les matheux évolués et pas les débutants 🙂 (En même temps, vu comment marche l’Education Nationale, il a suffi d’un inspecteur qui niait l’existence du monde réel pour infliger ça à des générations de lycéens).

    Réponse

    1. Certes. C’est d’autant moins évident qu’il faut quand même quelques conditions pour que ce soit le cas. J’essaye, hein, c’est dur d’expliquer un truc sans avoir le regard vide de l’audience « alors là, lapin compris » pour guider sur les passages délicats 🙂

      Réponse

      1. Tiens ça fait longtemps que je n’ai plus eu droit à ce regard.

        Ces derniers temps je tombe toujours sur des gens qui n’essayent même pas et démissionne tout de suite. Je trouve ça super triste.

  5. En plus de transformer une multiplication en addition comme tu le dis à la fin, les logs servent en science surtout à écraser les ordres de grandeur.

    Typiquement en chimie tu vois l’évolution de la concentration d’un produit en fonction de la concentration d’un autre : les chiffres vont par exemple de 10^-10 à 0,1, ça fait un facteur un milliard, neuf ordres de grandeur. Impossible de faire un graphique où on peut distinguer le 10^-10 et le 10^-9. Donc en abscisse on met le log de la concentration. Et en ordonnée en général aussi. Comme les lois sont en général en puissance dans ce milieu, ça faisait de belles droites (et facilitait sacrément les calculs à une époque sans ordinateur).

    Réponse

      1. Ben quand tu as dû te taper tous les calculs de logs à la caltos parce que t’es d’une génération qui n’avait pas forcément un ordi avec Excel chez lui ou au niveau Bac+3, ça te marque à vie.

        Mon oncle il devait les faire à la table de log ou de tête, ses calculs. (Je parle de mon oncle parce que mon père est un littéraire.)

        Ca me fascine d’autant plus de voir que la Tour Eiffel ou des ponts suspendus ne se sont pas écroulés : tant de calculs et pas d’erreur.

  6. Bonjour,
    Un grand merci pour votre approche des logarithmes. Devant rendre un dossier « scientifique » dans le cadre d’une sélection pour intégrer une formation continue d’ingénieur généraliste j’ai choisi de parler des mathématiques dans la construction musicale. Il se trouve que les logarithmes y ont la part belle ! La personne qui nous suit avant l’exposé final m’a demandé de simplifier les choses, d’expliquer les logarithmes comme si j’avais des enfants devant moi… J’ai de suite pensé à votre démonstration qui est très parlante. Je vous remercie donc pour l’éclairage que vous donnez à cette fonction !

    Réponse
  7. Ping: So… What’s a logarithm? – Balise's Blog

Votre commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Gravatar
Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. ( Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. ( Déconnexion /  Changer )

Annuler

Connexion à %s

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.