A La Poursuite de Pi [PDF]

Zitiervorschau

À LA POURSUITE DE

1[

Nil desperare (Ne désespérer de rien) Exergue du journal mathématique de Gauss où l'auteur démontre le lien entre le calcul de 1t et la moyenne géométrico-arithmétique

JORG ARNDT

& CHRISTOPH HAENEL

TRADUCTION & ADAPTATION

HENRI LEMBERG & FRANÇOIS GUÉNARD

À LA POURSUITE DE

VUIBERT UN LIVRE DES EDITIONS SPRINGER

Également aux éditions Vuibert : Pierre DUGAc,

Histoire de l'analyse. Autour de la notion de limite et de ses voisinages, 432 pages texte édité par Bernard BRU et Roger LAURENT, préface de Jean-Pierre KAHANE

Albert DUCROCQ & André WARUSFEL, Mathématiques: plaisir & nécessité, 384 pages G. H. HARDY & E. M. WRIGHT,

Introduction à la théorie des nombres, traduit par François SAUVAGEOT,

coédition Vuibert/Springer, 448 pages François Lo JACOMO,

Visualiser la quatrième dimension, illustré par Daniel MULLER, 128 pages

Claudine ROBERT, Contes & décomptes de la statistique. Une initiation par l'exemple, illustré par Yves GUÉzou, 208 pages Sous la direction de H.-D. EBBINGHAUS,

Les nombres. Leur histoire, leur place et leur rôle, de l'Antiquité aux recherches actuelles, traduit de l'allemand et adapté par François GUÉNARD, 464 pages Richard ISAAc, Une initiation aux probabilités, traduit de l'anglais par Roger MANSUY, coédition Vuibert/Springer, 256 pages Sous la direction de Jean-Michel KANTOR, avec le concours de Claude SABBAH,

Où en sont les mathématiques?

coédition Vuibert - Société mathématique de France, 448 pages et des dizaines d'autres ouvrages de sciences et d'histoire des sciences: www.vuibert.fr Ce livre est initialement paru en allemand sous le titre Pi. Algorithmen, Computer, Arithmetik © Springer Verlag, Berlin Heidelberg, 1998,2000 Photographie de couverture: Michel Sittler Couverture: Arnaud Martin Maquette, composition & mise en page des traducteurs Relecture et correction: Dominique Sabrier ISBN: 2 711771709 ISBN 2007: 978-2-7117-7170-7 La loi du 11 mars 1957 n'autorisant aux termes des alinéas 2 et 3 de l'article 41, d'une part, que les « copies ou reproductions strictement réservées à l'usage privé du copiste et non destinées à une utilisation collective» et, d'autre part, que les analyses et les courtes citations dans un but d'exemple et d'illustration, « toute représentation ou reproduction intégrale, ou partielle, faite sans le consentement de l'auteur ou de ses ayants droit ou ayants cause, est illicite» (alinéa 1" de l'article 40). Cette représentation ou reproduction, par quelque procédé que ce soit, constituerait donc une contrefaçon sanctionnée par les articles 425 et suivants du Code pénal. Des photocopies payantes peuvent être réalisées avec l'accord de l'éditeur. S'adresser au Centre français d'exploitation du droit de copie: 20 rue des Grands Augustins, F-75006 Paris. Tél. : 01 44074770

© Vuibert, mars 2006 - 20 rue Berbier-du-Mets, F-75647 Paris cedex 13

Table des matières 1

2

3

L'état de l'art

1

1

Les records

1

2

Un peu d'histoire

5

3

Algorithmes, ordinateurs et arithmétique.

15

4

Pourquoi? . . . . . . .

17

5

De nouveaux objectifs

19

Dans quelle mesure

7r

est-il aléatoire?

21

1

Probabilités . . .

21

2

7r

est-il normal? .

22

3

Et si

4

Le phénomène 163 . . . . .

25

5

D'autres résultats statistiques

29

6

7r

et les intuitionnistes . . . .

30

7

Représentation en fractions continues .

7r

25

n'était pas normal?

Les raccourcis vers

31

35

7r

1

Des approches « obscures» de

2

Petit et beau . . . . . . . .

37

3

Un crible pour approcher

37

4

7r

5

Par mémorisation .

44

6

Bit par bit ..

47

7

Raffinements

48

8

7r

7r

7r

et l'aléatoire: méthodes de Monte-Carlo

habite à Paris.

35

38

49

Table des matières

VI

4

5

6

7

Approximations de

9

et fractions continues

51

1

Les approximations rationnelles

51

2

Autres approximations . . .

55

3

Approximations de jeunesse

65

4

À propos des fractions continues

66

Les formules de l'arc tangente

11

1

La formule de John Machin .

71

2

D'autres formules liées à l'arc tangente

74

Les algorithmes du goutte à goutte

79

1

L'algorithme du goutte à goutte en détail

80

2

Suite d'opérations

82

3

Une variante plus rapide

84

4

Algorithme du goutte à goutte pour e

86

Gauss et 1

8

7r

89

7r

La formule MAG pour

7r

90

2

L'algorithme MAG de Gauss

93

3

La variante de Schonhage

95

4

Histoire d'une formule

98

7r

107

1

Les séries de Ramanujan

108

2

La vie extraordinaire de Ramanujan

110

3

Impulsions . . . . . . . . . . . . . . .

114

Ramanujan et

Les frères Borwein et

7r

10 L'algorithme BBP

117

121

1

Exponentiation binaire . . . . . . . . . .

125

2

Un programme en C pour la série BBP .

127

3

Des améliorations . . . . . . . . . . . .

130

Table des matières

VII

11 L'arithmétique en grande précision

135

1

La multiplication . . . . . . . .

135

2

La multiplication de Karatsuba

136

3

La multiplication par transformation de Fourier rapide (TFR) 139

4

Division....

149

5

Racines carrées

150

6 7

Racines n-ièmes

153 154

Calcul de sommes de séries

12 Questions diverses

157

1

Un questionnaire sur

7r . . . . . .

157

2

Il faut laisser les nombres parler .

158

3

Une « preuve» que

159

4

Le grand changement . . .

159

5

Presque mais pas tout à fait

159

6

Et pourquoi toujours plus?

161

7

7r

et les hypersphères . .

161

8

Viète x Wallis

9

La quadrature du cercle avec des trous

166

10

L'entonnoir infini

167

13 L'histoire de

=c:

7r

=

2

OsIer.

164

169

7r

1

Le symbole

7r

169

2

L'Antiquité.

171

3

Les polygones

174

4

Les expressions infinies

188

5 6

Les algorithmes ultra-performants La chasse aux décimales individuelles de

14 Notes historiques

202 7r

206

211

1

La plus ancienne quadrature du cercle?

211

2

Une loi sur

..... .

213

3

L'histoire de Bieberbach

215

7r

Table des matières

VIII

15 L'avenir: calculs sur le Net

217

1

L'algorithme binsplit ..

217

2

Le projet

221

7r

sur Internet

16 Une collection de formules

223

17 Tables des chiffres de

247

7r

1

Cent premières décimales de quelques constantes

247

2

Décimales de

7r

(de 0 à 1 800 en base 10) . . .

248

3

Décimales de

7r

(de 1 801 à 3 500 en base 10)

249

4

Décimales de

7r

(de 3 501 à 5 000 en base 10)

250

5

Décimales de

7r

(de 0 à 1 800 en base 16) . . .

251

6

Décimales de

7r

(de 1 801 à 3 500 en base 16)

252

7

Décimales de

7r

(de 3 501 à 5 000 en base 16)

253

8

Développement en fraction continue de

9

Développement en fraction continue de 7r (éléments de 701 à 1 400) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255

10

Développement en fraction continue de 7r (éléments de 1 401 à 2 000) . . . . . . . . . . . . . . . . . . . . . . . . . . . ..

7r

(éléments de 0 à 700)254

256

Bibliographie

257

Index général

267

Index des mathématiciens

271

Avant-Propos

Ce livre décrit, en des termes accessibles à tout public disposant de connaissances mathématiques de base, les derniers et les plus fascinants résultats mathématiques et numériques sur le nombre 7r. Ce nombre célèbre, qui vaut approximativement 3.1415, fut historiquement défini comme le rapport de la circonférence d'un cercle à son diamètre, rapport qui ne dépend pas de la taille du cercle. L'étude de ce nombre dure depuis plus de 4 000 ans. Cependant, aucune période de l'histoire de 7r ne fut aussi productive que l'époque contemporaine. Au cours des vingt dernières années, les records mondiaux de calculs de décimales de 7r ont explosé, et le détenteur actuel du record est un professeur japonais qui en novembre 2002 a calculé 1.2 million de millions (i.e. 1.2 x 10 12 ) décimales grâce à un super-ordinateur. Comment a-t-il fait et, surtout, pourquoi l'a-t-il fait? Dans notre ouvrage, une attention toute particulière est portée aux nouvelles méthodes de calcul dont la vitesse surpasse tout ce qui était imaginable avec les anciennes méthodes. La plupart de ces nouveaux algorithmes présentent la particularité plaisante d'être faciles à comprendre. Alors qu'autrefois le temps requis pour calculer un nombre donné de décimales augmentait de manière exponentielle avec ce nombre de décimales, on dispose maintenant d'algorithmes pour lesquels le temps de calcul est pratiquement une fonction linéaire du nombre de décimales recherché. Une autre innovation moderne très récente est l'algorithme BBP mis au point par trois chercheurs canadiens: il permet de calculer directement n'importe quel chiffre du développement héxadécimal de 7r sans devoir aussi calculer tous les chiffres qui le précèdent dans ce développement. En septembre 2000, grâce à un calcul effectué par quelques milliers d'ordinateurs sur Internet, Colin Percival (adolescent à l'époque) utilisa cette méthode pour calculer le mille-billionième (i.e. le 10 15 -ième) chiffre du développement binaire de 7r. Le livre est accompagné d'une page sur le site Vuibert qui contient le code source de chacun des programmes décrits en clair dans le livre. Sur cette page

x se trouvent également des programmes complets, ainsi que les 400 millions premières décimales de 7f, et des renvois vers des sites consacrés à 7f qui présentent un intérêt particulier. Outre les aspects numériques, le livre traite de bien d'autres facettes intéressantes de 7f : par exemple les quarante siècles de sa fascinante histoire. Bien des grands mathématiciens y laissèrent leur empreinte: citons, entre autres, Archimède, Gauss, Legendre, Ramanujan et maintenant, les frères Jonathan et Peter Borwein. Leur quête et celle d'innombrables autres mathématiciens y est contée de manière divertissante. Le livre consacre également une part importante aux aspects curieux et humoristiques de 7f. On donne ainsi les noms de divers « clubs d'amateurs de 7f ». On pourra aussi admirer le plus court programme de calcul de 7f jamais écrit, qui permet de calculer plus de mille décimales, alors que l'écriture en C du programme ne demande que 133 caractères. Beaucoup d'amis et de lecteurs nous ont aidés pour les deux éditions allemandes et l'édition anglaise qui ont précédé cette édition française. Nous aimerions particulièrement remercier le professeur F. L. Bauer de l'université Technique de Munich pour toutes les idées et les suggestions qu'il nous a faites afin d'améliorer tous les thèmes abordés dans ce livre. Nous nous sommes sentis très honorés de recevoir les encouragements et les conseils du professeur Bauer. Nous sommes impatients de recevoir les commentaires des lecteurs de l'édition française. Une adresse électronique sera créée sur le serveur Vuibert à cet effet. J6rg Arndt et Christoph Haenel

1 L'état de l'art Au mois de novembre 2002, une nouvelle étonnante fit le tour du monde: le professeur Yasumasa Kanada de l'université de Tokyo avait établi un nouveau record mondial de calcul des décimales de 7r; il venait de calculer 1 241 100 000 000 décimales. Accompagné de son équipe, Y. Ushiro, H. Kuroda et M. Kudoh, et du personnel de la société Hitachi, ils avaient effectué trois calculs indépendants en utilisant deux algorithmes différents, qui avaient fourni des résultats identiques. Ce calcul avait pris environ 600 heures machine d'un super ordinateur Hitachi. 1

1

Les records

Avec cette nouvelle percée, l'humanité possède maintenant 1.2411 billion de chiffres du développement décimal de 7r, commençant avec 3.1415. Cela fait vraiment beaucoup de chiffres. Les faire défiler très rapidement sur un écran prendrait plusieurs semaines. Si l'on ne voulait imprimer que 100 millions de chiffres du développement de 7r, cela prendrait environ 10 000 feuilles de papier, et il resterait encore 206 milliards de chiffres. Ils occuperaient 30 000 volumes de 1 000 pages chacun, mais on pourrait aussi les faire tenir sur un seul disque dur de grande capacité. Lorsque Yasumasa Kanada annonça ce nouveau record, il s'était passé trois années depuis qu'il avait annoncé le précédent, qui était de 206.1 milliards de décimales de 7r. Ce dernier record venait lui-même 2 ans après le précédent, lequel était de 51,5 milliards de chiffres. En 1981, le record était de 2 millions de chiffres, et il a été depuis battu 26 fois, doublant presque chaque année. Depuis quelques années, Kanada est le seul mathématicien à établir de nouveaux records mondiaux de calcul des décimales de 7r. En 1986, quand le record n'était encore que de 30 millions de chiffres, il avait encore quelques concurrents dans la course. Dix ans plus tard, il n'en restait plus que Kanada au Japon et les frères Chudnowsky aux États-Unis. Ils prenaient l'avantage lhttp://www.super-computing.org

L'état de l'art

2

à tour de rôle; cela jusqu'en 1996 où le seuil des 8 milliards de décimales fut franchi. Depuis 1997 et le record de 51 milliards de décimales, il ne reste en course que Kanada et son équipe. Pour atteindre ces records mondiaux, on s'est généralement servi de superordinateurs spécialement développés pour «broyer» des chiffres et ayant coûté des millions de dollars. Par exemple, Kanada réalisa son dernier record sur un Hitachi SR8000 équipé de 128 processeurs. Néanmoins, si l'on est un peu bricoleur et astucieux, il est possible de construire et d'utiliser de petits ordinateurs pour effectuer des calculs de 7r qui soient encore compétitifs. L'histoire des records du monde nous en donne plusieurs exemples. C'est ainsi qu'il y a quelques années les frères Chudnowsky calculèrent 8 milliards de décimales de 7r à New York sur un ordinateur qu'ils avaient eux-mêmes construit à partir de pièces achetées dans un grand magasin [92J. Et pour les micro-ordinateurs actuels, le programme PiFast de Xavier Gourdon 2 permet de calculer 128 millions de décimales de 7r en quelque 15 minutes et a permis à son auteur de détenir le record mondial de décimales calculées sur un PC, avec 50 milliards. On pourrait s'attendre à ce que Kanada enregistre son calcul de 7r sous forme compressée 3 sur un disque dur de plus de 100Go et le mette en vente pour les personnes intéressées. Mais il considère son approximation de 7r comme étant « non commerciale» et il ne la rendra publique qu'après l'avoir soigneusement vérifiée et s'être assuré qu'elle ne serve qu'à des fins scientifiques. Il a décidé de permettre seulement le téléchargement des premiers milliards de décimales à partir de son serveur Internet de Tokyo. Même avec les nouvelles liaisons à très haut débit, cette tâche pourrait demander quelques heures: sur une ligne téléphonique ordinaire, le transfert d'un milliard de décimales demande un jour complet. Même si le débit des connexions augmente de façon spectaculaire, la puissance des ordinateurs s'accroît de manière similaire, il est bien possible qu'il soit bientôt plus simple de calculer soi-même le nombre de décimales de 7r dont on pourrait avoir besoin. Un tel calcul est aujourd'hui facile à faire tant qu'on reste sur des séquences de quelques centaines de millions de décimales. Et un programme de calcul de 7r, aussi complexe soit- il prendra toujours moins de place que le nombre de chiffres qu'il permet de calculer. Quel est intérêt de disposer d'une séquence de décimales de 7r aussi longue? Une utilisation évidente est la recherche de sous-séquences remarquables, que ce soit par leur fréquence ou par les chiffres qui la composent, par exemple une très longue séquence de décimales toutes égales. L'analyse de quelques milliers de chiffres de la suite des décimales peut sans doute se faire « à la 2http://numbers.computation.free.fr/Constants/PiProgram/pifast.html les décimales de 7r étant (probablement) uniformément distribuées, N décimales tiennent sur 1/(8Iog 2)N ~ O.4N bits. 3 car

3

Les records

main», mais au-delà, il faut un ordinateur. Sur le serveur Vuibert, on trouvera un petit programme de recherche avec lequel on pourra jouer quelques heures en étudiant la séquence de 400 millions de décimales qui se trouve également sur le serveur. Les décimales de 7f se comportent sans doute comme si elles avaient été tirées « au hasard», par une succession de tirages sans mémoire des tirages antérieurs. De tels tirages sont associés à une loi de probabilité que l'on appelle loi binomiale. Lorsqu'on enseigne cette loi aux étudiants, on leur apprend la régularité des moyennes, ici celle de l'apparition de chaque chiffre, de chaque couple de chiffres, de chaque triplet, etc., lorsque la longueur de la séquence considérée tend vers l'infini. Et l'on insiste surtout sur le fait que derrière cette régularité se cache une irrégularité qui est la règle lorsqu'on considère le nombre d'occurrences plutôt que leurs moyennes. La suite des décimales de 7f constitue une formidable illustration concrète de cette irrégularité. Ainsi, lorsqu'on prend au hasard une séquence de 6 chiffres consécutifs du développement décimal de 7f, la probabilité d'obtenir une séquence dont les six chiffres soient égaux est 10- 5 = 0.00001 = 1/10000. La première occurrence de cet événement se produit à la position 768, où l'on trouve six chiffres 9 consécutifs. Certains amateurs de 7f ont donné un nom à cette étape du développement: le point de Feynmann. C'est parce que Richard Feynman (1918-1988), prix Nobel de physique, expliqua un jour que s'il devait réciter les chiffres de 7f, il les donnerait exactement jusqu'à ce point et conclurait alors par et ainsi de suite. Le bloc suivant de six chiffres consécutifs identiques arrive beaucoup plus tard, à la position 193 034. Il s'agit encore une fois d'une séquence de chiffres 9. Le premier zéro de l'écriture décimale de 7f se situe en position 32, un peu plus loin que ce que l'on attendrait. Cette propriété de 7f a facilité la tâche des poètes de 7f cherchant à composer des poèmes dans lesquels le n-ième mot a un nombre de lettres égal au chiffre placé en n-ième position de l'écriture décimale de 7f. Stricto sensu, un zéro du développement devrait mettre fin au poème. De tels poèmes ont été écrits dans beaucoup de langues. Voici le début de deux d'entre eux, un en français, et un en anglais. Que j'aime à faire connaître un nombre utile aux May l have a large container of coffee? Cream and 9 2 6 5 3 3 1 4 1 5

sages sugar?

5

Où la séquence 0123456789 apparaît-elle pour la première fois dans le développement de 7f? C'est seulement en 1997, avec l'un des derniers records, que l'on a enfin pu répondre à cette question fondamentale! Cette séquence arrive pour la première fois en position 17 387 594 880, loin au-delà de la

L'état de l'art

4

6.4 milliardième décimale, qui était auparavant la dernière connue. Une séquence voisine, formée de dix chiffres consécutifs tous différents, arrive pour la première fois beaucoup plus tôt, en position 60. Dès le XVIIe siècle, des mathématiciens avaient calculé 7r aussi loin, comme nous l'apprend l'histoire de 7r. Les fanatiques des nombres pourraient peut-être chercher dans le développement de 7r des positions auto-référentielles, dans lesquelles la séquence numérique est la même que la position elle-même. La première position de ce type arrive au tout début, en position 1. Les suivantes sont en 16 470 et 44 899, mais la quatrième ne se trouve qu'en 79 873 884. On ignore encore s'il y a d'autres positions auto-référentielles. Beaucoup de gens se demandent où se trouve dans le développement de 7r leur numéro de téléphone, de sécurité sociale, ou leur date de naissance: où suis-je dans 7r? Par exemple, les dates de naissance des deux auteurs sont en positions 5 407 560 et 14 666 671. On pourrait imaginer d'imprimer sur ses cartes de visite des positions de décimales de 7r donnant des informations personnelles. Il y a sur Internet un jeu comme cela, qui se limite actuellement à 50 millions de décimales. 4 On est sûr que, quelque part dans le développement de 7r, on trouve toute séquence finie de chiffres. Moyennant un codage approprié, on y trouve donc tout texte, du plus court au plus long, dans n'importe quelle langue. On y trouve aussi tout morceau de musique. En revanche, le développement de 7r ne contient aucune suite infinie autre que ses propres suites extraites; il contient celui de 7r lui-même (une seule fois), et il ne contient par exemple ni celui de 7r + 1, ni celui de )2. On peut représenter l'ADN d'un être humain avec environ 3.6 milliards de chiffres, de sorte que la séquence traduisant votre ADN figure peut-être dans la séquence de décimales de 7r déjà calculée. Peut-être, mais c'est hautement improbable. Par exemple, le nombre de décimales que Kanada a calculées ne contient même pas la totalité des nombres de 20 chiffres, qui est de 10 20 c'està-dire beaucoup plus que les quelques lOll chiffres obtenus par Kanada. Cela représente une partie encore plus faible des nombres à 21 chiffres. Cela rend tout à fait invraisemblable le fait que cette séquence puisse contenir disons la Bible. On estime le codage numérique de cette dernière à 107 chiffres, ce qui signifie une espérance du temps d'attente pour trouver une séquence 107 la représentant d'environ 10 chiffres, tandis que nous n'en avons pour 1 l'instant qu'un peu plus de 1010 . Pourra-t-on un jour calculer un tel nombre de décimales de 7r? On pense que non, car l'univers ne contient qu'environ 10 79 particules élémentaires; si l'on 4http://www.aros.net/-angio/pi_stuff/piquery

5

Un peu d'histoire

transformait l'univers tout entier en un gigantesque ordinateur, celui-ci ne pourrait stocker qu'à peu près 10 76 décimales de 7r, ce qui est peu comparé 107 aux 10 chiffres qu'il faudrait en moyenne calculer pour obtenir une séquence pouvant représenter la Bible. Il est cependant, tout à fait concevable que l'on puisse calculer individuellement des chiffres occupant des positions de cet ordre de grandeur.

2

Un peu d'histoire

Ceux qui recherchent la célébrité pourront s'attaquer au problème ouvert de la normalité ou de la non-normalité de 7r. Si 7r n'était pas normal, cela signifierait que certaines séquences de chiffres se trouvent plus fréquemment que d'autres dans le développement de 7r. La démonstration d'un tel résultat ferait assurément les titres des journaux. Jusqu'à présent, personne n'a trouvé de partie du développement qui suggère que 7r ne puisse être normal. Les tentatives utilisant le développement hexadécimal, qui commence par 3.243F6A8885, se sont révélées aussi infructueuses que celles utilisant le développement décimal. Aucune irrégularité non plus n'est apparue dans la représentation simple de 7r en fraction continue, i.e. dans la représentation de 7r sous forme d'une fraction infinie dont les numérateurs successifs sont tous égaux à 1, 7r

1

= 3 + ----------1

7+-------1

15+------1+

1

1 292+-1 + ...

Les fractions continues simples d'autres nombres transcendants comme celle de e font apparaître des modèles reconnaissables. Ces résultats expérimentaux ont conduit les mathématiciens à conjecturer que 7r devait être un nombre normal. Mais à ce jour, personne n'est parvenu à démontrer ou à infirmer cette conjecture. Peut-être y a-t-il quelque part dans le développement décimal de 7r une propriété remarquable qui n'attend que d'être observée. Nous aborderons cette question dans le prochain chapitre. Il n'est pas certain que 7r soit normal. En revanche, il est définitivement acquis que c'est un nombre irrationnel, comme le démontra en 1766 le mathématicien alsacien Johann Heinrich Lambert (1728-1777) . Un nombre est dit irrationnel s'il n'est pas rationnel, c'est-à-dire s'il ne peut pas être représenté comme un quotient de deux entiers. Par exemple, la fraction 355/113 = 3,141592 ... est une très bonne approximation de 7r dont elle

6

L'état de l'art

donne 6 décimales correctes. Elle n'est néanmoins pas égale à 'if, et aucune autre fraction non plus. L'approximation 355/113 fut découverte en Chine au Ve siècle ap. J.-C. par Tsu Chhung-Chih et, durant presque 800 ans, ce fut la meilleure approximation de 'if disponible. Cette approximation est décrite, accompagnée de quelques autres, au chapitre 4. On sait également que 'if est transcendant. En 1882, une preuve célèbre, mais extrêmement compliquée en fut fournie par le mathématicien munichois Ferdinand Lindemann (1852-1939), plus de 100 ans après que Lambert eut démontré l'irrationalité de 'if. Le théorème de Lindemann affirme qu'il n'existe aucun polynôme à coefficients rationnels dont 'if soit une racine. Il est vrai, par exemple, que 9'if4 - 240'if 2 + 1492 est très proche de 0 (plus précisément, -0.02323 ... ), mais il est impossible de trouver une telle expression qui donne exactement O. Il est surprenant que, plus d'un siècle après la démonstration de la transcendance de 'if, on ne sache pas grand chose de plus sur 'if. Certes on sait maintenant que 'if2, e 1r et 'if + ln 2 + V2ln 3 sont transcendants. Mais on ignore encore quelle est la nature rationnelle ou non de quantités similaires telles que e+'if, e''if, 'if/e, ln 'if ou 'ife. Beaucoup d'autres questions concernant 'if n'ont pas de réponse. Par exemple on ne sait toujours pas si 'if est un nombre normal ou pas, et il ne semble pas qu'on soit près de trouver une réponse, car jusqu'à présent, personne n'a d'idée sur la méthode qu'on pourrait utiliser pour attaquer ce problème. Et tout ce que nous apporte le calcul des 206.1 premiers milliards de décimales de 'if, c'est une information triviale telle que la fréquence et la distribution de brèves séquences de chiffres [11, p. 203]. Le nombre 'if est l'un des plus vieux sujets de recherche pour l'humanité et c'est sans doute le sujet qui a, dans l'univers des mathématiques, suscité le plus de recherches. Les hommes se s'intéressent à 'if depuis plusieurs milliers d'années. Par exemple, en 2000 av. J.-C., les Babyloniens et les Égyptiens avaient déjà découvert des approximations de 'if à moins de 0.02 près. Durant plus de 4 000 ans, les chercheurs continuèrent inlassablement à essayer de découvrir les secrets de 'if. L'histoire fascinante de cette quête est traitée plus en détail dans le chapitre 13. Quand on considère tout le travail qui a été fait sur 'if, le peu que l'on en sait est assez surprenant. Mais quand on sait que la théorie des nombres n'a pas d'égal dans l'art de poser des questions simples dont les réponses soient aussi compliquées, ce n'est guère surprenant. Un exemple célèbre est ce qui fut longtemps connu comme le dernier théorème de Pierre de Fermat (1601-1665) de 1637, qui affirme que si n > 2, l'équation xn + yn = zn n'a pas de solutions entières. Ce fut pendant près de deux siècles le problème

Un peu d'histoire

7

de mathématiques le plus célèbre, et bien que son énoncé fût simple et compréhensible par tous, il ne fut résolu qu'en 1994 par Andrew Wiles, qui en donna une solution extrêmement compliquée prenant plus d'une centaine de pages. En revanche, il reste en théorie des nombres beaucoup de problèmes ouverts qui sont faciles à formuler mais qui résistent à toutes les tentatives de résolution; par exemple une question célèbre est de savoir s'il existe une infinité de paires de nombres premiers dont la différence soit égale à deux, comme {5, 7}, {11, 13}, {17, 19}, ou {10 007,10 009}. Une question simple que personne n'a encore résolue. Avec sa preuve de la transcendance de 7r, Lindemann régla un autre problème qui avait préoccupé les cerveaux des meilleurs mathématiciens et philosophes depuis les Grecs anciens et qui était déjà connu en 414 av.J.-C. puisqu' Aristophane en parle dans sa comédie « Les Oiseaux ». C'est le problème de la quadrature le cercle, qui consistait à trouver une construction à la règle et au compas d'un carré dont l'aire soit égale à celle d'un disque donné. Si l'on note r le rayon du disque, on requiert de construire le côté de longueur x d'un carré dont l'aire x 2 soit égale à celle du disque, 7rr 2 . La longueur des côtés du carré doit donc être égale à x = ryl7f . Il est en général impossible de construire à la règle et au compas un segment de longueur donnée. Seules les longueurs qui satisfont à des conditions précises peuvent l'être: en font partie les longueurs entières, celles qui résultent d'opérations rationnelles telles que l'addition ou la division, ou de la formation de racines carrées [32, p. 347J. On peut par exemple construire un segment de longueur iVI7, mais pas un segment de longueur 3{Y3. L'expression x = ryl7f contient une multiplication et une racine carrée, et satisfait donc aux règles mentionnées. Mais pour résoudre la quadrature du cercle, il faudrait pouvoir construire un segment de longueur yI7f , et c'est justement ce dont le théorème de Lindemann montre l'impossibilité. Il s'ensuit qu'il est impossible de construire à la règle et au compas un carré dont l'aire soit égale à celle d'un disque donné. En revanche, si les conditions requises sont affaiblies, c'est possible. Par exemple, en géométrie hyperbolique il y a un disque dont l'aire est égale à 7r, qui peut être transformé en un carré de même aire, à l'aide d'une règle et d'un compas; mais dans cette géométrie non euclidienne, une ligne droite ne peut pas être tracée avec une règle. En 1882, en montrant que ce problème n'admet pas de solution, Lindemann résolut une fois pour toutes le problème de la quadrature du cercle. On aurait pu s'attendre à ce que toutes les tentatives pour résoudre le problème cessassent aussitôt. Il n'en fut rien! Beaucoup de gens ont continué à s'attaquer au problème, et aujourd'hui encore, cela perdure. L'Américain Dudley a consacré une monographie à ces gens qui deviennent obsédés par un problème mathématique, qu'il qualifie en anglais de mathematical cranks. Outre les obsédés du grand théorème de Fermat, ceux de la conjecture de Riemann, et de

L'état de l'art

8

quelques autres problèmes, il mentionne quelques « quadrateurs de cercles», tel le constructeur de navires O. Z. (Otto Zimmermann) de Hambourg, qui publia en 1983 un livre intitulé « 7r est rationnel». Dans son livre, Dudley propose un classement de ceux qui se sont attaqués, ou s'attaquent encore au problème de la quadrature du cercle. Selon cette classification, O. Z. est un membre de l'espèce relativement rare de ceux qui font évoluer leur opinion au fil du temps: avant 1975, sa construction conduisait à une valeur de 7r égale à 3.141 592 653 5576, alors que jusqu'en janvier 1976 elle fut de 3.141 592 653 598, tandis qu'ensuite, elle se simplifia à exactement 3.1428. est le rapport de la circonférence c d'un cercle sur son diamètre d; autrement dit, 7r = cid. C'est la définition géométrique classique du nombre 7r. Une deuxième définition géométrique énonce que 7r est le rapport de l'aire A d'un disque sur le carré du rayon r de ce disque; autrement dit, 7r = Alr 2 . On en déduit l'assertion évidente selon laquelle le rapport de l'aire du disque sur l'aire du carré circonscrit à ce disque vaut 7r 14. 7r

Plusieurs milliers d'années av. J.-C., les plus anciennes cultures indoeuropéennes étaient déjà conscientes qu'il existait un rapport constant entre la circonférence et le diamètre de tous les cercles, grands ou petits. Le second rapport fixe, celui qui relie les aires, fut lui aussi découvert dans un passé incroyablement lointain, mais peut-être cela est moins clair que pour le premier. Toutefois, ce n'est sans doute que dans la Grèce antique que fut identifiée l'identité commune des deux rapports, faisant intervenir un même nombre. Ce fait n'est pas immédiat à percevoir. La figure ci-dessous est peut-être l'illustration la plus simple de ce lien.

;:::; rayon ;:::; circonférence

Dans l'image de gauche, un cercle a été partagé en un grand nombre de secteurs égaux. Si l'on déplace ces secteurs pour les mettre côte à côte, on obtient l'image de droite, où les secteurs remplissent la moitié un rectangle. Plus le nombre de secteurs est grand, plus la longueur de la base de l'image de droite (la longueur du rectangle) se rapproche de la longueur de la circonférence du cercle, tandis que la hauteur du rectangle tend vers la longueur du rayon du cercle. Les secteurs ne remplissent que la moitié de la superficie du rectangle, et par suite, en passant à la limite, l'aire de ce rectangle est égale à deux fois l'aire du disque. Ainsi, 7r apparaît-il à la fois dans la formule donnant l'aire d'un disque, et dans celle donnant la longueur d'un cercle. Outre la définition géométrique de

7r,

il y en a beaucoup d'autres, certaines

9

Un peu d'histoire

provenant de contextes très différents. Par exemple, problèmes de probabilités.

TI

apparaît dans des

Quelle est la probabilité qu'une pièce lancée un nombre pair de fois tombe un même nombre de fois sur pile et sur face? La réponse est facile : si la pièce est lancée 2n fois, avec deux résultats possibles à chaque fois, il y a 2 2n résultats possibles, et façons d'obtenir un nombre de lancers ayant

e:)

donné face égal à n. Ainsi la probabilité p vaut-elle

(1.1 )

p=

(2n2n ) 2 n

c'est-à-dire

1 x 3 x 5 x ... x (2n - 1) 2 x 4 x 6 x ... x 2n

Avant l'arrivée des ordinateurs, le calcul de p pour de grandes valeurs de n était fastidieux, et les mathématiciens de l'époque pré-informatique utilisaient des approximations. Ici, on peut utiliser une formule découverte par John Wallis (1616-1703), faisant intervenir des produits infinis,

(1.2)

3x3x5x5x7x7··· 2x4x4x6x6x8x···

4

Il n'est pas difficile de voir [123] que le produit de Wallis survient dans la formule donnant p, de telle façon que

(1.3)

1 p~--

y7m

Avec 62 lancers, on obtient une probabilité de 0.1. Ainsi nous avons ici une définition de TI ne faisant pas intervenir les cercles. Bien que l'on n'utilise que des entiers, le nombre transcendant TI apparaît encore dans la formule. Le nombre TI figure dans beaucoup d'autres énoncés liés aux probabilités. Il intervient en particulier dans la courbe de Gauss de la loi normale, utilisée par exemple pour les tables de risque des assurances-vie. Ce qui a amené certaines personnes à dire que TI intervient même après la mort ... Il existe même des définitions de TI qui sont plus abstraites, par exemple, des définitions analytiques utilisant des intégrales. En voici deux exemples particulièrement attrayants qui furent découverts par le mathématicien suisse Leonhard Euler (1707-1783).

10

(1.4)

L'état de l'art

7r

=4

1 1

dx

o \.11 - x 4

11 0

x

2

\.11 - x 4

dx

ou

(1.5) On pourra se délecter de toute une gamme de formules sur collection de formules du chapitre 16.

7r

dans notre

Dans leurs cours, certains professeurs de mathématiques emploient encore une autre définition. Selon cette définition, ~ est défini comme le plus petit zéro positif de la fonction cosinus. Comme cette fonction est strictement positive en 0, strictement négative en 2, et qu'elle est continue, elle possède au moins un zéro entre 0 et 2. L'ensemble des zéros de cette fonction continue étant donc non vide, et par ailleurs fermé, il possède un plus petit élément dans le segment [0, 2]. C'est ce zéro que l'on appelle ~. En 1933, aussi incroyable que cela paraisse, l'utilisation de cette définition par le mathématicien Edmond Landau servit de prétexte pour lui faire perdre sa chaire à l'université de Güttingen, en Allemagne; à cette époque, cette définition fut jugée « anti-allemande ». On trouvera au chapitre 14 les détails de cette sordide histoire. Le nombre 7r a fasciné de nombreuses personnes au fil des âges, mais il est vraisemblable qu'il n'y ait jamais eu autant d'amateurs de 7r qu'aujourd'hui. À l'appui de cette thèse, le nombre de sites Internet consacrés à 7r : au moins 200 sites dont c'est le thème principal, et des milliers de pages y faisant référence. On peut trouver sur Internet beaucoup d'informations sur 7r. À consulter en particulier les sites des chercheurs qui se sont illustrés dans le domaine, comme ceux de Yasumasa Kanada et ceux des frères Peter et Jonathan Borwein, qui développèrent les algorithmes que Kanada employa pour exécuter ses calculs de 7r. Les Borwein et nombre d'autres chercheurs ont mis en ligne certains de leurs articles pour qu'on puisse les y télécharger. Il existe également sur Internet nombre de clubs sur 7r. Il est souvent possible d'en devenir membre, mais il faudra généralement passer un examen d'entrée. Celui-ci consiste souvent à réciter par cœur les premières décimales de 7r. Par exemple le «Freunde der Zahl 7r» (Amis du nombre 7r) à Vienne, qui publie aussi un journal appelé « 7r vobis cum », exige de ses membres qu'ils puissent

Un peu

d'histoire

11

réciter par cœur les 100 premières décimales. Si vous souhaitez y adhérer, on verra dans le chapitre 3 quelques moyens mnémotechniques ... Quand on parle de 1f, e n'est jamais très loin. Peut-être est-ce parce que ce nombre, connu comme la « base des logarithmes néperiens », ou comme « le nombre de Neper», e = 2.71 ... est relativement proche de 1f, au moins par le fait qu'il partage avec 1f la propriété d'être transcendant. Une autre raison pourrait être que les deux nombres sont reliés par une merveilleuse formule d'Euler (1.10), que nous allons voir ci-dessous. Autrement, 1f et e n'ont pas grand-chose en commun. Le nombre e ne fut découvert que relativement récemment, il y a environ 400 ans, tandis que 1f est dix fois plus vieux; e est un sous-produit de l'analyse infinitésimale qui fut développée au XVIIe siècle quand les mathématiciens développèrent la notion de limite. C'est ainsi que e fut obtenu. Voici une façon concrète d'introduire e : à l'issue d'une année, avec un taux annuel de 100%, que deviendrait une somme d'argent de 1 unité si les intérêts déjà accumulés étaient replacés, avec des périodes d'intérêt de plus en plus courtes? La réponse est e unités. Pour comprendre le mécanisme, voyons l'effet de la période de calcul des intérêts: avec un calcul annuel, la somme placée deviendrait 2 unités. Avec un calcul semestriel, la somme deviendrait 1.5 = 1 + 1/2 au bout de six mois, puis 1.5 x 1.5 = 2,25 = (1 + 1/2)2 au bout d'un an. Pour un calcul trimestriel, elle donnerait 1 + 1/4 = 1.25 au bout d'un trimestre, puis (1 + 1/4) x (1 + 1/4) = 1.25 x 1.25 = 1.5625 au bout d'un semestre, 1.5625 x 1.25 = 1.95313 au bout de trois trimestres, et enfin 1.95313x 1.25 = 2.44141 au bout de l'année, c'està-dire (1 + 1/4)4. Pour un calcul mensuel des intérêts, au bout de l'année, la somme deviendrait (1 + 1/12)12 = 2.61304. On voit que plus les intérêts sont capitalisés souvent, plus la somme augmente. Si l'on coupe l'année en n, la somme placée devient (1 + l/n)n, et lorsque n tend vers l'infini, le montant tend vers e. On a calculé beaucoup moins de décimales de e que de 1f. Depuis février 1999, 200 millions de décimales ont été calculées par Sébastien Wedeniwski, soit exactement un millième du nombre de décimales de 1f qui ont été calculées. (Les frères Chudnowsky ont prétendu avoir calculé un milliard de décimales de e, mais cela n'a pas été confirmé officiellement.) Cette disparité a conduit certains à supposer que e est plus difficile à calculer que 1f, mais cela n'a jamais été prouvé. Le dernier record du monde de calcul des décimales de 1f fait de ce nombre celui dont on a calculé le plus grand nombre de décimales. Numéro deux dans la liste des nombres dont on calculé le plus grand nombre de décimales, on trouve l'inverse de 1f, 1/1f = 0.318 309 886 61 ... dont on a calculé 206.1 milliards de décimales. Vient ensuite la racine carrée de 2 (J2 = 1.414 213 5623 ... ), avec 137 milliards (~ 237 ) de décimales connues.

12

L'état de ,'art

Les calculs de ces trois constantes ont été exécutés par Kanada. On trouve ensuite (depuis octobre 1999) e = 2.718 281 8284 ... (1 milliard ou 200 millions de décimales connues, comme on l'a vu plus haut), la constante d'Apéry ((3)

=

1 L"3 = 1.202 056 9031 ... (128 millions de décimales) et n

In(2) = 0.693 147 1805 ... (108 millions de décimales). On trouvera sur le site Vuibert un renvoi vers une table des records. On connaît non seulement les 206.1 premiers milliards de décimales de 7r, mais aussi quelques chiffres du développement hexadécimal ou du développement binaire, de rangs plus élevés. Ainsi par exemple, depuis septembre 2000, on connaît le mille billionième chiffre du développement binaire de 7r, un 0 (attention en consultant les sites Internet sur 7r : en français, les millions, billions, trillions, quadrillions ... vont de 106 en 106 , tandis qu'aux USA, ils vont de 10 3 en 10 3 ; ainsi, en français, un billion = 10 12 , tandis qu'en anglais, « one billion» = 109 = un milliard (français)). Ce résultat étonnant a été obtenu grâce à une nouvelle approche du calcul de 7r qui fut découverte par hasard en 1995. Elle est expliquée au chapitre 10. Le calcul des 206.1 premiers milliards de décimales de 7r n'a pas encore été exploité par les artistes, tandis que la conception de formules théoriques reste un art. Il ne fait aucun doute que l'existence de magnifiques formules sur 7r a fortement contribué à le rendre fascinant. Voici une sélection des formules disponibles, par ordre chronologique: 1. François Viète (1540-1603) découvrit en 1593 le premier produit infini de 2

somme -

7r

(1.6)

2 = -V2

V2+V2

VV2+V2

x - - - - x -'------ x ... 2 2 2

-

7r

Cette formule montre que 7r peut être exprimé avec une formule n'utilisant comme seul chiffre que le chiffre 2. (Comparer avec les formules 16.137). 2. Lord William Brouncker (vers 1620-1684) découvrit en 1658 la première fraction continue de 7r : (1. 7)

4

12

- = 1 + ------::---2 3

2 + ------=----

52

2 + ------,,--2

7

2 + ------,;:-2

9

2+-2+ ...

Un peu

d'histoire

13

FRANÇOIS VIÈTE

La caractéristique inhabituelle de ce développement en fraction continue réside dans la présence d'une forme régulière (12,3 2,5 2,72 ... ). Il ne s'agit pourtant pas d'une fraction continue simple, car les numérateurs ne sont pas tous des 1. La fraction continue simple de 7r ne montre, elle, aucune régularité. 3. De 1650 à 1973, pratiquement tous les calculs de 7r furent exécutés en utilisant des formules en arctangente. La formule de ce type la plus fréquemment employée fut celle de John Machin (1680-1752), qui s'en servit en 1706 pour obtenir ce qui constituait alors un record du monde, avec 100 décimales. 7r

1

1

4

5

239

- = 4 arctan - - arctan -

(1.8)

4. La série suivante fut découverte en 1914 par le mathématicien indien S. Ramanujan (1877-1920) ; elle converge extrêmement rapidement. Le calcul de chaque terme de cette série permet d'obtenir 8 décimales supplémentaires de 7r (1.9)

~ 7r

=

J8

~ (4n)! x 103 + 26390n (n!)4 396 4n

9801 L

n=O

L'état de l'art

14

5. De toutes les formules mathématiques sur 1f, la plus belle est assurément celle d'Euler: elle fut découverte en 1743 par le mathématicien suisse Leonhard Euler, et au sein d'une unique formule, elle fait intervenir cinq constantes fondamentales, 1f, e, i, 0 et 1, et quatre opérations de base, la somme, le produit, l'égalité et l'exponentiation:

(1.10)

i1f

e

+ 1 = O.

Cette formule a toujours exercé une certaine fascination, sans doute en raison de son caractère attrayant. Une autre formule relie

1f

et e, sans faire intervenir les nombres complexes:

(1.11)

-=2+4L----=--

e+1

CXl

e- 1

r=l

1

(21fr)2

+1

Encore et toujours, le nombre 1f a inspiré poètes et philosophes. Dans sa nouvelle intitulée « Contact», Carl Sagan imagine un extraterrestre disant à une Terrienne que 1f contient un message crypté important pour l'humanité. Il explique à cette femme que à un endroit précis du développement décimal de 1f, les chiffres cessent soudainement d'être distribués aléatoirement et qu'alors le développement contient une séquence formée de 0 et de 1 représentant l'écriture binaire du produit de 11 nombres premiers. Il s'agit donc d'un message en dimension 11. L'envoyeur utilise ainsi les mathématiques pour communiquer avec des humains. Son message même sera authentifié, car la séquence de 0 et de 1 ne se retrouve que dans le développement décimal de 1f, et ne sera donc trouvé que par des créatures utilisant ce système de numération, naturel lorsqu'on possède dix doigts. Ce message important a été dans 1f durant des milliards d'années, dans l'attente qu'il existe des mathématiciens à dix doigts munis d'ordinateurs assez puissants pour découvrir cette séquence, à l'évidence les hommes de notre époque. De telles histoires illustrent bien l'engouement pour 1f que l'on rencontre partout dans le monde. Et elles sont bienvenues pour les mathématiciens travaillant sur 1f, qui ont toujours besoin de nouvelles raisons pour justifier leurs demandes de crédits de recherche. Indiscutablement, 1f est une constante naturelle valable dans tout l'univers, s'appliquant de la même façon à tous les êtres vivants. Cela pourrait donc constituer un bon point de départ pour établir un contact avec des extraterrestres. D'aucuns ont même suggéré que 1f devrait être peint sur toutes les sondes spatiales quittant notre système solaire.

Algorithmes, ordinateurs et arithmétique

15

Douglas R. Hofstadter fit sensation il y a quelques années avec trois livres remarquables; dans « Métamagicum Il, il écrit « Si 7r était égal à 3, ... !! Ce qu'Hofstadter explique ensuite, c'est que si 7r était égal à 3, personne n'aurait l'idée d'écrire cette phrase. L'emploi du si serait lui aussi inutile, car on écrirait plutôt comme 7r est égal à 3 .... L'égalité 7r = 3 aurait des conséquences considérables : comme l'hexagone est le seul polygone à posséder un rapport périmètre/diamètre égal à 3, tous les cercles seraient des hexagones. Le zéro ne s'écrirait pas comme un rond, mais plutôt comme un hexagone.

3

Algorithmes, ordinateurs et arithmétique

L'histoire des calculs de

7r

peut être découpée en trois phases distinctes. La

première époque commence autour de 250 av.J.-C. avec le mathématicien grec Archimède de Syracuse. Avant lui, seules des méthodes expérimentales avait été employées; il fut le premier à développer une procédure systématique pour approcher 7r avec précision. Il calcula les longueurs de polygones réguliers; il considéra ensuite un cercle, et deux polygones réguliers à n côtés, l'un inscrit dans le cercle, l'autre circonscrit à ce cercle. Les longueurs de ces deux polygones fournissent un encadrement de la longueur du cercle. Plus n augmente, plus l'encadrement est fin. Archimède commença avec des hexagones réguliers et continua avec des polygones à 12,24,48 et enfin 96 côtés. En utilisant cette méthode, il obtint pour 7r l'encadrement 3 + 10/71 < 7r < 3 + 1/7. Les deux valeurs donnent deux décimales correctes de 7r. Dès lors, tous ceux qui trouvaient compliqué de considérer deux nombres pour approcher 7r se contentèrent du majorant, 3 + 1/7, de sorte que cette approximation devint rapidement la valeur standard de 7r utilisée pendant la plus longue période dans le monde entier. Au Moyen Âge on trouvait même des érudits qui croyaient que cette valeur était exacte. Mais plus important que la qualité de l'approximation, fut le fait que la méthode d'Archimède fut reprise et utilisée pendant presque 2 000 ans par tous les mathématiciens travaillant sur 7r. Au fil des siècles, ces mathématiciens augmentèrent le nombre de côtés des polygones employés pour les calculs; c'est ainsi qu'en 1630, lorsque cette ère de l'approximation géométrique s'acheva, on connaissait les 39 premières décimales de 7r. La deuxième époque commença au milieu du XVIIe siècle avec la découverte de l'analyse infinitésimale et des expressions infinies. Une nouvelle méthode, fondée sur l'utilisation de développements en série de la fonction arctangente s'imposa (voir chapitre 5), et occupa le devant de la scène pendant plus de 300 ans, jusqu'en 1980. Le premier calcul poussé de 7r reposant sur cette méthode permit d'obtenir en 1706 exactement 100 décimales de 7r, avec des

16

L'état de l'art

calculs menés à la main; en 1973, un ordinateur permit d'obtenir grâce à cette méthode un peu plus d'un million de décimales. Nous sommes actuellement dans la troisième époque de l'histoire des calculs de décimales de 7r. Elle a commencé autour de 1980 quand des mathématiciens découvrirent comment combiner trois développements récents dans des domaines apparemment indépendants. Le premier développement porta sur une opération arithmétique apparemment simple, la multiplication de nombres longs: c'est l'opération élémentaire intervenant dans les calculs de 7r, et le progrès fut d'accélérer cette opération, ce qui réduisit le temps nécessaire au calcul de la somme d'un nombre donné de termes d'une série. Aussi étonnant que cela soit, c'est seulement en 1965 que fut découverte cette nouvelle méthode de multiplication, connue maintenant comme la multiplication par transformation de Fourier rapide. (TFR) Lorsqu'on double la longueur (i.e. le nombre de chiffres) de deux nombres que l'on multiplie par la méthode scolaire, c'est-à-dire la méthode apprise à l'école primaire, le temps de calcul est multiplié par quatre: la méthode de multiplication scolaire est quadratique. Lorsqu'on utilise la méthode de multiplication par TFR, le temps de calcul augmente quasiment linéairement avec la longueur des nombres que l'on multiplie. Nous verrons au chapitre 11 un exemple numérique pour lequel la méthode scolaire prend une journée tandis que la méthode de multiplication par TFR ne prend que 3 secondes. La second percée majeure fut le développement d'algorithmes très efficaces conçus spécifiquement pour calculer les décimales de 7r. Ils surpassent très largement les formules en arctangente. Ces algorithmes utilisent encore des séries, mais ils sont beaucoup plus productifs que les meilleures séries en arctangente. Nous avons déjà mentionné une telle série trouvée par Ramanujan, dont le calcul de chaque nouveau terme fournit 8 décimales supplémentaires de 7r (1.9). Une série encore plus efficace fut mise au point par les frères Chudnowsky (8.7) ; chaque nouveau terme fournissait 15 décimales de 7r. Ils s'en servirent en 1989 pour calculer un milliard de décimales, ce qui constituait à l'époque le record. Les autres algorithmes de calcul de 7r fonctionnent de manière entièrement différente; ils furent pour la plupart développés au début des années 1980 par deux frères canadiens, Jonathan et Peter Borwein (nés respectivement en 1951 et en 1953). Un de ces algorithmes quadruple le nombre de décimales obtenues à chaque calcul d'un nouveau terme. On parle dans ce cas de vitesse « quartique». En 1999, c'est cet algorithme qui permit à Kanada de calculer en seulement vingt itérations les 206.1 premiers milliards de décimales de 7r. Le principe général de telles procédures est discuté en détail dans les chapitres 7 et 9. Au débu_t du XIX e siècle, le mathématicien allemand Carl

Pourquoi?

17

Friedrich Gauss (1777-1855) avait en fait déjà développé avec précision un tel algorithme ultra-rapide. Cependant, pour diverses raisons sa procédure resta ignorée pendant plus de 170 ans. Le troisième développement, qui de nos jours passe pratiquement inaperçu, est l'explosion des performances des ordinateurs. Une loi empirique qui s'est pour l'instant toujours vérifiée est que l'ordinateur type du moment double sa vitesse tous les deux ans. Ce seul facteur a contribué par un coefficient d'au moins 1000 à l'explosion des calculs de décimales de 7r depuis le début des années 1980. Évaluées en ces termes, les 2 millions de décimales calculées par Kanada en 1981 pour son premier record sont équivalentes aux 2 premiers milliards de décimales de son record mondial de 1999. Grâce à la mise en œuvre combinée de ces trois développements, il y a eu un énorme accroissement de productivité. Depuis 1981 le nombre de décimales connues de 7r a été multiplié par 100 000, jusqu'au record actuel de 206.1 milliards de décimales. C'est l'équivalent d'un facteur de croissance de 190% par an. Peu de domaines peuvent montrer un tel taux de croissance !

4

Pourquoi?

Qu'est-ce qui motive des gens à poursuivre ces insaisissables décimales de 7r? Pour des calculs pratiques, les 10 premiers chiffres du développement décimal sont généralement suffisants. Avec 39 chiffres, on peut calculer le volume de l'univers avec une précision de l'ordre de l'atome. Du fait d'instabilités numériques, certaines applications scientifiques réclament des calculs intermédiaires effectués avec beaucoup plus de chiffres que le résultat final, mais aucune application connue à ce jour ne réclame plus de 100 chiffres. On peut imaginer qu'on découvrira un jour des situations réclamant le calcul de plus de 1000 chiffres, mais certainement pas plus que ça [13]. La précision à laquelle 7r peut être calculé semble dépasser de loin tout besoin pratique; alors pourquoi continuer? Il existe une motivation pratique pour les grands programmes de calcul de 7r, c'est la vérification des systèmes informatiques, matériels et logiciels. Pour calculer des milliards de décimales de 7r, il faut exécuter des milliers de milliards d'opérations arithmétiques, et le moindre défaut dans le matériel, dans le système d'exploitation ou dans le logiciel devient apparent. Il est arrivé que des calculs de 7r mettent en évidence des erreurs logiques dans la conception de certains ordinateurs. Un gros calcul de 7r effectué sans faute est un élément assez fiable de validation d'un système informatique. Le nombre 7r est l'échelle de référence ultime en analyse numérique. Comme on connaît déjà beaucoup de décimales de 7r, on peut évaluer les nouvelles méthodes en les essayant sur le calcul des décimales de 7r : cela permet de les comparer sur une même échelle de mesure.

18

L'état de l'art

Mais la principale raison qui motive ces calculs de décimales de 7r, c'est la grande quantité de questions théoriques non résolues concernant 7r. Ces questions sont d'un intérêt mathématique majeur. Elles concernent un grand nombre de domaines: l'analyse, la théorie des nombres, la théorie des fonctions, la théorie de la complexité, l'étude d'algorithmes, les statistiques et d'autres domaines encore. Un spectre aussi large exerce naturellement une fascination exceptionnelle. Pendant plus de 4000 ans, 7r s'est révélé une source inépuisable de nouvelles découvertes et de surprises. Cela s'est encore vérifié ces dernières années, avec la découverte de nouvelles méthodes pour le calcul de 7r, comme l'algorithme du goutte à goutte (voir chapitre 6) et l'algorithme BBP (voir chapitre 10). Les données expérimentales constituent souvent un outil précieux de compréhension d'un problème théorique pour en trouver une démonstration, et les décimales de 7r fournissent une bonne base de données expérimentales. De plus, nous possédons aujourd'hui des logiciels de calcul formel et certains mathématiciens développent actuellement des méthodes automatiques de démonstrations théoriques sur ordinateur, à partir de vérifications expérimentales. En 2004, de tels programmes fonctionnent déjà sur les équations aux dérivées partielles, mais des mathématiciens travaillent à la mise au point de tels algorithmes dans les domaines évoqués ci-dessus. On peut penser qu'alors le stock de données accumulées sera utile. Tout nouveau record du monde a pour vocation d'être battu. Toute personne possédant les aptitudes et les moyens nécessaires pour le faire s'y appliquera. C'est vrai en sport comme dans les domaines scientifiques. L'étude mathématique de 7r ne se cantonne pas au développement de formules de théorèmes et d'algorithmes. Le calcul lui-même relève encore des mathématiques, tout au moins au-delà du premier million de décimales. Sans une connaissance approfondie de l'arithmétique et du comportement asymptotique des transformations de Fourier, il est impossible d'écrire un programme de calcul des décimales de 7r qui puisse soutenir la compétition. Quelqu'un a dit un jour qu'on peut transformer une personne normale en une enthousiaste de 7r, mais que l'inverse n'est pas possible. C'est assez vrai. L'enthousiasme et le plaisir qui transparaissent dans les textes écrits par les chasseurs de décimales de 7r suggèrent que 7r possède une vie propre qui s'exerce à travers ces gens. Les auteurs du présent ouvrage ont certainement attrapé le virus. Enfin, dernier aspect, et pas des moindres: 7r permet de donner une VIsibilité à des laboratoires de mathématiques qui autrement resteraient inconnus du grand public. De nouvelles découvertes sur 7r suscitent l'intérêt des non-mathématiciens. C'est un des rares sujets dont les résultats (pas les démonstrations!) soient accessibles à tous.

19

De nouveaux objectifs

5

De nouveaux objectifs

Depuis quelques années, à peu près depuis 1995, certains mathématiciens travaillant sur 7r ont réorienté leurs recherches. Au lieu de chercher à calculer le développement décimal de 7r depuis le début jusqu'à des ordres toujours plus élevés, ils se concentrent maintenant sur le calcul de chiffres individuels de développements de 7r dans des bases qui sont des puissances de 2, en pratique, le développement binaire ou le développement hexadécimal de 7r. Dans ces développements, ces chiffres individuels sont placés dans des positions beaucoup plus élevées que les derniers chiffres des développements calculés depuis le début. L'impulsion pour cette réorientation des recherches vint de la découverte inattendue d'une méthode qui permet de calculer directement des chiffres hexadécimaux individuels de 7r, sans avoir à calculer tous les chiffres qui précèdent dans le développement. Tout cela grâce à la formule

(1.12)

7r

=

1

~ 16n 00

(4+ 8n

2 1 1) 1 - 8n + 4 - 8n + 5 - 8n + 6

En octobre 1995, les inventeurs de cette formule (David Bailey, Peter Borwein et Simon Plouffe) firent l'admiration de tous lorsqu'ils la présentèrent avec ses conséquences (voir chapitre la). Jusqu'alors personne ne pensait qu'il soit possible un jour de calculer les chiffres d'un développement sans calculer les précédents. Un calcul de 7r se présentait jusque-là comme un arbre, dont on ne pensait pas pouvoir atteindre une feuille sans passer par les branches. Ce calcul direct d'un chiffre précis du développement hexadécimal de 7r, c'est un petit peu comme si l'on arrivait à enlever une aiguille placée au milieu d'une botte de foin sans faire bouger la paille située au-dessus de l'aiguille. Le facteur décisif est le terme 16 n au dénominateur de tous les termes de la série. Cette série est appelée la série BBP, initiales de ses découvreurs. En la publiant, ceux-ci firent la preuve de son efficacité en publiant également le la 000 milliardième chiffre du développement hexadécimal de 7r. La nouvelle idée semble avoir électrisé les mathématiciens travaillant sur 7r. Depuis la publication de la serie BBP, ils ont trouvé d'autres formules du même type, et même un algorithme général pour engendrer de nouvelles formules semblables. C'est grâce à l'une d'entre elles que l'on a pu calculer des chiffres du développement hexadécimal de 7r placé plus de 100 fois plus loin que le dernier chiffre calculé par Yasumasa Kanada. Le plus récent et le plus jeune détenteur de ce type de record est Colin Percival; né en 1981 et entré récemment à l'université, il suivit une démarche

20

L'état de l'art

différente de celle de Kanada : au lieu d'exécuter lui-même les calculs sur le super-ordinateur d'une université, grâce à à Internet il partagea les calculs sur 1700 ordinateurs dispersés à travers le monde. Il invita les propriétaires d'ordinateurs à l'aider dans son projet qu'il avait appelé PiHex ; il leur envoya par courriel son programme de calcul que les ordinateurs exécutèrent alors lorsqu'ils n'étaient pas utilisés à faire autre chose. Chaque ordinateur attaqua une sous-tâche différente et Percival assembla ensuite les résultats individuels. De cette façon après deux ans de calcul correspondant en réalité à 700 ans de calcul sur un unique ordinateur (à processeur P90) il atteignit le Il septembre 2000 un nouveau record mondial: il trouva le 250 billionième chiffre hexadécimal de 1[", un E. Parce que l'écriture binaire du chiffre hexadécimal E est 1110, Percival en déduisit que le 10 000 billionième chiffre du développement binaire de 1[" est un o. Le problème avec la série BBP et ses variantes, c'est qu'elles ne permettent d'obtenir que des chiffres des développements binaires ou hexadécimaux de 1[", et non des décimales. À ce jour, on ne dispose d'aucune méthode pour calculer une décimale de 1[" sans calculer aussi toutes les décimales qui la précèdent dans le développement. On pense qu'avec le temps, ce problème sera résolu. Un jour, quelqu'un mettra au point une formule «BBP » pour calculer des chiffres décimaux individuels de 1[". Nous attendons ce jour avec impatience.

2 Dans quelle mesure 7r est-il aléatoire? 1

Probabilités

Quel est la probabilité pour que la s-ième décimale de

7r

soit le chiffre z?

Au premier regard la réponse paraît assez simple. Comme la position 8 doit être occupée par l'un des dix chiffres décimaux 0, 1, ... ,9, la probabilité pour que ce soit l'un précis de ces dix chiffres est exactement 0.1. Un soi-disant subjectiviste des probabilités, i.e. un adepte de Thomas Bayes (1702-1761), dirait que la réponse dépend de ce que l'on connaît déjà de 7r puisque, selon ce philosophe, une « probabilité» mesure l'étendue de ce qu'on ne connaît pas. Si l'on connaît déjà la 8-ième décimale de 7r, alors la probabilité pour que ce soit z ou l'un des autres chiffres est 0 ou 1. En revanche,si on ne connaît rien de la s-ième décimale, on pourra alors dire en attendant de disposer de plus d'informations, la probabilité considérée est égale à 0.1. «Non» répondront les mathématiciens et les adeptes de théories philosophiques classiques. «La question est mal posée». En effet, les décimales de 7r ne sont pas des variables aléatoires; elles sont déterminées précisément. Par exemple, la deuxième décimale est un 4, et cela n'a aucun sens de se demander quelle serait la probabilité que ce soit un 5. La théorie des probabilités concerne des événements aléatoires, et non des assertions déterministes. Ainsi posée, la question du caractère aléatoire de 7r est incorrecte. Une manière mathématiquement correcte de formaliser cette idée est « Est-ce que 7r est normal? »

22

2

Dans quelle mesure 'if

7r

est-il aléatoire?

est-il normal?

Les mathématiciens disent qu'un nombre réel donné par son développement décimal est normal si, pour tout entier naturel non nul n, on retrouve toutes les séquences de n chiffres dans le développement avec une fréquence identique. Ainsi, par exemple, dans un nombre normal le chiffre 0 apparaît avec une fréquence de 1/10, et la séquence de chiffres 357 avec une fréquence de 1/1000. Un nombre normal n'est pas forcément «aléatoire », mais un nombre « aléatoire», c'est-à-dire qui aurait été formé avec des chiffres tirés aléatoirement avec équiprobabilité et indépendance des tirages serait presque sûrement normal. Si chacun des dix chiffres apparaît dans le développement décimal d'un nombre avec une fréquence identique, on dit que ce nombre est simplement normal. Le concept de normalité s'étend à des développements dans des bases autres que 10. Un nombre normal dans toutes les bases est dit absolument normal. La question de la normalité d'un nombre ne se pose que si son développement décimal n'est pas asymptotiquement constant. On sait que 7r est irrationnel; son développement décimal n'est donc pas asymptotiquement périodique (c'est-à-dire périodique au-delà d'un certain rang), et il est possible que 7r soit normal. Mais un tel résultat n'a pas encore été démontré: on ignore encore si 7r est normal ou non; on ignore même si cette propriété est démontrable ou indécidable. Si 7r n'était pas normal, alors certaines séquences de chiffres de même longueur surviendraient avec des fréquences différentes. Par exemple, le chiffre 7 pourrait apparaître plus fréquemment que le 3; ou bien peut-être qu'au-delà d'un certain point dans le développement la séquence 314159265 n'apparaîtrait plus. On trouve certes des intervalles contenant de telles irrégularités, mais, sur les très longues séquences dont on dispose aujourd'hui, on n'a encore pu observer aucune véritable irrégularité; cela ne veut pas dire que le développement complet (la suite infinie des décimales) n'en comporte pas. Un nombre normal devra toujours contenir une séquence de longueur un miLlion, formée uniquement de chiffres 5. Bien que le nombre de chiffres connus du développement décimal de 7r soit important, la fréquence des occurrences d'une telle séquence est si faible que l'on n'en a pas encore trouvé. Les séquences dont on a pu observer la fréquence dans la partie connue du développement sont d'une longueur très courte (moins de 10 chiffres de longueur), et l'on n'a donc aucune information concrète sur la fréquence des séquences longues. Dans une séquence aléatoire il est facile de trouver un intervalle qui semble non-aléatoire. Pour 7r, ce n'est pas le cas: comme les chiffres du développement décimal peuvent être calculés, 7r n'est pas un nombre aléatoire. Le fait que

7r

soit non seulement irrationnel mais aussi transcendant n'exclut

1["

23

est-il normal?

pas la possibilité de modèles réguliers survenant dans son développement décimal. Inversement, la présence éventuelle d'un modèle dans la formation du développement décimal ne signifierait pas que 1[" ne soit pas non-normal. Pour illustrer ce point, considérons le nombre artificiel 0, 123 ... 10111213 ... dont le développement est formé en écrivant les uns derrière les autres tous les entiers. La règle de formation des décimales est bien en évidence, et il s'agit d'un nombre normal. Cela fut démontré par Ivan Niven [86]. La question de la normalité de 1[" a été la source de nombreuses études statistiques. Les résultats de ces études sont tantôt instructifs, tantôt décevants, tantôt curieux. Nous allons ci-après en rendre compte. Plusieurs tests statistiques sont disponibles qui permettent d'évaluer jusqu'à quel point les chiffres d'une séquence extraite du développement décimal de 1[" sont répartis aléatoirement; les résultats de ces tests sont toujours exprimés à l'aide de probabilités. Si l'on utilise par exemple de tels tests sur une table de roulette, on ne peut pas garantir que la roulette ne soit pas biaisée, et de toute façon, lorsqu'on effectue un grand nombre de tirages, même une roulette parfaite produira des séquences inhabituelles. Tout cela peut être quantifié parfaitement en termes de probabilités.

Main

Forme

Nombre observé

N ombre théorique

Cinq chiffres différents

abcde

604976

604 800

Une paire

aabcd

1 007 151

1 008 000

Double paire

aabbc

216 520

216 000

Brelan

aaabc

144 375

144000

aaabb

17891

18000

Full (brelan

+ paire)

Carré

aaaab

8887

9000

Cinq chiffres identiques

aaaaa

200

200

Le test statistique le plus simple est le test du poker. Au jeu du poker, chaque joueur reçoit cinq cartes, que l'on appelle une main. Les mains possibles sont classées en sept types. Par exemple, une « paire» est constituée de deux cartes de même niveau, disons deux rois, et de trois cartes de niveaux différents qui ne soient pas des rois. Un « carré» est formé de quatre cartes de même niveau, et d'une cinquième carte, forcément de niveau différent. Lorsqu'on considère le développement décimal de 1[", les « mains» sont formées en considérant cinq chiffres consécutifs du développement décimal, l'ordre de ces cinq chiffres n'étant pas pris en compte. Pour un test, on considère des mains disjointes; ainsi, dans la séquence formée par les premiers dix millions de termes, on extrait deux millions de « mains». Le test du poker

24

Dans quelle mesure

1f

est-il aléatoire?

consiste à compter, les mains ayant des propriétés semblables à celles que l'on considère au poker: une paire, une double paire, etc. Dans le tableau ci-dessus, on donne les résultats obtenus avec les premiers dix millions de chiffres du développement décimal de 1f ([117]). La comparaison des fréquences observées avec les fréquences attendues ne montre rien d'anormal. Le test statistique du X2 donne 0,53 pour cette distribution, ce qui tout à fait compatible avec l'hypothèse de normalité de 1f. Ce serait seulement si l'on avait obtenu des valeurs inférieures à 0,05 ou supérieures à 0,95 que l'on aurait pu trouver cette séquence suspecte. Si l'on considère de plus petits intervalles, par exemple des intervalles formés de 500 000 décimales consécutives, qui sont suffisamment grands pour contenir encore quelques occurrences des mains les plus rares, l'image est différente pour ces mains, ce qui normal car, pour les faibles fréquences, les effectifs sont faibles et ne permettent donc pas de parler de « loi des grands nombres ». Voici par exemple, la distribution des mains pour l'intervalle des décimales entre la 3 000 OOl-ième et la 3 500 OOO-ième.

Main

Forme

Nombre observé

N ombre théorique

Cinq chiffres différents

abcde

30297

30240

Une paire

aabcd

50263

50400

Double paire

aabbc

10877

10 800

Brelan

aaabc

7 156

aaabb

927

900

Carré

aaaab

459

450

Cinq chiffres identiques

aaaaa

Full (brelan

+ paire)

21

7200

10

En ne considérant que cette séquence, et sans être trop regardant sur la loi des grands nombres, on pourrait être tenté de dire que le nombre de mains ayant cinq chiffres identiques est bien trop grand. Mais en refaisant le calcul sur la séquence suivante des 500 000 décimales, la fréquence observée des mains de cinq chiffres identiques est cette fois-ci plus faible que celle attendue, de sorte que quand on considère la réunion des deux séquences de 500 000 décimales, la fréquence observée est tout à fait en accord avec la fréquence attendue. Il y a aussi la possibilité d'une anomalie contraire, celle d'une fréquence observée coïncidant « trop» bien avec la fréquence attendue. On trouve une telle séquence de 500 000 décimales à partir de la position 4 250 001. Dans cette séquence la répartition des mains de poker ne diffère que de 0,5% des chiffres prévus.

Et si

1f

3

Et si

25

n'était pas normal? 7r

n'était pas normal?

Dans une des premières éditions de ses Jeux Mathématiques, Martin Gardner rapporte une conversation avec un certain « Dr. Matrice» [54] : Dr. Matrice emprunta mon crayon et écrivit rapidement les 32 premières décimales de 1f.

3.

~ IIY

~ YI1

14159~53589 9323846~43383279 o... 1

1

« Les mathématiciens considèrent le développement décimal de 1f comme une série aléatoire, mais pour un numérologiste ce développement est riche de modèles remarquables. » Il encadra les deux apparitions de 26. « Vous observerez que vingt-six est la première séquence de deux chiffres à se répéter». Il annota le développement pour faire apparaître la deuxième occurrence de 26 comme le centre d'une série bilatéralement symétrique. Pour cela, Dr Matrice inséra deux traits verticaux pour délimiter un intervalle de 18 chiffres, puis relia ensemble trois paires identiques de chiffres apparaissant symétriquement dans l'intervalle qu'il avait délimité (voir la figure ci-dessus). Il attira également l'attention sur les ensembles de cinq chiffres de part et d'autre du premier 26 : «La somme des cinq chiffres précédant le premier 26 vaut 20, qui est égal au nombre de décimales précédant le second 26. La somme du bloc de cinq chiffres suivant le premier 26 vaut 30, le nombre de décimales précédant le deuxième trait vertical. La somme de ces deux blocs de cinq chiffres vaut 50, la séquence de deux chiffres suivant le deuxième trait vertical. La séquence entre les deux barres commence à la treizième décimale, et 13 est la moitié de 26. La somme des six chiffres composant les trois paires 79, 32 et 38 vaut 32, la paire du milieu ainsi que le nombre total de décimales écrites. Lorsqu'on additionne le 46 et le 43 de chaque côté du second 26 on trouve 89, la séquence de deux chiffres précédant le premier chiffre vertical... »

4

Le phénomène 163

Après les fariboles du Dr Matrice, voici une autre curiosité ludique. Le nombre e7rV163 ne semble pas particulièrement remarquable. Son écriture ne fait appel à rien d'inhabituel : les nombres transcendants e et 1f et le nombre premier 163, plus une racine carrée et une exponentiation. N'importe

26

Dans quelle mesure

7f

est-il aléatoire?

qui penserait qu'il s'agit d'un nombre tout à fait quelconque. Et pourtant ...

(2.2)

e1Tv163 = 262 537412 640 768 743.9999999999992 ...

C'est presque un entier. La différence entre ce nombre et l'entier le plus proche est inférieure à 10- 12 . Ce «phénomène 163 » fut mis en lumière par le mathématicien écossais Alexandre Aitken (1895-1967) [15]. On n'est pas sûr de ce qui l'amena à cette découverte. Dans le monde mathématique Aitken est connu non seulement pour ses travaux académiques en analyse numérique (4 livres et 70 publications) mais aussi pour ses aptitudes légendaires en calcul mental. Il était capable de factoriser de tête de très grands nombres en facteurs premiers et de dire avec exactitude si un nombre qu'on lui soumettait était premier ou non. On l'entendait dire « Ce nombre sent comme un nombre premier». De la même manière sans doute, il pensa à cette propriété curieuse du nombre 163. y a-t-il d'autres nombres possédant une telle propriété? Voici une table donnant les premiers entiers n pour lesquels e1TVn est proche d'un entier.

n

6

2 197.990 .. .

17

422 150.997 .. .

18

614 551.992 .. .

22

2 508 951.998 .. .

25

6 635 623.999 3 .. .

37

199 148 647.999 97 .. .

43

884 736 743.999 7 .. .

58

24 591 257 751.999 999 8 ...

59

30 197 683 486.993 ...

67

147 197952 743.999 991 8 ...

74

545 518 122 089.999 1 ...

163

262 537412 640 768 743.999 999 999 999 2 ...

L'auteur de cette liste, Roy Williams, a offert un prix pour quiconque pourrait de manière convaincante soit démontrer que cette valeur numérique est simplement due au hasard, soit expliquer pourquoi il ne s'agit pas d'un accident. Une chose est certaine: à elle seule, la longueur de la liste laisse conjecturer que cette valeur numérique n'est pas due au hasard. La liste se prolonge en

27

Le phénomène 163

effet, avec beaucoup d'autres valeurs de n supérieures à 163 pour lesquelles le développement décimal de e1fVn commence après la virgule décimale par plusieurs chiffres 9. Par exemple, pour n = 232 et n = 4 075, on trouve 5 chiffres 9, pour n E {719, 1 169,5 773}, on en trouve 4, et pour n = 1 467, on en trouve 8. Ces données expérimentales laissent soupçonner qu'il y a là un authentique phénomène à étudier, mais elles ne nous donnent aucune piste pour une démonstration. Les débuts de preuves mathématiques sont si compliqués que, même avec un haut niveau mathématique, les perspectives de gagner le prix semblent extrêmement minces: le phénomène défie les simples explications. Les mathématiciens qui s'y sont attaqués l'ont fait en utilisant la théorie des équations modulaires, que seuls quelques spécialistes maîtrisent parfaitement[61]. Pour n E {43, 67, 163}, on a une explication liée à la fonction j définie par

(2.3)

j(n)

1

avec -

q

= ~ + 744 + 196884q + 21493760q2 + 864299970q3 + ... q

= _e1fVn . On montre grâce à une interprétation différente de

j que

pour ces valeurs de n, j(n) est un entier et même un cube parfait. On a j(43) = -960 3 ,j(67) = -5280 3 et j(163) = -640320 3 . Cela permet d'expliquer pourquoi pour ces valeurs de n, le nombre e1fVn est proche d'un entier. On voit en effet sur le développement de j qu'il n'en diffère que par la somme de la série 196884q+21493760q2 + 864299970q3 + ... qui est un nombre petit. Avec cette explication, on peut faire encore mieux en combinant le développement en série de j et le fait que j(n) soit le cube d'un entier pour ces valeurs de n. On obtient

(2.4)

~e1fVT63 -

744

= 640 319.999 999 999 999 999 999 999 999 3 ...

Il Y a quelques autres valeurs de n pour lesquelles un développement en série peut expliquer la valeur numérique de e1fVn , mais cela ne donne pas d'explication simple de la fonction j elle-même. Le mathématicien indien S. Ramanujan (1887-1920) , dont nous parlerons plus en détail dans le chapitre 8 découvrit de telles séries. Il était malheureusement adepte des explications ultra-concises, et son mémoire [96] ne fait pas exception. Pour autant

28

Dans quelle mesure

Ir

est-il aléatoire?

qu'on puisse reconstituer sa démarche intellectuelle, il suivit une méthode semi-heuristique consistant à « peigner» les équations modulaires de degrés inférieurs à quelques centaines. Ce faisant, il tomba sur les degrés 22, 37 et 58, dont certaines combinaisons conduisaient à des entiers. Il trouva par exemple l'égalité

qui permet d'expliquer le cas de n

= 37.

À partir de ces valeurs de n, on peut aussi expliquer celles qui s'en déduisent par une multiplication par un carré, comme 232 = 58x2 2 , ou 1467 = 163x32 . Mais il reste encore des cas qui résistent aux explications, comme e 7fvTI9 qui diffère de moins de 0.000 013 d'un entier.

L'hypothèse selon laquelle l'intervention de variables complexes conduirait forcément à un résultat complexe est erronée, ainsi que nous l'avons vu. Cela est confirmé par Donald E. Knuth de l'université de Stanford, en Californie. Nous aurons d'autres occasions de mentionner ce mathématicien qui est l'auteur d'un célèbre traité, The Art of Computer Programming, sans doute l'ouvrage d'informatique le plus cité. Dans l'introduction du deuxième volume, Knuth raconte l'histoire de son super-générateur de nombres aléatoires dont il pensait qu'il engendrerait les plus aléatoires de tous les nombres aléatoires. À cet effet Knuth écrivit un programme qui était conçu pour être totalement aléatoire. Par exemple, à chaque exécution, il commençait à un endroit aléatoire du programme et pour chaque nombre aléatoire il exécutait un nombre aléatoire de boucles. Knuth coda aussi son programme d'une manière si compliquée que personne ne pourrait le comprendre. Il commençait avec une valeur initiale qui, naturellement, était choisie au hasard. Il pensait que son programme contenait tant de choix aléatoires qu'il produirait des nombres incroyablement aléatoires.

Mais qu'arriva-t-il? Après quelques termes, la suite de nombres engendrée par le programme aboutissait presque aussitôt sur le nombre à 10 chiffres 6 065 038 420, puis devenait périodique de période 27. Quand il changeait la valeur initiale, la période passait à 3 178, ce qui, pour un générateur de nombres aléatoires est tout aussi lamentable. La conclusion qu'il en tira est que l'on ne devrait jamais engendrer des nombres aléatoires avec une méthode aléatoire. Cela s'applique également aux recherches sur Ir. Aussi nous faut-il préciser que le phénomène 163 n'est pas accidentel mais constitue le point de départ de l'une des méthodes les plus rapides pour le calcul des décimales de Ir. En 1989, elle inspira les frères Chudnovsky lorsqu'ils mirent au point une série

29

D'autres résultats statistiques

qui leur permit de franchir pour la première fois la barrière du calcul d'un milliard de décimales de 7r.

5

D'autres résultats statistiques

Naturellement les décimales de 7r ont été calculées sur des ordinateurs en utilisant de nombreuses méthodes différentes. Par exemple, quand Yasumasa Kanada annonça en octobre 1999 son calcul de 206.1 milliards de décimales, il publia la répartition des 200 premiers milliards de décimales. La voici. Chiffre

Nombre d'occurrences

a

20 000 030 841

1

19 999 914 711

2

20 000 136 978

3

20 000 069 393

4

19 999 921 691

5

19 999 917 053

6

19 999 881 515

7

19 999 967 594

8

20 000 291 044

9

19 999 869 180

Total

200 000 000 000

Comme on le voit sur cette liste, la distribution des chiffres est quasiment uniforme. Le chiffre qui s'éloigne le plus est le 8, mais même pour lui, la déviation par rapport à la moyenne n'est que de 0.000 01 %. Kanada chercha aussi dans sa séquence record des sous-séquences remarquables. Il rapporte par exemple que la séquence 01234567891 apparaît cinq fois dans la séquence des 206.1 premiers milliards de décimales de 7r, alors qu'on s'attendrait à la rencontrer seulement deux fois. Une autre singularité est le fait que la séquence 543 210 987 654 n'apparaît pour la première fois que relativement tard dans la séquence considérée, en position 197 954 994 289, bien que dans l'hypothèse d'un développement aléatoire sa probabilité d'apparition dans les 69 premiers milliards soit de 0.5. Supposons que les chiffres du développement décimal soient tirés aléatoirement avec équiprobabilité des dix chiffres, et indépendance de tirages; notons w la probabilité pour qu'une séquence donnée de k chiffres n'apparaisse pas dans une séquence de longueur n. Alors w et n sont reliés par les deux formules lnw

(2.5)

n

= In(l _ lO-k)

30

Dans quelle mesure

7r

est-il aléatoire?

(2.6) Selon la dernière formule, la probabilité du fait confirmée par Kanada est de 0.13, ce qui ne susciterait la suspicion d'aucun statisticien. Si l'on partage le développement décimal de 7r en blocs de dix chiffres consécutifs, et toujours sous l'hypothèse du caractère aléatoire de ce développement, quelle est la probabilité pour qu'un bloc soit constitué de dix chiffres différents? Un tel bloc pourrait par exemple être la séquence 0123456789. Il y a 1010 séquences possibles de dix chiffres, et parmi celles-ci, il y en a 1O! qui soient formées de dix chiffres différents. La probabilité cherchée vaut donc 10!/10 1O = 1/2755 ... ~ 0.000 36. Autrement dit, en moyenne, une séquence de 27 550 décimales consécutives de 7r contiendra en moyenne une séquence de longueur 10 constituée des dix chiffres 0,1, ... ,9. En réalité, la première de ces séquences de dix chiffres différents apparaît très tôt, dès le septième bloc de dix décimales. Voici les premiers blocs: 3. 1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 5923078164

6

7r

et les intuitionnistes

Ainsi que l'a indiqué Jonathan Borwein [29], l'exploit de calcul de Kanada a une grande importance historique. Au début du XX e siècle le mathématicien hollandais L. E. J. Brouwer développa une théorie qui porte le nom d'intuitionnisme. Brouwer remettait en cause le principe du tiers exclu qui avait été scrupuleusement respecté par tous les mathématiciens depuis l'époque d'Aristote : si P est une assertion bien formée, ou bien P est vraie, ou bien la négation de P est vraie, et il n'y a aucune troisième possibilité. Brouwer remit en cause ce principe, en montrant qu'il n'est pas toujours applicable. À l'appui de sa thèse, il demanda s'il est vrai ou faux que la séquence 123456789 apparaît quelque part dans le développement décimal de 7r. Étant donné l'état des connaissances sur 7r à son époque, il pouvait penser que l'on ne pourrait jamais répondre à cette question, car pour le

Représentation en fractions continues

31

faire, il faudrait «probablement» connaître 6,9 milliards de décimales de 7f, tandis qu'à cette époque, on n'en connaissait que 707. Selon Brouwer, si l'on ne peut pas dire si cette assertion est vraie ou fausse, c'est parce que le principe du tiers exclu ne s'applique pas à cette assertion. Grâce à Kanada, on connaît aujourd'hui la réponse à cette question, et aussi à bien d'autres que Brouwer et ses disciples avaient utilisées pour étayer leur théorie. Voici l'une d'elles. Une des implications du principe du tiers exclu est que la démonstration de l'impossibilité d'une proposition d'impossibilité montre la proposition ellemême. La réfutation de Brouwer procède ainsi. Sous la suite des décimales de 7f, écrivons la fraction décimale p = 0.33333 ... , que l'on termine dès qu'apparaît dans le développement décimal de 7f la séquence 0123456789. Si le 9 de cette séquence est la k-ième décimale, alors p = (10 k - 1)/(3 X 10 k ). Maintenant supposons que p soit irrationnel. Alors, p ne peut pas être égal à (lOk -1)/(3 X 10 k ), car dans ce cas, p serait rationnel. Par suite, la séquence considérée ne peut pas apparaître dans le développement décimal de 7f. Mais alors, p = 1/3, ce qui est encore une fraction, contrairement à l'hypothèse. Ainsi, l'hypothèse selon laquelle p est irrationnel conduit à une contradiction. En appliquant le principe du tiers exclu, cela signifie que p est rationnel, donc qu'il existe deux nombres entiers r et s tels que p = r / s. Mais on ne peut préciser ces deux entiers qu'en indiquant la position de la séquence 0123456789 dans le développement décimal de 7f, ou en démontrant qu'elle ne se trouve pas dans ce développement. Selon Brouwer, cet exemple montre que le principe du tiers exclu ne s'applique pas toujours. Maintenant, nous pouvons préciser ces entiers r et s, ce qui dans l'esprit de Brouwer ne se produirait jamais. Cela permet-il de réfuter la théorie de Brouwer? Non, il suffit de reprendre l'argument en remplaçant la séquence 0123456789 par une séquence plus longue, par exemple la séquence de 100 chiffres obtenue en accolant bout à bout dix fois de suite la séquence 0123456789. Non seulement l'intuitionnisme n'est pas réfuté mais, d'une certaine façon, on peut dire que les mathématiques expérimentales mettent en IJuvre une pensée intuitionniste, ce qui est le cas de beaucoup de travaux contemporains sur 7f.

7

Représentation en fractions continues

La séquence connue du développement décimal de 7f ne fournit aucun indice suggérant que ce développement décimal ne soit pas aléatoire. Y a-t-il alors d'autres représentations de 7f qui soient plus instructives? Cette question est légitime, dans la mesure ou toute nouvelle représentation de 7f, par exemple son écriture hexadécimale, étant obtenue à partir d'un arbre de calculs assez

32

Dans quelle mesure

1r

est-il aléatoire?

différent, il est vraisemblable qu'une nouvelle représentation ne ressemble pas aux précédentes. Une approche prometteuse est la fraction continue simple de 1r 1 . Comme on l'a déjà indiqué dans le premier chapitre, le nombre e présente un comportement assez différent selon qu'on considère son écriture décimale ou son développement en fraction continue. On obtient respectivement e = 2.71828 18284 590 ... , et 1 1 1 1 1 1 1 1 1 1 1 1 e=2+- - - - - - - - - - - 1+2+1+1+4+1+1+6+1+1+8+1+ ...

(2.7)

La représentation décimale de e ne possède aucune régularité, tandis que sa représentation en fraction continue est très régulière : la formule est faite de blocs de trois quotients successifs dont les dénominateurs sont de la forme 1 nI, où n est un entier pair non nul. Le nombre 1r possède des caractéristiques fort différentes : ni son développement décimal ni son développement en fraction continue ne semblent obéir à une quelconque règle de régularité. 1r

111111111111 - - -- - - - - - - 7 + 15 + 1 + 292 1 + 1 + 1 + 2 + 1 + 3 + 1 + 14 + ...

= 3+-

Peut-être peut-on en conclure que

1r

est encore plus aléatoire que e?

En 1985, William R. Gosper calcula 17 millions de termes du développement en fraction continue simple de lr, ce qui permet de faire des statistiques sur les différents dénominateurs. Voici quelques résultats pour les 8192 premiers termes éléments (3,7,15,1,292, etc.) : Moyenne des 2 048 premiers éléments

27.5

Moyenne des 2 048 suivants

15.3

Moyenne des 2 048 suivants

8.2

Moyenne des 2 048 suivants

10.4

Que peut-on en conclure? La valeur moyenne des 2 048 premiers termes semble inhabituelle. Elle est presque deux fois plus grande que la valeur moyenne des blocs suivants de 2 048 termes. Cela reste vrai lorsqu'on considère des blocs de longueur différente : la moyenne des termes du premier bloc est toujours supérieure à celle des blocs suivants. IOn précisera la notion de fraction continue au chapitre 4.

33

Représentation en fractions continues

Quand on examine les données plus en détail, on voit que cette différence entre les moyennes vient du 431 e dénominateur, qui est anormalement grand, puisqu'il vaut 20 776. Si l'on retire cet élément, la moyenne du premier bloc redevient proche de celle des autres blocs. Pour l'instant, ce terme particulier en position 431 est le seul élément remarquable que l'on ait pu tirer du développement en fraction continu de 7r : une petite irrégularité dans l'irrégularité des termes. Il n'y a heureusement pas que le développement en fraction continue simple de 7r : il existe d'autres développements en fractions continues, et parmi eux, certains semblent présenter quelque régularité. En voici un, trouvé par L. J. Lange en 1999.

(2.8)

Ici, les fractions sont les termes de la suite

(2n 6

1?

La séquence des décimales de 7r déjà connues a passé avec succès tous les tests de caractère aléatoire qu'on lui a fait subir. C'est pourquoi on pourrait se servir de cette séquence comme d'un générateur de nombres aléatoires, à condition bien sûr de ne pas le révéler! Une société de loterie pourrait tout simplement tirer chaque semaine les 7 décimales suivantes de 7r et former ainsi le numéro gagnant de la semaine. y a-t-il une lueur d'espoir pour que l'on trouve quelque chose de remarquable dans le développement décimal de 7r? Peut-être. Nous avons déjà mentionné plus haut les frères Chudnovsky, qui ont beaucoup travaillé sur 7r et qu'il est difficile de soupçonner de vouloir attirer sur eux l'attention des médias par des déclarations fantaisistes. En 1992, ils déclarèrent à un journaliste être sur une piste, «pas encore statistiquement significative, mais presque». Ils déclarèrent avoir besoin de beaucoup plus de milliards de décimales pour confirmer ou infirmer leur intuition. Bien qu'ils n'aient pas donné tous les détails, on pense qu'ils ont cherché une propriété statistique invisible pour les tests usuels. Il s'agirait de phénomènes d'« ondes» dans le développement décimal. Par exemple, le premier, le troisième et le cinquième milliard de décimales auraient un déficit de l'un des chiffres, tandis que les deuxième, quatrième et sixième présenteraient un excédent de ce même chiffre.

Depuis avril 1999, Kanada a mis à la disposition des frères Chudnovsky la séquence de décimales qu'il a calculées, et l'on attend maintenant que ces derniers publient les résultats de leur étude.

3 Les raccourc'ts vers

7r

Indiscutablement la voie la plus facile pour approcher K est de se reporter au chapitre 17 de ce livre où l'on trouve une liste de quelque 5 000 décimales, tandis qu'on trouve plus de 400 millions de décimales sur la partie du site Vuibert consacrée au nombre K. Une autre façon d'obtenir facilement un grand nombre de décimales de K est d'utiliser un logiciel informatique de calcul formel, comme Mathematica, Maple ou un programme spécial de calcul des décimales de K, comme ceux que l'on trouve sur Internet. Dans ce chapitre, on va se concentrer sur des approches de l'exercice d'une certaine initiative.

1

Des approches « obscures» de

K

qui réclament

7r

Si la superficie A et le diamètre d d'un disque sont connus, alors K est égal à 4A/d 2 . C'est précisément l'approche qui sous-tend le curieux programme en C créé par Brian Westley. Il calcule K avec 3 décimales. #define _ OO>OO?O:--OO,--F; int F,OO; mainO{F_OOO ;printf("%1.3f\n" ,-4.*F/OO/OO) ;}F_OOO {

- - - - - - - - - - - - - - - - - - - -- --

}

36

Les raccourcis vers

1f

Ici, le « disque» a une superficie de 201 (mesurée en utilisant les caractères _ et - et un diamètre de 16 (mesuré grâce aux lignes formées par ces caractères), de sorte que la valeur approchée de 1f que l'on obtient est de 3.141. Pour obtenir plus de décimales, il suffit de faire grossir de cercle, d'un facteur 10 pour chaque nouvelle décimale. Le programme proposé ne ressemble pas du tout à un programme en C ordinaire, mais il respecte néanmoins la norme ANSI de programmation en C. Avec ce programme, Westley obtint un prix au « International Obfuscated C Code Contest» (IOCCC) en 1988. Depuis 1984, cette compétition se déroule sur Internet chaque année. Le gagnant est la personne qui crée le programme en C le plus incompréhensible et le plus créatif, mais qui est néanmoins exécutable. Les outils fondamentaux employés ici sont la syntaxe concise du C, et surtout le pré-processeur C. D'habitude, les résultats sont artificiels mais également artistiques. Ce sont toutefois invariablement des exemples illustrant comment on ne devrait jamais écrire un programme. Voici un autre exemple de programme. cha _3141592654[314 ], __ 3141[3141];_314159[31415],_3141[31415];main(){register char* _3_141,*_3_1415, *_3 __ 1415; register int _314,_31415, __ 31415,*_31, _3_14159, __ 3_1415;*_3141592654= __ 31415=2,_3141592654[0] [_3141592654 -1]=1 [ __ 3141]=5; __ 3_1415=1;do{_3_14159=_314=0, __ 31415+ +;for( _31415 =0;_31415«3,14-4)* __ 31415;_31415++)_31415[_3141]=_314159[_31415]= 1;_3141[*_314159=_3_14159]=_314;_3_141=_3141592654+ __ 3_1415;_3_1415= __ 3_1415 + __ 3141;for (_31415 = 31413 1415 ; _31415;_31415-,_3_141 ++, _3_1415++){_314 += 314«2 . 314«=1' 314+= *_3=1415;_31 ~_314159~=314; if(!(*_31+1) )* _31 =_314 / __ 31415,_314 [_3141]=_314 % _3 __ 1415=_3_141 __ 31415 ;* ( )+= *_3_1415 = *_31;while(* 3 1415 >= 31415/3141 ) * _3 __ 1415+= 10,(*--_3 __ 1415 )++;_314=_314 [_3141]; if ( ! _3_14159 && * _3_1415)_3_14159 =1, __ 3_1415 = 3141-_31415;}if( _314+( __ 31415 »1»= __ 31415 ) while ( ++ * _3_141==3141/314 )*_3_141--=0 ;}while(_3_14159 ) ; { char * __ 3_14= "3.1415"; write«3,1), (--* __ 3_14, __ 3_14 ),(_3_14159 ++,++_3_14159))+ 3.1415926; } for ( _31415 = 1; _31415+oo

t n

Aire (quart de cercle) Aire( quart de carré)

4t n

-

~

7r

4

7r

Le résultat est un élégant algorithme d'approximation de 7r. Il suffit de simuler un grand nombre de lancers (le plus grand nombre possible) et de vérifier à chaque fois si la fléchette est dans le disque. Cette vérification est particulièrement simple: si x et y sont les coordonnées du point d'atterrissage (0 :( x, y :( 1), alors le point sera dans le disque si et seulement si sa distance à l'origine est inférieure à 1, c'est-à-dire si et seulement si x 2 + y2 :( 1. Dans le programme en C++ suivant, les coordonnées aléatoires x et y sont engendrées en utilisant la fonction rand du langage C++, qui est la fonction standard de génération de nombres pseudo-aléatoires. Cette fonction fournit des nombres pseudo-aléatoires équirépartis dans l'intervalle [0, RAND _ MAX], où RAND_MAX est un nombre dépendant du système sur lequel est implanté le compilateur C++. Il convient donc de diviser par RAND_MAX le résultat fourni par la fonction rand pour obtenir un nombre dans l'intervalle [0,1]. Le générateur aléatoire de la fonction rand est initialisé par la fonction standard srand 0 qui dépend du temps, et fournit donc un nombre initial qui n'est pas constant.

Ir

et l'aléatoire: méthodes de Monte-Carlo

41

**************************************************************** Il Algorithme des fléchettes pour approcher de pi. **************************************************************** #include #include #include #include



int main(void)

{

long k, n, hits; const double factor while (1) {

cout « "Nombre de lancers (0 pour arrêter): "; cin » n; if ( n = 0)

1* 1* 1* 1*

next prelim. digit previous prelim. digit len: One more than R+W array pointer

1* Init a[] with 2's

84

Les algorithmes du goutte à goutte {

q

=

0;

1* Compensate for the very first digit *1

for(i=len; --i >= 1; {

}

q += 10L * a[i]; a[i] = q % (i+i+l); q 1= (i+i+l); q *= i',

q += 10L * a[O]; a[O] = q % 10; q 1= 10; i f (q == 9)

++nines; else

{

}

}

}

i f (p >= 0)

1* q = carry + 10*a[i] 1* a[i] := q % (2i+l) 1* carry := floor(q,2i+l)*i

*1 *1 *1

first digit carry + 10 * a[O] q a[O] = q mod 10 q : next prelim digit

*1 *1 *1 *1

1* 1* 1* 1*

9: increment no of 9's 1* q 1* q != 9: print prelim. digits

printfC"%Olld", p + q/l0); 1* p : prev. prel. digit if (digits < nines) 1* adjust digits to print nines = digits; digits -= (nines+l); while (--nines >= 0) 1* print 9's or O's printf(q == 10? "0" "9") ; nines = O· P = (q =='10 ? 0 : q); 1* set previous prelim. digit

*1 *1 *1 *1

free(a); return;

À la fin de leur article ([95]) cité ci-dessus, Rabinowitz et Wagon proposèrent un programme Pascal qui n'avait manifestement pas été rédigé par les auteurs eux-mêmes, mais certainement par un de leurs étudiants, auquel d'ailleurs ils exprimaient leur gratitude. Ce programme a été retapé et essayé par plusieurs lecteurs. Ceux-ci ont rencontré divers problèmes; par exemple, si l'on utilise un compilateur Pascal 16 bits, le programme s'arrêtera pour des entiers n > 262, avec un message de débordement de type. Comme nous l'avons remarqué précédemment, leur programme, pour n = 1 et n = 32, fournit une décimale incorrecte, due au fait que le tableau stockant ces décimales est de longueur trop petite, ou, dans de nombreux cas, il retourne moins de décimales que ce qui est prévu, car la variable nines n'est pas remise à 0 en fin de programme. Notre programme ci-dessus tente d'éviter ces faiblesses.

3

Une variante plus rapide

On peut apporter à cet algorithme deux améliorations essentielles qUI le rendent nettement plus court et beaucoup plus rapide. Tout d'abord, au lieu de calculer 'if, on peut calculer lOOO'if, en employant la série

85

Une variante plus rapide

(6.4)

10007r

123

= 2000 + 3(2000 + 5(2000 + 7(2000 + ... )))

La conversion n'est ainsi pas effectuée en base 10 mais en base 10 000, si bien qu'à chaque passage, le programme donnera quatre décimales au lieu d'une seule. Cette astuce aura non seulement pour effet, de rendre le programme quatre fois plus rapide, mais aussi un effet plus important encore sur la «complication » mentionnée plus haut. Dans cette version plus rapide, on attend seulement d'obtenir un seul groupe de 4 chiffres, au lieu d'en avoir un nombre variable. Cela est suffisant pour obtenir environ les 50 000 premières décimales de 7r, car, jusque-là, il n'est pas nécessaire de stocker plus d'une seule chaîne de 4 chiffres dans le tampon de réserve. C'est nécessaire uniquement lorsque le développement décimal contient une séquence de 4 zéros consécutifs dont le premier est dans une position divisible par 4. Cela n'arrive pour la première fois qu'à partir de la 54 936 small e décimale de 7r. La seconde amélioration est plutôt de type scolaire et, bien évidemment, elle a été omise dans la formulation originale de l'algorithme du goutte à goutte. En fait, en changeant de base d'écriture, après le calcul d'une «décimale », on peut réduire la longueur du reste devant être traité du nombre de bits du rang de ladite décimale. Ainsi, après chaque calcul d'un bloc formé de 4 décimales, la longueur du domaine de f [J peut être réduite par l10· 4/3 + 1J = 14 places. Cette amélioration accélère encore d'un facteur 2le programme. Voici un programme C pour cette variante. C'est une version améliorée du miniprogramme montré au chapitre 3. ************************************************************************* * Programme goutte à goutte pour pi pour NDIGITS décimales * 4 chiifres par boucle * Version étendue * de Dik T. Winter et Achim Flammenkamp. ************************************************************************* #include #include #define NDIGITS 15000 #define LEN (NDIGITS/4+1)*14 long long long long long long long long

a[LEN] ; b; c = LEN; d; e = 0; f = 10000; g; h = 0;

/* max. digits to compute /* nec. array length /* /* /* /* /* /* /* /*

*/ */

array of 4 digit-decimals*/ nominator prey. base */ index */ accumulator and carry */ save prey. 4 digits */ new base, 4 dec. digits */ denom prey. base */ init switch */

86

Les algorithmes du goutte à goutte

int main(void)

{

{

for ( ; --b > 0; {

}

h d }

}

/* outer loop:4 digits/loop*/

for ( ; (b=c-=14) > 0;

d *= b; i f (h == 0) d += 2000 * f; else d += a[b] * f; g=b+b-1 ; a[b] = d % g; d /= g;

/* inner loop: radix conv

*/

/* ace *= nom. prev base

*/

/* first outer loop

*/

/* non-first outer loop /* denom prev. base

*/ */

/* save carry

*/

printf ("%041d", e+d/f); /* print prev 4 digits */ e = d % f; /* save current 4 digits */ /* assure a small enough d */

return 0;

Lorqu'on fixe NDIGITS = 15 000, ce programme calcule exactement 15 000 décimales de 7r. Il Y a aucune raison de le voir s'arrêter à cette limite à moins que l'on ne se soucie de la portabilité du programme et de sa conformité à la norme ANSI C. Comme la plupart des compilateurs C ne tiennent pas compte des éventuels débordements lors de l'évaluation d'expressions d'entiers signés tant qu'il y a assez d'espace de travail dans le tableau défini, ce programme peut être modifié afin de calculer deux fois plus de décimales de 7r (en utilisant la définition @NDIGITS 32500). Il Y a seulement 40 ans, ce nombre de décimales constituait un record mondial. Néanmoins, aussi grande que soit la longueur du tableau défini dans le programme, et même en utilisant cette dernière variante de l'algorithme du goutte à goutte, celle qui produit des paquets de 4 décimales exactes et qui n'utilise qu'une place dans la mémoire tampon, cet algorithme ne donnera jamais plus de 54 932 décimales exactes. Et cela n'est réalisable qu'en retirant au moins une de ces conditions de limitation; la plus facile à retirer est la première.

4

Algorithme du goutte à goutte pour e

L'algorithme du goutte à goutte n'est bien entendu pas limité au calcul de 7r.

Soit e le nombre transcendant e = 2.7182 ... Son développement en série, analogue à celui de 7r défini ci-dessus (6.1) est défini par

(6.5)

e

111

= 1 + -(1 + -(1 + -(1 + ... ))) 1

2

3

Algorithme du goutte à goutte pour e

87

Ici, comme dans la série définissant 7r, on utilise des bases différentes, mais cette fois tous les numérateurs des fractions intervenant sont égaux à 1. Cela signifie qu'aucune multiplication n'est nécessaire pour le calcul de la retenue. Mais plus important encore est le fait que la série (6.5) définissant e est unique, si bien que la complication qui existe avec 7r n'existe pas ici. Un programme de goutte à goutte pour les décimales de e est donc bien plus simple. Voici un programme long de 138 caractères pour le calcul de 15 000 décimales de e, programme écrit dans l'esprit du mini-programme de 7r, du chapitre 3 : /* note: N=15000, LEN=87700 >= 1.4*N*log10(N), 84700=LEN-N/5 */ a[87700],b,c=87700,d,e=le4,f=le5,h; mainO {fore ;b=c--, b>84700 ;h=printf ("%05d" ,e+d/f) ,e=d%=f) for(;--b;d+=f*(h?a[b] :e),a[b]=d%b,d/=b);}

Nous avions alors promis de donner l'explication du fonctionnement du programme de Lievaart : en fait, lui aussi, repose sur l'algorithme du goutte à goutte pour e.

7 Gauss et

7r

Une des méthodes les plus rapides pour calculer 7r, peut-être même la plus rapide, est vieille d'environ 200 ans. Elle fut découverte aux alentours de 1800 par le «prince des mathématiciens» Carl Friedrich Gauss (1777-1855). Elle fut ensuite oubliée, avant d'être exhumée 170 ans plus tard par deux chercheurs, Eugene Salamin [100J et Richard Brent [37] qui la redécouvrirent

90

Gauss et

7r

indépendamment et simultanément, pour en faire la base des calculs superrapides de 7r. La méthode de calcul de Gauss a depuis servi de point de départ à bien d'autres méthodes de calcul, comme le montre la variété de noms sous lesquels on l'invoque dans la littérature mathématique: c'est ainsi qu'on parle entre autres de la méthode itérative de Brent et Salamin, ou de la méthode de Gauss-Legendre. Dans ce livre, nous parlerons de la méthode de la moyenne arithmético-géométrique de Gauss (MAG en abrégé), parce que cet algorithme porte indubitablement l'empreinte de Gauss, et que sa marque distinctive est de reposer sur la moyenne arithmético-géométrique.

1

La formule MAG pour

'if

La forme originale de cette formule de Gauss qui joua un rôle si important dans l'étude de 7r est donnée à la fin de ce chapitre. La voici, écrite sous forme moderne (Gauss, 1809, Salamin et Brent, 1976) :

(7.1)

L'élément essentiel de cette formule est la fonction MAG : (a, b) f------* MAG(a, b), qui donne la moyenne arithmético-géométrique de deux nombres, c'est-à-dire une combinaison des moyennes arithmétiques et géométriques. Les nombres Ck qui interviennent aussi dans la formule sont liés à cette fonction MAG. Dans la vie courante, nous rencontrons souvent différentes moyennes. La moyenne arithmétique (a + b) /2 de deux nombres a et b est un outil courant qui est employé, par exemple, pour établir les moyennes des étudiants après des épreuves. La moyenne géométrique y'(ib de deux nombres a et b permet de calculer la moyenne de deux quantités ou plus, lorsque celles-ci sont reliées par des multiplications, par exemple deux taux d'intérêts. Dans les deux cas, le mot «moyenne» désigne un nombre situé « entre» les deux valeurs initiales. MAG (a, b) représente aussi une moyenne des deux nombres a et b. Cependant, cette moyenne ne peut pas être calculée d'un seul coup; on l'obtient au terme d'une procédure itérative, qui nécessite un nombre infini d'étapes, produisant chacune un nombre de plus en plus près du résultat final. Nous appellerons algorithme MAG cette procédure itérative, la fonction MAG étant

La formule MAG pour

91

7r

la fonction qui à deux nombres a et b associe la limite des suites construites avec l'algorithme MAG.

Algorithme MAG Ini tialisation

ao:= a bo := b

Itération (k

= 0, 1,2 ... )

ak+l :=

ak

+ bk 2

bk+1 := Vakbk

--7

--7

MAG(a, b)

MAG(a, b)

Les deux suites (ak) et (b k ) convergent vers une limite commune, MAG(a,b). On voit que ak+l s'obtient en prenant la moyenne arithmétique des deux termes précédents ak et bk , tandis que bk+l s'obtient en prenant leur moyenne géométrique. C'est à 14 ans que Gauss s'intéressa pour la première fois à la moyenne arithmético-géométrique; il obtint confirmation de son comportement en calculant à la main les premiers termes de la suite, pour différentes valeurs initiales. On a gardé la trace de quatre exemples, dont les valeurs initiales sont a = V2 et b = l. Voici les quatre premiers termes de la suite associée à ces valeurs initiales [56, III, p. 364]1

Moyenne arithmétique

Moyenne géométrique

= 1.414213562373095048802 al = l.207106781186547524401 a2 = 1.198156948094634295559 a3 = 1.198140234793877209083 a4 = 1.198140234735592207441

b = 1.000000000000000000000

0

bl

0

a

= 1.189207115002721066717 b2 = 1.198123521493120122607 b3 = 1.198140234677307205798 b4 = 1.198140234735592207439

Chiffres corrects

4 9 19

1 Cette suite de colonnes montre que Gauss, aussi génial fut-il, ne rechignait pas à « retrousser ses manches» pour se lancer dans des caluls longs et laborieux. Jusqu'à aujourd'hui, les mathématiciens l'admirent aussi pour cela.

92

Gauss et

1r

Au cours du processus itératif, les nombres ak et bk se rapprochent de plus en plus, les ak en décroissant, les bk en croissant (Si, au départ, on avait pris une valeur de a inférieure à b, les deux suites se seraient d'abord croisées avant de converger l'une vers l'autre avec la monotonie indiquée). La valeur vers laquelle les deux suites convergent, i.e. leur limite, est appelée la moyenne arithmético-géométrique de a et b; on la note MAG (a, b). Dans le cas de a = V2 et de b = 1, la valeur de la limite est clairement 1,19814 ... La moyenne arithmético-géométrique de deux nombres est toujours comprise entre leur moyenne arithmétique et leur moyenne géométrique.

t

moyenne arithmétique 1 x moyenne arithmético-géométrique MAG(l, x) moyenne géométrique vix 1

1 10 x La principale leçon que l'on peut tirer de l'exemple numérique de Gauss est la convergence rapide des deux suites (ak) et (b k ). La dernière colonne indique le nombre de décimales communes aux deux termes. Après seulement 4 itérations, on obtient une approximation de MAG( V2, 1) ayant 19 décimales exactes. À chaque itération, le nombre de décimales exactes double pratiquement. Cette propriété traduit ce que l'on appelle la convergence quadratique de l'algorithme. C'est une très bonne vitesse de convergence, qui explique l'intérêt que les mathématiciens portent à cette méthode. Dans la formule (7.1) sur 1r, la vitesse à laquelle 1r est calculé est déterminée par la vitesse à laquelle la fonction :tvlAG (au numérateur) est elle-même calculée; si ce dernier calcul est effectué avec une convergence quadratique, cette dernière est léguée au calcul de 1r.

Le dénominateur de la formule (7.1) contient des termes q. Ils sont obtenus par la mise en IJuvre de l'algorithme MAG, à partir des coefficients ak et bk calculés lors des étapes successives : le coefficient Ck+1 est défini comme la demi-différence de ak et bk . Autrement dit,

(7.3)

L'algorithme MAG de Gauss

93

c'est-à-dire, compte tenu de l'expression de ak+l et bk+1 en fonction de ak et bk,

(7.4) Comme les suites (an) et (b n ) ont même limite, il est clair que la suite (c n ) tend vers O. Voici quelques propriétés fondamentales de la fonction MAG. Soit ao et bo deux réels vérifiant < bo ~ ao. Alors, la suite (Ck) définie pour tout kEN k ,. fi l ' l " t ' · par Ck+l = ak -2 b ' ven e es ega 1 es sUlvantes [32 ,p. 1-4] :

°

ak = ak+l + Ck+l bk = ak+l - Ck+l

MAG(a, b) = lim ak = lim bk k---++oo

k---++oo

MAG(Àa, Àb) = ÀMAG(a, b) MAG(a,b) = MAG (a; b, MAG(l, b)

=

Va"b)

1 + bMAG(l, 2Vb)

2 l+b bk ~ bk+1 ~ ak+l ~ ak MAG(ak, bk ) = MAG(ak+l' bk+l) = MAG(a, b) Si ao = 1 et si ~e(bo) > 0, l'algorithme MAG est bien défini. Les suites (ak) et (b k ) construites grâce à l'algorithme MAG sont définies pour tout k, et elles convergent à vitesse quadratique. L'algorithme MAG peut s'étendre aux entiers négatifs, en posant a-k = 2ka k, b-k = 2kck, et Ck = 2kbk, où ak, bk, et Ck, sont les suites construites grâce à l'algorithme MAG en l'initialisant avec ak = ao, bk = Co et Ck = bo, donc en permutant bo et Co.

2

l'algorithme MAG de Gauss

C'est en partant de ses travaux sur la moyenne arithmético-géométrique, et d'autres résultats que nous allons aborder, que Gauss arriva à cette formule

94

Gauss et

7r

d'approximation de 7r qui est si importante aujourd'hui (7.1). On peut en déduire directement un algorithme de calcul approché de 7r.

L'algorithme MAG de Gauss Initialisation ao:= 1 bo := 1/V2 So := 1/2

Itération (k = 0, 1,2 ... , K - 1)

ak+l := bk+l :=

ak

+ bk 2

v'tbk

C~+l := (ak+1 - t)2

._ Sk - 2k+l C2 + Sk+l .k 1

Retourner une approximation de 7rK

=

(aK

7r

donnée par

+ bK)2 2SK

L'algorithme commence par l'initialisation de trois variables a, b et s. Au fil des itérations successives, les variables a et b évoluent en accord avec les règles de l'algorithme MAG vers l'approximation de MAG(l, 1/ V2) qui figure au dénominateur de (7.1). Pendant ce temps, la somme s du dénominateur est calculée grâce à la variable auxiliaire c~+1 = (ak+1 - ak)2. L'utilisation d'une variable auxiliaire t = ak est rendue nécessaire par le fait que la valeur ak soit utilisée encore deux fois après avoir été déjà remplacée par ak+1. L'itération se poursuit jusqu'à ce que les résultats aient atteints un seuil de précision prédéfini, ou bien jusqu'à ce qu'un nombre prédéfini d'itérations aient été exécutées. Au terme de la procédure, l'approximation de 7r est obtenue en effectuant un unique calcul hors de la boucle. Au lieu de la valeur

+ bK)2 qui est employée. C'est la 2s K meilleure approximation que l'on puisse obtenir en K itérations. (inaccessible) MAG(l,l/V2), c'est (aK

Ainsi ces quelques lignes définissent-elles l'un des meilleurs algorithmes de calcul de 7r. Avec seulement trois itérations, on obtient déjà 19 décimales exactes:

La variante de Schéinhage

95

Itération

PK

Nombre de décimales correctes

1

3.14 ...

3

2

3.1415926 ...

8

3

3.141592653589793238 ...

19

4

idem

41

5

idem

84

6

idem

171

7

idem

345

8

idem

694

9

idem

1 392

Chaque itération supplémentaire fournit deux fois plus de décimales que l'itération précédente. Toutes les 10 itérations multiplie par 100 le nombre de décimales exactes, et il suffit de 36 itérations pour calculer les premières 206,1 milliards de décimales. L'erreur absolue est [32, p.48] :

La deuxième expression montre clairement la décroissance quadratique de l'erreur, et l'on en déduit également que PK est toujours plus petit que 1f.

3

La variante de Schonhage

Les performances de l'algorithme MAG de Gauss dépendent fortement des calculs effectués avec des entiers longs, c'est-à-dire ayant un très grand nombre de décimales. En effet, il faut effectuer le produit akbk, le calcul de la racine carrée de ce terme, et calculer le carré (ak+l - ak)2. (En revanche, les additions longues et les multiplications par des puissances de 2 ont moins de conséquences sur les performances; en effet, ces multiplications sont effectuées avec de simples décalages lorsque les nombres sont écrits en base deux.) Toute amélioration des performances est bien sûr hautement désirable. La version suivante, conçue par Arnold Schonhage [105, p. 266], accélère considérablement l'algorithme de Gauss. Cette variation évite la multiplication de nombres longs akbk (une «multiplication longue» ) qui doit être exécutée à chaque étape.

96

Gauss et

1f

La variante de Schonage de l'algorithme MAG de Gauss Initialisation

ao:= 1 Ao:= 1 Bo:= 0.5 So := 0.5

Itération (k

= 0,1,2 ... , K -

t:=

bk

1)

Ak+Bk

4

= \l'BK

ak+l :=

+ bk

ak

2

.- a 2k+l A k+l·BHl := 2(Ak+l - t) Sk+l := Sk

+ 2k+l(BHl -

A k+1)

Retourner une approximation de

PK:=

(A K

1f

donnée par

+ B K )2 SK

Schonhage se passe de la multiplication longue akbk en remplaçant ce produit par des opérations plus rapides effectuées avec d'autres variables: akbk = 2( a - k + Z2 - ~ (ak + bk)). (Les carrés de a et b sont stockés dans les variables A et B.) Les performances s'en trouvent améliorées d'environ 25%. C'est le fruit d'un simple réarrangement des opérations, sans astuce particulière de mise en œuvre. De cette façon, Schonhage évite également d'une part un calcul long de racine carrée au cours de l'initialisation et d'autre part une longue opération de quadrature durant le calcul de l'approximation de 1f. Si l'on tire parti du fait que bk et Bk peuvent partager le même emplacement de mémoire, alors la variante de Schonhage, tout comme la forme originale, ne demande que 5 variables longues, à savoir a, A, b = B, t et s. Le gain de vitesse n'est pas limité par une occupation supplémentaire de mémoire. Il est très facile de convertir en programme l'algorithme MAG de Gauss en utilisant la variante de Schonhage : a ::; A

1

B ::; s

0.5

La variante de Schënhage

For k

=

1 to N

t

(A+B)/4

b

sqrt(B)

a

=

97

(a+b)/2

A

a*a

B

(A-t)*2

End For Pour le calcul des premières décimales de 7f, il est facile d'implanter ce programme dans tout langage de programmation disposant des opérations arithmétiques effectuées en virgule flottante, ou mieux encore, dans tout logiciel de calcul algébrique. La mise en IJuvre en vue d'établir un nouveau record du monde pose d'importants problèmes d'implantation.

Le problème d'un stockage massif. Dès le début des calculs, les variables longues a, A, b = B, s et t doivent être évaluées et manipulées avec une longueur compatible avec le résultat final; mais quand veut obtenir plusieurs centaines de milliards de chiffres de 7f, la mémoire vive des ordinateurs, même des plus gros, n'est pas suffisante; c'est pourquoi les variables doivent être stockées hors de la mémoire vive, et y être introduites bloc par bloc. Pour faire cela rapidement, il faut effectuer un gros travail de gestion de mémoire propre au processeur utilisé. L'arithmétique de haute précision. Les instructions standard implantées dans les ordinateurs permettent d'effectuer des calculs avec une précision limitée, et beaucoup d'ordinateurs permettent seulement de manipuler des variables s'écrivant avec au plus 16 décimales. Aussi les opérations longues telles que l'addition ou la modification de variables longues doivent-elles être décomposées en opérations « courtes». La procédure est théoriquement complexe et sa mise en œuvre pratique est cruciale pour les performances. Pour cette raison « l'arithmétique de haute précision» nécessaire est généralement la partie la plus difficile de l'écriture d'un programme de calcul des décimales de 7f. C'est même d'habitude la motivation principale pour le développement d'un tel programme. Il existe cependant de grandes bibliothèques de programmes de calculs en grande précision que l'on peut acquérir. Il est alors possible d'en extraire des fonctions que l'on peut incorporer dans le programme de calcul de 7f, ce qui permet de se dispenser d'effectuer ce travail fondamental de programmation (y compris celui lié à la gestion de mémoire mentionnée ci-dessus).

98

4

Gauss et

'if

Histoire d'une formule

La Moyenne Arithmético-Géométrique Sous une allure inoffensive, la formule de Gauss pour 'if (7.1) dissimule des aspects très intéressants : elle est remarquable non seulement pour son efficacité dans le calcul de 'if, mais aussi pour son histoire et pour les propriétés mathématiques sur lesquelles elle repose. La moyenne arithmético-géométrique (MAG) et sa règle de calcul sont moins vieilles qu'on ne pourrait le supposer du fait de leur simplicité. Les deux furent découvertes il y a environ 200 ans. Aussi surprenant que ce soit, la règle de calcul de la fonction MAG est en réalité antérieure à la découverte de cette fonction [46J. Le mathématicien français Joseph-Louis Lagrange (17361813) fut en 1785 le premier à se servir de cette règle, pour le calcul approché d'intégrales elliptiques. Il ne découvrit néanmoins ni la fonction MAG, ni ses liens avec les intégrales elliptiques. Ce fut Gauss qui les découvrit. Ainsi que l'écrivit David Cox, « ... nous avons affaire à une situation surprenante, où Lagrange fut un précurseur de Gauss, alors que ce dernier fut lui-même un précurseur d'Abel, de Jacobi et de bien d'autres ». [45, p.315J. Ce fut en 1791, alors qu'il n'avait que 14 ans, que Gauss découvrit la fonction MAG. Sa découverte exerça sur lui une telle fascination que durant les dix années qui suivirent, il travailla presque sans interruption au développement d'une théorie des moyennes arithmético-géométriques. Son travail atteint une profondeur qui depuis n'a pas été égalée [57, p.186J. Ce n'est que lorsqu'il eut atteint 22 ou 23 ans que Gauss écrivit un mémoire en latin dans lequel il décrivait ses découvertes sur la moyenne arithmético-géométrique : de origine proprietatibusque generalibus numerorum arithmético-geometricorum (Sur l'origine et les caractéristiques générales des moyennes arithmético-géométriques) [56, III, pp.361-374J. Le mémoire ne fut jamais publié comme tel, et ce ne fut qu'en 1866 qu'il fut imprimé dans un recueil de travaux. De son vivant, Gauss ne publia qu'un article mentionnant ces moyennes; ce fut en 1818 dans son traité Determinatio attractionis (Sur l'attraction de l'anneau elliptique) [56, III, p. 352-353], qui contient la troisième preuve de l'identité fondamentale (7.13). On trouve des informations supplémentaires dans ses écrits formels. On sait très peu de choses sur les recherches que, durant son adolescence, Gauss mena sur les moyennes arithmético-géométriques. Il semble cependant qu'il disposa très rapidement des résultats mentionnés ci-dessus; ses recherches sur la lemniscate lui montrèrent certainement l'importance du cas particulier (y2, 1). Il y a aussi des indications montrant qu'il connaissait déjà en 1794 le lien entre la fonction MAG et le calcul de ce qu'il appelait les « intégrales numériques», que l'on appelle maintenant les fonctions theta.

99

Histoire d'une formule

Il Y eut deux phases dans les recherches de Gauss sur la fonction MAG, et le 13 mai 1799 marque le début de la seconde phase. Ce fut ce jour-là que Gauss, âgé de 22 ans, réussit à établir un lien entre MAG et un domaine qu'il avait jusqu'alors étudié indépendamment.

La lemniscate Outre la fonction MAG, le deuxième ingrédient rentrant dans la formule de Gauss (7.1) est la fonction appelée lemniscate. Cette fonction tire son nom de la lemniscate, une courbe que Gauss avait déjà étudiée en détail alors qu'il était adolescent. La lemniscate tire son nom du mot grec )..T//-Lw/w(J" (lemniskos), signifiant « petit ruban». Elle ressemble à un huit couché.

Écrite en coordonnées polaires, une de ses équations est r 2

= a 2 cos 2B.

Quand Gauss s'intéressa à la lemniscate, cette courbe était connue depuis presque 100 ans. En 1694, deux des frères Bernoulli l'avaient découverte indépendamment : Jacques Bernoulli (1654-1705) et son cadet Jean (1667-1748). L'article de Jacob parut en septembre 1694 et celui de Jean un mois plus tard seulement. À la suite de ces publications, les frères eurent une violente dispute pour savoir auquel des deux revenait la paternité de la découverte [45, p. 311]. La querelle alla si loin que Jean jura qu'il ne retournerait jamais à Bâle tant que son frère y vivrait.

av

Jacques Bernoulli avait découvert la lemniscate en partant de la courbe dite « élastique», dont une équation cartésienne est x 2+y2 = (x 2 - y2). Cette courbe élastique est celle que l'on obtient lorsqu'on plie une baguette de telle sorte que les tangentes en ses extrémités soient perpendiculaires à la droite reliant ces extrémités.

0+------------+

~-"-,B

100

Gauss et

7r

Une équation de la courbe élastique est

La formule donnant la longueur de la courbe élastique eut historiquement plus d'importance que l'équation de cette courbe. Cette longueur est donnée par

(7.10)

LV

=2

1 1

o

dt

~ vI - t 4

= 2.622 057 554 2 ...

Jacques Bernoulli trouva une formule donnant cette longueur dès 1691. Il lui fallut ensuite trois années pour trouver une courbe d'équation plus simple ayant la même longueur. C'était la lemniscate, qu'il trouva en 1694; la longueur d'une de ses deux boucles est donnée par l'intégrale ci-dessus. Ainsi peut-on dire que la longueur d'un arc de la lemniscate fut découverte avant la lemniscate elle-même [45, p. 311]. Au XVIIIe siècle, bien avant Gauss, la courbe élastique et la lemniscate étaient mentionnées dans beaucoup de traités de mathématiques. Par exemple, en 1730 James Stirling (1692-1770) donna des valeurs approchées très précises des intégrales (7.9) sur [0, 1] et de (7.10); ses résultats donnaient les 17 premières décimales. Giovanni Fagnano (1715-1797) découvrit certaines méthodes pour partager un arc de lemniscate en n parties égales, lorsque n est un entier de la forme 2m , 3· 2m ou 5· 2m [45, p. 313]. À partir de 1748, Leonhard Euler (1707-1783) développa la théorie des intégrales elliptiques, en commençant avec la lemniscate. En particulier, Euler découvrit ce lien remarquable entre les deux intégrales précédentes:

7r

(7.11)

4

Gauss commença à travailler sur la lemniscate en janvier 1797 (à l'âge de 19 ans), ainsi que l'indique la fiche nO 51 de son agenda mathématique: [55, p.67] : Curvam lemniscatam a V:~x4 pendentem perscrutari coepi » (J'ai commencé mes recherches sur la lemniscate, qui est une courbe fonction de ... ). Dans la première version de ses notes, Gauss avait écrit le mot elasticam, mais il le barra plus tard pour le remplacer par lemniscatam. Plus tard, il employa également le symbole LV, comme dans (7.10).

J

Gauss recommença ses recherches en s'attaquant au problème du partage d'une lemniscate en parties égales, que nous avons mentionné plus haut à

Histoire d'une formule

101

propos de Fagnano. Cela le conduisit aux «fonctions de la lemniscate» sinlemn et coslemn ainsi définies : sinlemn

(rx Jo ~) = x, 1 - t4

coslemn ( -w 2

lX 0

2

t dt

~ v1-t 4

) = x

Il définit ces fonctions dans le cadre des nombres complexes et établit diverses propriétés de ces fonctions. Un an après avoir découvert la construction à la règle et au compas d'un polygone régulier à 17 côtés, il trouva une construction à la règle et au compas d'un partage d'une lemniscate en 5 parties de même longueur. Ainsi que l'indiquent quatre fiches de son agenda, il fit au cours des trois premiers mois de 1797 un grand nombre de découvertes dans ce domaine (n.54, 59, 60, 62). Gauss fut particulièrement encouragé lorsqu'il remarqua l'analogie entre les fonctions de la lemniscate et les fonctions du cercle, par exemple (7.12)

W

[1

dt

"2 = Jo v'f=t4

et

L'analogie était encore plus visible car au lieu du symbole w, on utilisait à l'époque plutôt II. En 1798, Gauss commença à étudier le nombre -!' et cela fut à l'origine de nouvelles découvertes. Entre autres choses il trouva un développement en série de l'inverse de ce nombre, ce qui lui permit d'en calculer les 15 premières décimales. On peut dire qu'en juillet 1798 Gauss connaissait déjà « tout» du quotient 7r /w [45, p. 319]. Sur la fiche nO 92 de son agenda, on peut lire « Nous avons découvert des propriétés très fines de la lemniscate, qui ont dépassé toutes nos attentes, et les méthodes utilisées ouvrent un domaine entièrement nouveau». Il sentait qu'il avait fait une découverte importante et dans la fiche n° 95 (en octobre 1798) il écrivit même: «Une nouvelle branche de l'analyse s'ouvre à nous, à travers notamment l'étude des fonctions, etc. » Gauss était si excité qu'il laissa sa phrase inachevée.

La fusion des deux domaines Vint alors le 30 mai 1799. Gauss nota ce jour-là: «Nous avons vérifié jusqu'à la onzième décimale que la moyenne arithmético-géométrique de V2 et de 1 est égale à 7r /w; si c'est prouvé, ce sera véritablement une nouvelle branche de l'analyse qui s'ouvrira à nous ». [56, X.2, p. 43] Sous forme de formule, cette découverte, qui aujourd'hui encore paraît sensationnelle, s'écrit ainsi: (7.13)

~ = MAG(V2, 1)(= 1.19814 ... ) w

102

Gauss et

7r

Grâce à cette formule, Gauss établit un lien entre deux domaines apparemment indépendants, les moyennes arithmético-géométriques et les fonctions de la lemniscate, deux thèmes étroitement liés aux fonctions elliptiques. Au moment de la découverte, il était aussi conscient de sa signification, ainsi que sa conclusion le suggère à travers l'expression (37 71

Numériquement l , 3.14084 ... < deux décimales exactes de 7r.

7r

< 3.14285 .... Cette approximation donne

Tropfke [114, p. 273] fit ce commentaire: « Cela marque l'origine de la valeur 3~, qui se répandit victorieusement de pays en pays et de livre en livre. À Alexandrie cette valeur ne tarda pas à remplacer la vieille valeur de (16/9)2, 1 Aujourd'hui, on écrit les encadrements en écrivant à gauche le nombre le plus petit, mais à l'époque d'Archimède, il était habituel d'écrire les inégalités dans l'autre sens. En outre, pour l'encadrement considéré, c'est le majorant qui est calculé en premier.

175

Les polygones

ARCHIMÈDE

parce qu'elle était tout aussi commode tout en étant plus précise. D'Alexandrie, l'approximation de 7r trouvée par Archimède se répandit jusqu'en Inde, et on a même établi qu'au Ve siècle ap. J.-C., elle était connue en Chine. » Seuls quelques fragments du livre d'Archimède ont survécu. Presque tous les passages en dorique, le dialecte que parlait Archimède ont été perdus. On a néanmoins pu reconstruire les grandes lignes de la preuve d'Archimède. Pour démontrer son théorème, Archimède calcula les périmètres de deux polygones réguliers à 96 côtés, l'un inscrit dans un cercle, l'autre circonscrit à ce cercle. Le périmètre du polygone circonscrit est légèrement plus grand que la circonférence du cercle et fournit ainsi une majoration de 7r, tandis que le périmètre du polygone inscrit est légèrement plus petit, et fournit une minoration de 7r. La longueur du polygone à 96 côtés d'Archimède fut calculée grâce à une séquence de polygones dans laquelle chaque polygone a deux fois plus de côtés que le polygone prédécesseur. Archimède commença par des hexagones, dont les propriétés géométriques avaient été étudiées en profondeur dans la Grèce antique. Des hexagones, il passa à des polygones à 12, puis 24, 48 et enfin 96 côtés. Il calcula d'abord les longueurs de tous les polygones circonscrits, puis

L'histoire de

176

1f

celles de tous les polygones inscrits, plutôt que d'évaluer de manière croisée d'abord les longueurs des deux hexagones, puis celles des deux polygones à 12 côtés, etc. Parfois, la construction d'Archimède est décrite autrement. Archimède obtint les formules nécessaires en se servant des figures ci-dessous. Polygones circonscrits

Polygones inscrits

c C D

A

B

f----~,..'O

(13.7) (13.8)

(CO+OA): CA = OA: AD OA2 + AD 2 = OD 2

r--------~

(13.9) (13.10)

(AB

A

: BC = AD: DB AD 2 + DB 2 = AB 2

+ AC)

Les notations utilisées dans les figures sont identiques à celles qu'employa Archimède. Les segments AC et BC représentent les demi-côtés d'un polygone inscrit ou circonscrit à n côtés, tandis que AD et BD représentent les demi-côtés du polygone suivant. Ainsi OD et AD ont-ils pour effet de diviser des angles AOC et BAC. Les formules (13.7) et (13.9) peuvent être démontrées à l'aide de la géométrie élémentaire, mais ce n'est pas la méthode la plus simple. Archimède dut les calculer sans les formules trigonométriques de duplication, et même sans véritable formule du tout. Les formules permettant de passer d'un polygone à n côtés au suivant offrirent à Archimè la possibilité de de construire deux séquences de nombres complètement symétriques (a6, a12, a24, a48, a96) et (b 6 , b12 , b24, b48 , b96 ), qui sont liées de la manière suivante :

(13.11)

(13.12) Au temps d'Archimède, les notations trigonométriques usuelles n'existaient pas encore. En les utilisant, on voit que les séquences (an) et (b n ) sont reliées par les formules an = ta~ bn = si~ ex = ~, où c est une constante d'échelle (le'

(le'

177

Les polygones

que l'on peut choisir de façon à simplifier les calculs. Les deux formules d'Archimède (13.11) et (13.12) sont probablement les deux premières formules de récurrence de l'histoire; elles lui permirent de passer de l'hexagone au polygone à 96 côtés. Après avoir établi ces formules, Archimède eut seulement besoin de valeurs initiales permettant d'effectuer le calcul. Les proportions initiales des deux hexagones GA: AC et AC: CB valant V3, toute la précision du calcul reposait sur celle de l'évaluation de V3. Comme Archimède n'avait pas d'autres moyens à sa disposition, il dut se contenter de deux approximations, et sans explication choisit cet encadrement : 1351 780

(13.13)

> V3 >

265 153

Peu d'énigmes suscitèrent autant de travail de la part des historiens des sciences que la question de comprendre comment Archimède arriva à cet encadrement de V3 par des fractions approchant V3 = 1. 7320508 ... respectivement à 2· 10- 5 et 5· 10- 7 près. L'explication la plus simple [64, II, p.51] est qu'il utilisa pour cela des inégalités déjà connues depuis longtemps, et sans doute au temps des Babyloniens,

b a+2a

(13.14) En prenant a

=

>

~

ya 2

b + b > a + --2a + 1

2, et b = -l, on obtient 2-i

> V3 > 2-~, soit

i

> V3 > %.

La dernière inégalité suggère d'utiliser 5 comme approximation de 3V3 V27 = V25 + 2. En réutilisant l'encadrement (13.14), on obtient 2 5 + 10

2

26

19

> 3V3 > 5 + Un soit 15 > V3 > U

L'inégalité î~ > V3 permet d'utiliser 26 comme approximation de ~ V675. Une nouvelle application de (13.14), fournit alors 1 26 - 52

=

1 1351 soit - 51' 780

> 15V3 > 26 - -

1325 765

> V3 > - -

=

265 153

= -

Quoi qu'il en soit, Archimède prit les numérateurs 1351 et 265 de (13.13) comme a6, les dénominateurs 780 et 153 comme C, et 2c comme b6 . Il exécuta alors quatre itérations, une pour chacun des polygones à 12,24,48 puis 96 côtés. À chaque itération il devait faire une approximation d'une racine carrée

178

L'histoire de

7r

à l'aide d'une fraction, et pour cela, il employa évidemment la méthode que

l'on vient de détailler pour l'approximation de V3. En tout cas l'erreur sur 7r due à l'approximation d'un cercle par un polygone à 96 côtés était 8 fois plus grande que l'erreur due aux calculs, pour l'un des côtés de l'encadrement, trois fois pour l'autre côté. La plupart des calculs de la procédure suivie ont pu être reconstitués (seules les expressions entre crochets ont été ajoutées) et on peut les résumer ainsi 2 [64, II, p.55J

Polygones circonscrits

n

a

b

c

6

265

306

153

12

571

> [)571 2 + 1532 J

24

1162~

48

2334~

[V(1162~)2 + [V(1162~)2 +

96

4673~

153

1172~ 1532 ] > 2339~ 153 2 ] >

153 153 153

Polygones inscrits c

n

a

b

6

1351

1560

12

2911

24

5929~ 41 1823

< )2911 2 + 780 2 < 3013~ 4

48 96

3661 1007

1

780 240

2

2

< )1823 + 240 < 1838

tl

tl

2016i

780

240 66

2

< )(1007 +

66 2

< 1009i

V(2016i)2 + 66 2
1 mois? Kanada, Tamura 1989.07 536,870,898 G2 67 :13 h Chudnovsky's 1989.08 1,011,196,691 ? C > 2 mois? Kanada, Tamura 1989.11 74 :30 h 1,073,741,799 G2 Chudnovsky's 1991.08 2,260,000,000 ? 250 h? C Chudnovsky's 1994.05 4,044,000,000 ? inconnu C Takahashi, Kanada 1995.06 3,221,225,466 B4 36 :52 h Takahashi, Kanada 1995.08 4,294,967,286 B4 113 :41 h Takahashi, Kanada 1995.10 6,442,450,938 B4 116 :38 h Chudnovsky's 1996.03 8,000,000,000 inconnu C Takahashi, Kanada 1997.04 17,179,869,142 G2 5 :11 h Takahashi, Kanada 1997.05 15 :19 h 34,359,738,327 B4 Takahashi, Kanada 1997.07 51,539,607,510 B4 29 :03 h Takahashi, Kanada 1999.04 68,719,470,000 B4 32 :54 h Takahashi, Kanada 1999.09 206,158,430,000 G2 37 :21 h Kanada,Ushiro,Kuroda 2002.11 1,241,100,000,000 T,S2 600 h l Series: M=Machin (5.20), G=Gauss (5.22), K=Klingenstierna (5.21) 81=8t0rmer (5.19), R=-=Ramamanujan (13.49), C=Chudnovsky (8.7). Itérations: G2=Gauss AGM , B4=Borwein quartic TAB.

13.2 - Histoire de

7f,

ère de l'ordinateur

ENIAC NORC Pegasus IBM 704 Pegasus IBM 704 IBM 7090 IBM 7030 CDC 6600 FACOM MELCOLM HIT M-280R HIT M-280R RIT M-280R 8ymbolics 3670 CRAY-2 HIT 8-810/20 HIT 8-810/20 NEC SX-2 8-820 CRAY-2 IBM-3090 RIT 8-820/80 IBM-3090 RIT S-820/80 rn-zero inconnu RIT S-3800 RIT 8-3800 RIT S-3800 1 semaine? HIT SR2201 HIT SR2201 RIT 8R2201 RIT SR8000 HIT 8R8000 HIT 8000MP

210

L'histoire de

Qui? Bailey, P. Borwein, Plouffe Bellard Bellard Percival Percival Percival

Quand?

Position Hexadecimale

1995.09 1996.10 1997.09 1998.08 1999.02 2000.09

1010 1011 2.5.10 11 1.25 . 10 12 10 ·1012 250.10 12

TAB.

Formule

Séquence Hexadecimale

BBP Bellard Bellard Bellard Bellard Bellard

921C73C683 9C381872D2 87F7281DC9 07E45733CC AOF9FF371D E62168069C

... ...

... ... ...

...

13.3 - Histoire des records de calcul de décimales

Ir

14 Notes historiques 1

La plus ancienne quadrature du cercle?

Sur le cercle de rayon 5, il y a 12 points dont les coordonnées sont entières. Ce sont les 4 points d'intersection du cercle et des axes, (±5,0) et (0, ±5) et les 8 points de coordonnées (±3, ±4) et (±4, ±3), correspondant à des triangles rectangles de côtés de longueurs 3, 4 et 5. Ces points sont illustrés sur la figure de gauche ci-dessous. (0 125) 35,120) 25.,/2 44,117)

0

5 .,/2

(75,100)

3.,/2v'5

(0,0)

(125,0)

Ces 12 points sont les sommets d'un polygone dont 8 côtés ont comme longueur V2 x J5 et dont les 4 autres côtés ont comme longueur V2. Le diamètre de ce polygone est 10, et sa longueur est 8 x V2 x J5 + 4V2 ;:::;; 30,9550 ... Cela donne comme approximation de 7r, 3,09550 ... Si l'on fait subir au cercle de rayon 5 une homothétie de rapport 5, on obtient un cercle de rayon 25 qui, outre les 12 points images des 12 points à coordonnées entières du premier cercle contient 8 nouveaux points à coordonnées entières, (±24, ±7), (±7, ±24). Il y a donc 20 points à coordonnées entières, qui forment les sommets d'un polygone dont 12 côtés ont comme longueur 5V2, et dont les 8 autres côtés ont comme longueur 4J5. Ce polygone fournit une approximation de 7r qui est 7r, 3,12814 ... Si l'on fait subir au dernier cercle une nouvelle homothétie de rapport 5, on obtient un cercle de rayon 125 qui contient 28 points à coordonnées entières,

212

Notes historiques

les images des 20 points du cercle précédent, et les points de coordonnées (±117, ±44) et (±44, ±117). Ces 28 points sont les sommets d'un polygone possédant vingt côtés de longueur 25V2 et 8 côtés de longueur 3V2VS; ce polygone fournit une approximation de 'if qui est 3.13200 ... Cette construction peut être itérée. On déduit chaque nouveau cercle du précédent par une homothétie de rapport 5. Le nouveau cercle contient 8 points à coordonnées entières de plus que son prédécesseur. Les longueurs des côtés du polygone s'écrivent comme des multiples de V2 ou de V2VS. Cette procédure très simple aurait certainement enthousiasmé Pythagore; elle fut découverte par Franz Gnaedinger de Zurich [59] ; la démonstration complète de la construction est attribuée à Christoph Poeppe. Lorsqu'il publia sa construction, Gnaedinger indiqua également d'autres constructions géométriques simples pour déterminer les coordonnées des sommets; il conçut aussi des méthodes très simples pour déterminer des valeurs approchées aussi précises que l'on veut de V2 et de VS. Voici par exemple une construction d'un tableau de nombres permettant de trouver des valeurs approchées de V2 : 112 2

3

5

12

4

7 29

17 70

10 41

24 99

58 140

La règle de construction du tableau est facile à reconstituer. Les fractions 10/7 et 7/5 sont des approximations simples de V2. Mais 24/17 et 17/12 sont meilleures, et 140/99 et 99/70 sont encore meilleures. Franz Gnaedinger est avant tout un égyptologue, et il chercha à savoir si « ces bons vieux Égyptiens» avaient eu connaissance de cette méthode. Sa conclusion est que c'est très probable. D'abord, les anciens Égyptiens avaient une bonne raison pour mesurer des cercles. Le hiéroglyphe associé au dieu du soleil Râ était un cercle. Si l'on pouvait seulement comprendre le cercle et sonder son nombre secret, alors on serait en mesure de partager une partie des pouvoirs de Râ. Ensuite, les Égyptiens furent assez précoces en mathématiques. Ils étaient déjà au fait des triangles pythagoriciens (triangles rectangles dont les longueurs des côtés sont des nombres entiers) ; les plus simples d'entre eux ont des côtés dont les longueurs sont des multiples de 3, 4 et 5 et les Égyptiens les qualifiaient de « triangles sacrés».

Une loi sur

7r

213

Selon Gnaedinger, tous les éléments d'une méthode d'approximation de 7r et de bien d'autres nombres se trouvent dans le complexe funéraire du pharaon Zoser à Saqqarah dans la pyramide de Chéops et dans celle de Chéphren, par exemple: • Saqqarah: 17/12 pour

v'2

• Saqqarah: de nombreux triangles pythagoriciens • Pyramide de Chéphren : demi section transversale

=

triangle sacré

• Pyramide de Chéops: le triangle sacré 15 - 20 - 25 dans la chambre royale • Pyramide de Chéops: 140/99 pour

v'2 et

• Pyramide de Chéops: base x 2/hauteur

161/72 pour )5

= 22/7 c'est-à-dire à peu près

7r.

Gnaedinger s'est principalement intéressé au génie architectural visionnaire d'Imhotep, qui aux alentours de 2600 av. J.-C. conçut la monumentale pyramide de Saqqarah près de la ville antique de Memphis; ce monument fut érigé à la gloire et pour la vie éternelle du pharaon Zoser. Pour étayer sa théorie, Gnaedinger cite d'autres égyptologues qui pensent qu'Imhotep aurait très bien pu avoir développé de bonnes approximations de 7r selon la procédure ci-dessus, et aussi d'excellentes approximations rationnelles de v'2 et de )5, par une construction semblable à celle du tableau ci-dessus. Après seulement deux itérations avec le polygone à 20 côtés, il aurait obtenu l'approximation 7r ~ 3.128 ... , qui est bien meilleure que (16/9? = 3.160 ... qui se trouve dans le papyrus Rhind daté de 1850 av. J.-C. et qui fut probablement découverte empiriquement (voir chapitre 13). Cette version plus précise de 7r aurait été découverte plus de 700 ans plus tôt.

2

Une loi sur

Jr

Il y a un peu plus d'une centaine d'années, une loi fixant à 3.2 la valeur de 7r failli être votée dans l'État d'Indiana, aux États-Unis. L'histoire amuse surtout les Américains, peut-être parce qu'elle se produisit dans leur pays et se termina finalement bien, à moins que ce ne soit parce qu'un vice-président peu populaire venait de cet État. À la fin du XIX e siècle vivait à Solitude, dans l'Indiana, un médecin de campagne qui s'appelait Edward Johnston Goodwin (1828 ?-1902). Selon sa biographie, cet homme découvrit la véritable valeur du nombre 7r par des moyens surnaturels au cours des premières semaines du mois de mars 1888. À proprement parler, sa « révélation» dut comporter plusieurs valeurs de 7r, car dans une lettre qu'il adressa à l'American Mathematical Monthly, il donna en réalité cinq valeurs différentes de 7r, allant de 2.56 à 4.0.

214

Notes historiques

Il déposa des demandes de brevets dans plusieurs pays, dont l'Allemagne et l'Autriche. Il persuada ensuite un élu de sa ville natale d'introduire un projet de loi sur sa nouvelle découverte mathématique. Le texte de loi fut écrit par le Dr. Goodwin lui-même. Il y décrivait 1f littéralement, ainsi qu'il l'avait déjà fait dans l'American Mathematical Monthly, de plusieurs façons. Le projet de loi 246 contient par exemple, ce passage: ... révélant le quatrième fait important, que la proportion du diamètre sur la circonférence est comme cinq quarts à quatre ... Ce «fait» donne une valeur de 1f de 16/5 = 3.2. Ailleurs dans le texte sont données trois autres valeurs de 1f : « l'aire = (circonférence/ 4)2 donne une valeur 1f = 4, l'aire = 6 x (circonférence/4)2/5 donne la valeur 1f = 10/3 = 3.33333, tandis que 1f = 32/9 = 3.555556 est obtenu grâce à l'égalité diamètre / (circonférence / 4) = 9/8 ». Le projet de loi franchit le premier obstacle avec la chambre des représentants de l'Indiana le 5 février 1897. Après délibération de la commission responsable, le projet de loi fut transmis au sénat pour confirmation, avec un avis favorable. Pour la défense des représentants on doit dire qu'ils n'étaient préoccupés que des bénéfices commerciaux qu'ils comptaient en tirer pour leur État, et que sur le plan mathématique, ils faisaient entièrement confiance à la réputation du Dr Goodwin. Un représentant expliqua que si cette loi était votée, son auteur accorderait à son État natal le droit d'utiliser sa découverte gratuitement en la publiant, par exemple, dans les manuels scolaires, tandis que le reste du monde devrait payer des droits pour l'utiliser. Par chance pour la réputation de l'Indiana le professeur C.A. Waldo de l'université Purdue visita ce jour-là la chambre des représentants et assista à la séance de la commission. Il indiqua aux sénateurs les faiblesses du projet de loi, et ceux-ci le mirent en attente, où il est encore. Un des historiens ayant étudié cet événement, David Singmaster, nota que Goodwin fut l'un des rares « quadrateurs du cercle» à proposer plusieurs valeurs de 1f [110]. La valeur moyenne de toutes celles qu'il proposa pour 1f à travers ses articles, et dans le projet de loi mentionné ci-dessus a été calculée par Singmaster; c'est 3.28907. Cette histoire parut dans le journal allemand Die zeit (1997/28, 4 juillet 1997). Elle fut accompagnée de ce commentaire: «Avant de rire et de se moquer des institutions de l'Indiana et de l'ignorance générale qui régnait en 1897, on devrait réfléchir au destin qu'un tel projet de loi rencontrerait si aujourd'hui il était soumis au référendum. »

L'histoire de Bieberbach

3

215

L'histoire de Bieberbach

Pendant les années 1930, l'Allemagne nazie fut la toile de fond d"un triste épisode de l'histoire de 7r. De 1909 à 1933 le mathématicien juif Edmond Landau (1877-1938) poursuivit une brillante carrière à l'université de Gôttingen, centre mathématique renommé qui regroupait des mathématiciens aussi célèbres que David Hilbert, Félix Klein et Emmy Noether. Dans ses cours de calcul différentiel et intégral, Landau employait la définition de 7r qui est aujourd'hui considérée comme normale: 7r /2 est le plus petit zéro positif de la fonction cosinus. Dans le style concis qui était le sien, Landau écrivit dans un livre de cours: «La constante universelle du théorème 262 sera notée 7r» [51, p. 130J. En 1933 Landau fut révoqué de sa chaire sur un critère racial. Plus tard, un éminent collègue de Landau ajouta l'affront à la blessure en suggérant que le licenciement de Landau était motivé par des considérations liant mathématique et psychologie. Ce collègue berlinois de Landau était Ludwig Bieberbach, spécialiste de la théorie des fonctions. En juin 1934 il écrivit les lignes suivantes dans un traité sur la structure de la personnalité et la créativité mathématique: Ainsi ... le vaillant rejet par le corps des étudiants de Gôttingen qu'un grand mathématicien, Edmund Landau a subi, est dû au fait que le style non-allemand que cet homme met dans sa recherche et dans son enseignement est insoutenable pour des sensibilités allemandes. Un peuple qui a perçu, comment des désirs étrangers de domination rongent son identité, comment les membres d'une autre race travaillent pour imposer des idées étrangères aux siennes doit refuser les professeurs d'une culture étrangère. En 1934, le mathématicien anglais Godfrey H. Hardy qui fut, ainsi que nous l'avons vu le mentor de Ramanujan, répondit ainsi à Bieberbach: Pendant la première Guerre, beaucoup d'entre nous, beaucoup d'Anglais et beaucoup d'Allemands, avons dit des choses que nous pensions à peine et que nous regrettons maintenant de nous rappeler. La crainte peut-être pour son propre poste, l'effroi d'être entraîné dans ce torrent de folie en crue, la détermination à tout prix de ne pas être surpassé, tout cela est naturel mais ne constitue pas une excuse particulièrement héroïque. La réputation du professeur Bieberbach exclut de telles explications de ses assertions; et je suis conduit à la conclusion peu charitable qu'il les croit vraies.

15 L'avenir: calculs sur le Net Dans ce chapitre nous allons décrire une procédure de calcul distribué de 7[, c'est-à-dire une méthode de calcul de 7[ par petits morceaux indépendants qui peuvent être assemblés et utilisés ultérieurement. Avec cette approche, une grande partie du travail de calcul peut être partagée entre de nombreux petits ordinateurs connectés à Internet. Cela présente l'avantage de réserver l'usage des super-ordinateurs très coûteux aux parties du calcul qu'ils sont seuls capables d'exécuter. L'algorithme utilisé est appelé «algorithme du découpage binaire », que nous appellerons par son nom d'origine binsplit. Cet algorithme, qui circule depuis déjà quelques temps a récemment été réhabilité par Bruno Haible [62]. Il repose sur une série qui avait cessé d'être employée dans la chasse aux décimales de 7[ depuis l'apparition des algorithmes ultra-rapides. Cependant, ici, le facteur critique est la vitesse de convergence. Avec ceci en tête, il n'est pas étonnant que la série favorite pour l'algorithme binsplit soit celle qu'avaient utilisée les frères Chudnovsky, (8.7) qui fournit 15 décimales supplémentaires à chaque terme.

1

l'algorithme binsplit

Nous allons à présent établir les principes sous-jacents à l'algorithme binsplit. Ils sont en fait très simples. Nous souhaitons d'abord calculer la somme '2:.{:':01 ak, où les (ak) sont des nombres rationnels. La méthode naïve demande un temps proportionnel à N. On peut améliorer ce temps, en utilisant le quotient (15.1) après avoir posé

a-l

= 1.

On a alors

N-l (15.2)

L

k=O

ak = ro(1

+ rl(1 + r2(1 + r3(1 + ... (1 + rN-I)))))

218

L'avenir: calculs sur le Net

Posons, pour tout n et m