David Madore's WebLog: 2021-06

J'ai déjà publié un certain nombre d'éléments autobiographiques par ici : outre cette autobiographie couvrant les années 1976–1996, j'avais écrit ce billet de blog sur mon rapport à mon orientation sexuelle, celui-ci sur ma découverte des ordinateurs, et d'autres choses çà et là, comme (ce qui a un rapport avec ce que je veux évoquer ci-dessous) ici sur ma lecture de Tolkien ou bien là sur celle d'Asimov. Je voudrais dire ici quelques mots sur les histoires que j'ai moi-même écrites quand j'étais ado, sur ce qu'elles racontent et sur ce qu'elles disent sur moi (même si je les ai déjà évoquées en passant comme ici ou là, et plus récemment là). Au minimum, je voudrais raconter un peu quelle est leur intrigue et comment elle m'est venue, et, pour que vous n'ayez pas à les lire vous-mêmes — comment j'ai pu produire des choses aussi mauvaises ou, en tout cas, bizarres. Et ce que j'ai appris à travers elles.

Mon papa m'avait un jour fait la remarque, que je trouve très juste, que quand on enseigne la littérature à l'école, on sélectionne ce qu'il y a de mieux, les meilleures œuvres des plus grands auteurs, et sans doute montrer aux enfants pourquoi c'est si bien écrit, mais peut-être que la médiocrité a en fait autant à nous apprendre que le génie (ne dit-on pas, après tout, qu'il faut apprendre par les erreurs des autres, parce qu'on ne peut pas vivre assez longtemps pour les commettre toutes soi-même ?), ou encore la comparaison entre les deux (peut-on vraiment se rendre compte que Shakespeare est un dramaturge de génie sans le comparer à un autre qui n'en est pas un ? ou d'ailleurs simplement à des moments où il ne l'est pas vraiment — quandoque bonus dormitat Homerus — mais c'est assez tabou de montrer un passage de Shakespeare pour dire là ce n'est franchement pas terrible, alors qu'on osera plus facilement avec un auteur qui a moins marqué toute la civilisation). Et un texte médiocre reflétera en outre peut-être mieux le contexte historique et social dans lequel il a été écrit que celui d'un auteur que sa stature même rend singulier, et qui nécessite sans doute pour être décodé correctement de traverser plusieurs couches d'interprétation et de réinterprétation plaquées par les époques intermédiaires.

Je ne sais pas si mes œuvres forment même un bon exemple de médiocrité, ou même si je peux me mettre en avant comme exemple typique (whatever this means) d'ado qui, nourri d'une pop-culture « tolkienisante » en France dans les années '80–'90, s'est mis à produire son propre sous-Tolkien ou sous-Asimov, mais je peux toujours essayer. Il n'y a pas que le cadre (fantastique ou science-fiction) qui mérite un mot, parce que mes romans disent aussi autre chose sur moi, comme mon obsession pour le mysticisme et la symétrie, et derrière le sous-Tolkien il y a du sous-Oulipo, ou quelque chose comme ça.

Pour redonner un peu de contexte, même si j'ai déjà raconté ça plusieurs fois, j'ai grandi « un pied dedans, un pied dehors » par rapport à une pop-culture que je qualifie ci-dessus de tolkienisante : je n'ai lu The Lord of the Rings qu'à 15 ans (encore une fois, cf. ici ; j'avais lu The Hobbit bien avant), mais j'avais des amis qui l'avaient lu bien avant, et qui m'en avaient parlé, et je m'étais formé une certaine idée de l'œuvre, et surtout, j'avais été exposé à un certain nombre de — comment dire — produits dérivés du Seigneur des Anneaux. Je n'ai pas joué à Dungeons & Dragons (ou peut-être juste une ou deux fois, pour des parties très courtes), mais j'ai côtoyé des gens qui y jouaient beaucoup (ou à d'autres jeux de ce genre), et j'ai assisté à de telles parties, ça m'intéressait plus de m'asseoir à côté du DM et de tout observer que de participer personnellement à l'action ; de même s'agissant des Livres dont Vous Êtes le Héros, je n'y jouais guère (je n'avais pas la patience de prendre les dés pour les combats, suivre les règles, et subir la frustration d'être tué et de recommencer), mais j'aimais quand même les lire, quasi linéairement, en explorant des choix un peu au pif, d'où il résultait d'ailleurs une idée assez confuse de la trame générale de l'intrigue que je découvrais finalement dans un désordre à peu près total ; parfois (surtout en fin d'école primaire, donc vers 10 ans), des amis et moi nous construisions mutuellement des aventures, dans un cadre informel, sans dés ni plateau ni règles précises, nous proposant juste oralement situations et nous invitant à dire ce que nous voulions faire, et ces aventures étaient pleines de magie. Et une autre chose qui m'a beaucoup marqué, ce sont certains jeux d'aventure sur ordinateur : je ne redis pas ce que j'ai déjà écrit ici (ainsi que là et là), mais j'ai beaucoup été influencé par la série King's Quest et surtout Ultima.

Je viens de lister quelques uns des ingrédients des mondes de mon imagination, mais il y a autre chose que je devrais surtout essayer de dire c'est : pourquoi la heroic fantasy ? Ce n'est pas uniquement une influence extérieure qui m'a poussé vers ce genre. Il y a bien sûr l'aspect d'avoir besoin de rêver un peu de magie dans un monde qui n'en a pas (et peut-être d'autant plus fortement que, fasciné par les sciences, je devais reléguer le surnaturel à mes rêves et fictions). Mais il y a un autre aspect auquel on pense peut-être moins évidemment que « l'envie de rêver » :

• Écrire une histoire se déroulant dans le monde réel demande soit une expérience de celui-ci, soit un effort de documentation, qui sont difficilement accessibles quand on est ado, surtout à une époque où Wikipédia n'existait pas et même le Web quasiment pas. (Ou alors on va se limiter à des récits qui se déroulent dans un collège/lycée français, ce qui présente certes des possibilités assez considérables d'exploration psychologique, mais limite sérieusement l'intrigue elle-même. En tout cas, je n'ai jamais eu envie de reproduire dans ce que j'écrivais ce que je vivais déjà chaque jour. Mais en même temps j'étais trop maniaque de la précision pour accepter de simplement ignorer mon ignorance, inventer ce que je ne savais pas, et admettre que je ferais forcément plein d'erreurs.)
• A contrario, le cadre « médiéval-fanastique tolkienisant standard » offre à la fois suffisamment de références partagées pour pouvoir commencer à écrire une histoire sans perdre une éternité en exposition si on ne le souhaite pas (si je dis elfe, mon lecteur s'imagine quelque chose de vaguement conforme au standard ISO de l'elfe), mais suffisamment de flexibilité pour permettre d'y insérer à peu près n'importe quoi comme intrigue. C'est un cadre générique, peu envahissant, mais hautement paramétrable (à commencer par le réglage critique « niveau et type de magie disponible »), dont on peut faire absolument ce qu'on veut, et où on n'a à se soucier que de cohérence interne sans que qui que ce soit vienne vous reprocher, par exemple, que la rue Servandoni n'existait pas à l'époque où se situe votre roman.

Alors oui, on peut considérer que le cadre médiéval-fantastique tolkienisant standard est un peu cheap, qu'il s'agit du plastique à tout faire d'un million de mondes interchangeables. (J'ai moi-même souvent ressenti l'agacement extrêmement bien décrit ici par Boulet et qui pourrait directement attaquer beaucoup des histoires que j'ai écrites.) Mais on doit savoir gré à Tolkien d'avoir créé ce cadre standard qui ouvre les portes du royaume de l'imagination à mille adolescents qui ne deviendront jamais écrivains mais qui ont besoin de rêver, et peut-être à un qui deviendra écrivain, quitte à rester dans ce cadre mais en en faisant quelque chose de créatif car il est bien sûr possible de dépasser le cliché. (Pour être bien clair, je ne prétends absolument pas que je fantastique soit un genre réservé aux adolescents ou jeunes adultes : je dis juste qu'il est plus facile de se mettre à écrire dans ce cadre quand on est adolescent ou jeune adulte.)

C'est intéressant, parce qu'il semble qu'il (Tolkien) ait voulu créer une mythologie de l'Angleterre, mais ce qu'il a créé est à la fois plus large (dépassant largement l'Angleterre) mais aussi différent. La distinction entre un cadre imaginaire et une mythologie cohérente est assez subtile : il est plus facile d'écrire une histoire dans un monde basé le cadre médiéval-fantastique tolkienisant que sur les mythes grecs, par exemple, ou bien sur le cycle Arthur-Lancelot-Merlin-Graal, parce que ces derniers renvoient à des histoires assez précises avec lesquelles le lecteur s'attendrait à trouver une articulation (qu'il s'agisse de Thésée ou de Perceval, on leur associe plus que des caractéristiques générales, mais des événements bien définis), alors qu'il est beaucoup plus facile d'importer quelques idées des mondes à la Tolkien sans importer toutes les histoires de la Terre du Milieu. Allez savoir pourquoi : peut-être est-ce grâce à Dungeons & Dragons que se sont répandues non seulement l'idée de ce cadre générique mais aussi l'idée encore plus importante que chacun est libre de s'en emparer et d'en faire ce qu'il veut.

L'autre type de cadre dont on peut facilement imaginer s'emparer, c'est la science-fiction (et on peut peut-être croire que, pour moi qui avais une certaine culture scientifique déjà à quinze ans, ç'eût été plus naturel). J'ai certainement été beaucoup influencé par la trilogie originale des films Star Wars (j'ai vu l'épisode VI à sa sortie) et par la lecture du cycle Foundation d'Asimov (je ne vais pas redire ce que j'ai déjà écrit ici), et sans doute aussi, à un certain niveau, par le livre de vulgarisation scientifique Cosmos de Carl Sagan : quelle que soit la part de ces différences influences, je rêvais de civilisations galactiques, mais en même temps je voyais bien qu'il était très difficile d'écrire des histoires scientifiquement sensées dans un tel cadre. Car quels que soient les mécanismes imaginés pour contourner les obstacles évidents que présentent la finitude de la vitesse de la lumière, l'immensité des échelles d'espace et de temps impliquées, la rareté des planètes habitables et l'imagination des formes de vie extra-terrestres (ou l'explication de leur absence !), pour arriver à quelque chose de ne serait-ce que plausible scientifiquement, non seulement on devra faire d'immenses efforts d'exposition, mais en outre on arrivera certainement à un univers tellement étranger à l'expérience familière de l'auteur et du lecteur qu'il sera difficile de rentrer dedans. L'autre solution était de jeter résolument la science à la poubelle et de traiter le space opera comme on traite le médiéval-fantastique, comme un décor en plastique où on peut insérer n'importe quelle manière d'histoire, mais j'étais plus hostile à suspendre mon incrédulité scientifique de cette manière qu'en imaginant des elfes, des nains et des gnomes.

[Lire la suite…]

Mon poussinet s'est acheté une nouvelle voiture. Ou plus exactement, a remplacé un joujou, rouge de chez Honda, thermique et bruyant, par un autre joujou, blanc de chez Tesla, électrique et beaucoup moins bruyant et beaucoup plus Internet of Shit ; mais ce n'est pas mon propos ici d'en parler : le point de départ de ce que je veux dire ici, c'est que le nouveau joujou est assez long et large, et que la descente du parking de notre immeuble est compliquée.

Nous avons trois véhicules et trois places de parking (une achetée avec l'appartement et deux louées à des voisins). Ma moto, bizarrement, ne pose aucun problème pour monter et descendre au parking. Pour la Tuture préférée (qui fait censément 1.74m de large, et 4.15m de long dont 2.51m entre les essieux), le poussinet s'en sort bien (le plus souvent sans marche arrière), mais moi je n'ose pas trop essayer, et c'est d'ailleurs mon principal obstacle à circuler en voiture. Et pour le nouveau joujou (qui fait censément 1.85m de large, et 4.69m de long dont 2.83m entre les essieux), c'est beaucoup plus compliqué : à ce stade, à chaque fois que nous voulons entrer ou sortir du parking, je descends de la voiture, je passe devant, et j'indique au poussinet par des signes de main la distance à gauche et à droite (certes, le joujou a plein de capteurs, mais ils sont essentiellement inutiles dans ces circonstances, parce qu'ils passent juste leur temps à faire bip, et ne détectent pas forcément la « bonne » distance) : il arrive à sortir en une seule fois, mais pour rentrer dans le parking il faut trois ou quatre marches arrière (et la question de pourquoi ce n'est pas symétrique est une de celles que je veux discuter ici).

Pourtant, la descente du parking n'est pas si étroite : elle fait 2.67m de large au point le plus resserré que j'aie mesuré ; cette largeur est un peu stupidement grignotée par le fait qu'il y a des garde-corps (je ne sais pas comment les appeler : une sorte de marche ou de micro trottoirs de part et d'autre de la descente, au niveau du sol, large d'environ 15cm et haute d'environ autant), qui réduit l'espace disponible au niveau des roues à 2.38m au point le plus étroit. Mais bien sûr, la descente est courbe : entre la porte côté rue et la base de la rampe, il y a un changement de cap de 90° (on entre perpendiculairement à la rue Simonet, et on finit parallèlement à elle).

Géométriquement, si j'en crois les plans d'architecte de l'immeuble que j'ai récupérés je ne sais plus comment, la forme est très simple (cf. figure ci-contre) : prenez un quart de cercle de rayon 6.50m et un autre de rayon 5.50m dont les centres sont décalés de 1.75m selon chacun des axes du quart de cercle (donc à distance 1.75m×√2 ≈ 2.47m l'un de l'autre), le centre du petit cercle étant évidemment plus éloigné des arcs eux-mêmes que celui du grand cercle, et ensuite prolongez tangentiellement chacune des deux extrémités de chacun des deux arcs. (En notation SVG et en exprimant les distances en mètres : M 0.00 0.00 L 9.37 0.00 A 6.50 6.50 0 0 1 15.87 6.50 L 15.87 18.38 pour le bord extérieur et M 0.00 2.75 L 7.62 2.75 A 5.50 5.50 0 0 1 13.12 8.25 L 13.12 18.38 pour le bord intérieur.) Ceci fait donc une rampe dont la largeur est de (6.50m−5.50m)+1.75m = 2.75m dans ses parties rectilignes, et de (6.50m−5.50m)+1.75m×√2 ≈ 3.47m dans sa partie courbe, à quoi il faut retirer environ 15cm de garde-corps de part et d'autre comme je l'ai expliqué ci-dessus. J'ai fait apparaître sur la figure des rectangles à l'échelle du joujou du poussinet, mais il n'est pas évident de le placer comme je viens de le montrer (cf. plus loin). L'épaisseur des traits sur la figure est de 30cm (le milieu du trait est au niveau du mur lui-même, le bord intérieur correspond à peu près au bord du garde-corps).

Bon, en plus, la rampe est bien sûr en pente (de 14.38% selon le plan d'architecte, l'hélice étant orientée à main gauche : sur le schéma ci-contre, la sortie côté rue est en bas de la figure, la base de la rampe côté parking est à gauche), mais je ne pense pas que ça joue énormément sur le problème géométrique que je vais évoquer. Par ailleurs, la construction de l'immeuble n'a pas respecté précisément les plans d'architecte et les arcs de cercle ont été approchés par des polygones, donc il y a trois ou quatre points anguleux sur le mur extérieur : je ne sais pas bien si ça joue dans l'explication de l'asymétrie ressentie entre montée et descente, je vais y revenir ; la largeur de la rampe, comme je l'ai dit plus haut, n'est, d'après mes mesures, pas tout à fait égale aux 2.75m contractuels de mur à mur, je l'ai déjà noté.

Mes lecteurs savent que j'aime faire des typologies, alors allons-y. Je peux distinguer trois niveaux au problème d'entrer ou sortir la voiture :

1. La question purement géométrique (entrer ou sortir la voiture, en supposant une connaissance parfaite de ses dimensions, sa position, la forme de la rampe, etc., donc toutes les distances impliquées), que je vais elle-même ci-dessous subdiviser en trois.
2. La complication supplémentaire que, assis à la place du conducteur, on voit mal ce qu'on fait, on évalue mal les distances, malgré les rétroviseurs et les diverses caméras de la Tesla, en tout cas, plus mal que quelqu'un qui se tient à distance et qui regarde la voiture de l'extérieur.
3. La complication supplémentaire qu'une voiture n'avance pas exactement comme on veut (je parle du point de vue de la traction : je mets la question du rayon de braquage sur le chapeau géométrique) : ceci ne concerne pas la Tesla, dont le moteur électrique permet d'avancer aussi lentement qu'on veut, presque millimètre par millimètre, aussi bien en montée qu'en descente, mais le problème se pose avec une voiture thermique si on ne veut pas vitrifier l'embrayage en patinant trop longtemps.

Je veux surtout parler ici du (A), même si (B) et (C) sont aussi problématiques en pratique. Maintenant, même si je le simplifie à outrance en traitant la voiture comme un simple rectangle et en ramenant tout le problème dans le plan, ce que je vais faire, le (A) se subdivise lui-même en trois niveaux de difficulté :

[Lire la suite…]

Je rassemble dans cette entrée quelques faits algorithmiques et informatiques qui sont généralement « bien connus » (et franchement assez basiques) mais souvent utiles, et qu'il est possiblement difficile de trouver rassemblés en un seul endroit. Le problème général est de tirer algorithmiquement des variables aléatoires selon différentes distributions, typiquement à partir d'un générateur aléatoire qui produit soit des bits aléatoires (indépendants et non biaisés) soit des variables aléatoires réelles (indépendantes) uniformément réparties sur [0;1]. Je parle d'algorithmique, mais ce n'est pas uniquement sur un ordinateur : ça peut être utile même dans la vie réelle, par exemple si on a une pièce avec laquelle on peut tirer à pile ou face et qu'on veut s'en servir pour jouer à un jeu qui réclame des dés à 6 faces, ou si on a des dés à 6 faces et qu'on veut jouer à un jeu d'aventure qui réclame des dés à 20 faces.

Comment tirer des nombres aléatoires en conditions adversariales ? Je commence par ce problème-ci qui n'a pas de rapport direct avec la suite, mais que je trouve quand même opportun de regrouper avec : Alice et Bob veulent jouer à pile ou face, ou plus généralement tirer un dé à n faces, mais ils n'ont pas de pièce ou de dé en lequel ils fassent tous les deux confiance. Par exemple, Alice a sa pièce fétiche que Bob soupçonne d'être truquée et symétriquement (ou peut-être même que chacun est persuadé de pouvoir tirer des nombres aléatoires dans sa tête mais ne fait évidemment pas confiance à l'autre). La solution est la suivante : chacun fait un tirage avec son propre moyen de son côté, sans connaître le résultat de l'autre, et on combine ensuite les résultats selon n'importe quelle opération (choisie à l'avance !) qui donne tous les n résultats possibles pour chaque valeur fixée d'une quelconque des entrées (un carré latin, par exemple une loi de groupe) ; par exemple, s'il s'agit de tirer à pile ou face, on peut décider (à l'avance !) que le résultat sera pile (0) si les deux pièces ont donné le même résultat et face (1) si elles ont donné un résultat différent ; s'il s'agit de dés à n faces donnant un résultat entre 0 et n−1, on fait la somme modulo n (c'est-à-dire qu'on fait la somme et qu'on soustrait n si elle vaut au moins n, pour se ramener à un résultat entre 0 et n−1). Bien sûr, il faut un protocole pratique pour faire en sorte que chacun fasse son tirage sans connaître le résultat de l'autre (sinon, s'il a moyen de tricher, il pourra adapter le résultat en conséquence) : physiquement, chacun peut faire son tirage en secret et écrire le résultat secrètement sur un papier placé dans une enveloppe scellée, qu'on ouvrira une fois les deux tirages effectués (en fait, il n'y a que le premier tirage qui a besoin d'être fait de la sorte) ; cryptographiquement, on procède à une mise en gage (typiquement au moyen d'une fonction de hachage, mais je ne veux pas entrer dans ces questions-là). On peut bien sûr généraliser à plus que deux joueurs (en faisant la somme modulo n de nombres tirés par chacun des participants). Le protocole garantit que le résultat sera un tirage uniforme honnête si l'un au moins des participants désire qu'il le soit (et a les moyens de réaliser un tirage honnête) : bien sûr, si aucun des participants ne le souhaite, c'est leur problème, donc on s'en fout. Même si on abandonne toute prétention à ce que les participants tirent leur valeur aléatoirement et qu'on s'imagine qu'ils la choisissent, tant qu'il s'agit d'un jeu à somme nulle, la stratégie optimale est bien de tirer au hasard (et encore une fois, s'ils veulent coopérer pour un autre résultat, tant qu'il n'y a pas d'autre partie impliquée, c'est leur problème, de même s'ils s'imaginent pouvoir faire mieux que le hasard en utilisant, par exemple, une prédiction psychologique).

Je ne sais plus où j'avais lu que ce protocole a été découvert (il l'a certainement été de nombreuses fois !) à la renaissance. Dans mon souvenir, le découvreur proposait même que, pour une question de la plus haute importance, on demande au pape de faire un des tirages en plus de tous les autres participants. Je ne sais d'ailleurs pas si ce protocole a un nom standard.

Comment tirer une variable de Bernoulli de paramètre p à partir de bits aléatoires ? Autrement dit, ici, on a fixé p, et on veut faire un tirage aléatoire qui renvoie oui avec probabilité p et non avec probabilité 1−p, et pour ça, on dispose simplement d'une pièce qui renvoie des bits aléatoires en tirant à pile (0) ou face (1), et on souhaite effectuer les tirages de façon économique. Par exemple, combien de tirages de pièce faut-il, en moyenne, pour générer un événement de probabilité 1/3 ? Il s'avère, en fait, que quel que soit p on peut s'en tirer avec deux (2) tirages en moyenne (je veux dire en espérance). Pour cela, on peut procéder ainsi : on effectue des tirages répétés et on interprète les bits aléatoires ainsi produits comme l'écriture binaire d'un nombre réel x uniformément réparti entre 0 et 1 : on compare x à 1−p en binaire, c'est-à-dire qu'on s'arrête dès qu'on dispose d'assez de bits pour pouvoir décider si x < 1−p ou x > 1−p (on peut considérer le cas x = 1−p comme s'il était impossible vu qu'il est de probabilité 0), en notant qu'on va avoir x < 1−p lorsque le k-ième bit tiré est 0 et que le k-ième bit de l'écriture binaire de p vaut 0, et x > 1−p lorsque le k-ième bit tiré est 1 et que le k-ième bit de p vaut 1 ; et si x < 1−p on renvoie non, sinon oui. Concrètement, donc, faire des tirages aléatoires jusqu'à ce que le k-ième bit tiré soit égal au k-ième bit de l'écriture de p, et alors s'arrêter et renvoyer ce bit-là. Il est clair que cet algorithme fonctionne, mais pour qu'il soit encore plus évident qu'il conduit à faire deux tirages en moyenne, on peut le reformuler de la façon encore plus élégante suivante (il suffit d'échanger les résultats 0 et 1 pour x, qui sont complètement symétriques, lorsque le bit correspondant de p vaut 0) : tirer des bits aléatoires jusqu'à tomber sur 1, et lorsque c'est le cas, s'arrêter et renvoyer le k-ième bit de p (où k est le nombre de bits aléatoires qui ont été tirés). Je trouve ça incroyablement élégant et astucieux (même si c'est très facile), et je ne sais pas d'où sort ce truc. (Cela revient encore à tirer une variable aléatoire k distribuée selon une loi géométrique d'espérance 1, comme je l'explique plus bas, c'est-à-dire valant k avec probabilité (½)^k+1, et renvoyer le (k+1)-ième bit b_k+1 de p, ce qui, quand on écrit p = ∑_k=0^+∞ b_k+1·(½)^k+1, est finalement assez évident.)

Comment tirer un entier aléatoire entre 0 et n−1 à partir de bits aléatoires ? (Ma première réaction en entendant ce problème a été de dire : considérer x uniforme dont l'écriture binaire est donnée par la suite des bits tirés, générer suffisamment de bits pour calculer la valeur de ⌊n·x⌋, où ⌊—⌋ désigne la partie entière, et renvoyer celle-ci. Ceci fonctionne, mais ce n'est pas le plus efficace. Un autre algorithme avec rejet consiste à générer r := ⌈log(n)/log(2)⌉ bits, qui, lus en binaire, donnent un entier aléatoire c entre 0 et 2^r−1, renvoyer c s'il est <n, et sinon tout recommencer. Mais ce n'est pas très efficace non plus, quoique dans des cas un peu différents.) Je décris ce problème plus en détails dans ce fil Twitter, mais donnons juste l'algorithme : on utilise deux variables internes à l'algorithme, notées v et c, qu'on initialise par v←1 et c←0 (il s'agit d'un réservoir d'entropie, et la garantie est que c est aléatoire uniformément réparti entre 0 et v−1) ; puis on effectue une boucle : à chaque étape, on génère un bit aléatoire b (valant 0 ou 1 avec probabilité ½ pour chacun, et indépendant de tous les autres, donc) et on remplace v ← 2v et c ← 2c+b ; puis on compare v avec n et c avec n : si v<n (ce qui implique forcément c<n) on continue simplement la boucle (il n'y a pas assez d'entropie) ; si v≥n et c<n, on termine l'algorithme en renvoyant la valeur c ; enfin, si c≥n, on effectue v ← v−n et c ← c−n et on continue la boucle. Le calcul du nombre moyen de tirages effectués est fastidieux (voir cette référence citée dans le fil Twitter référencée ci-dessus), mais c'est optimal.

L'algorithme que je viens de décrire s'adapte assez bien pour tirer un entier uniforme entre 0 et n−1 à partir d'une source de entiers uniformes entre 0 et m−1 (le cas que je viens de décrire est le cas m=2), autrement dit : comment fabriquer un dé à n faces à partir d'un dé à m faces ? Je n'ai pas vraiment envie de réfléchir à si c'est optimal (mise à jour : on l'a fait pour moi), mais c'est en tout cas assez élégant : on utilise deux variables internes à l'algorithme, notées v et c, qu'on initialise par v←1 et c←0 ; puis on effectue une boucle : à chaque étape, on génère un tirage aléatoire b entre 0 et m−1 à partir de la source dont on dispose et on remplace v ← m·v et c ← m·c+b ; puis on effectue la division euclidienne de v et de c par n : si les deux quotients calculés sont différents (⌊c/n⌋ < ⌊v/n⌋), on termine l'algorithme en renvoyant le reste c%n := c − n·⌊c/n⌋ de la division de c par n, tandis que si les deux quotients sont égaux, on remplace chacun par son reste, c'est-à-dire v ← v%n et c ← c%n et on continue la boucle.

Introduisons maintenant aussi des tirages continus.

[Lire la suite…]