S.A.F. PI = 3. 1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 5923078164 0628620899 8628034825 3421170679 8214808651 3282306647 0938446095 5058223172 5359408128 4811174502 8410270193 8521105559 6446229489 5493038196 4428810975 6659334461 2847564823 3786783165 2712019091 4564856692 3460348610 4543266482 1339360726 0249141273 7245870066 0631558817 4881520920 9628292540 9171536436 7892590360 0113305305 4882046652 1384146951 9415116094 3305727036 5759591953 0921861173 8193261179 3105118548 0744623799 6274956735 1885752724 8912279381 8301194912 9833673362 4406566430 8602139494 6395224737 1907021798 6094370277 0539217176 2931767523 8467481846 7669405132 0005681271 4526356082 7785771342 7577896091 7363717872 1468440901 2249534301 4654958537 1050792279 6892589235 4201995611 2129021960 8640344181 5981362977 4771309960 5187072113 4999999837 2978049951 0597317328 1609631859 5024459455 3469083026 4252230825 3344685035 2619311881 7101000313 7838752886 5875332083 8142061717 7669147303 5982534904 2875546873 1159562863 8823537875 9375195778 1857780532 1712268066 1300192787 6611195909 2164201989 (these are just 1000 decimals of PI) ***** Computing PI ******* The Formula =========== This information comes from two books. My notes are a bit scratchy and faded now, but, at a guess, 1) The One Million Digits of PI, Guilloud and Bouyer, 1960's? 2) The Computer Age? {I'll check this out one day, or if someone could send me the info then great.} The value of PI was first calculated in 1949 on the ENIAC computer using the formula, pi = 16 arctan(1/5) - 4 arctan(1/239) which is known as machin's Formula. It calculated 2037 digits in 70 hours. The formula I used was, pi = 48 arctan(1/18) + 32 arctan(1/57) - 20 arctan(1/239) this was used on a 7600 Control Data computer to generate 1,000,000 digits in 23 hours and 18 minutes in 196? (I'd assume 1968 or 1969). I presume that calculating the two arctan's, 1/18 and 1/57, is preferred as the partial sums will reduce much quicker than for the arctan 1/5. The Method for calculating the ArcTan ===================================== The arctan is calculated as a series of continuously reducing partial sums, ArcTan 1/K = SUM(p = 0 to infinity) of (-1)^p/(2p + 1)K^(2p+1) The partial sums can be expressed as, Vn+1 = -(2n + 1)/(2n + 3) * 1/K^2 * Vn I use the variables vm for Vn and vn for Vn+1, confusing huh! Still the algorithm is quite simple. The first value of course is for p=0 and this reduces to v0 = 1/K which is what I set both vm and vn to at the start. Then I keep reducing vn and adding or subtracting it from vm which is the current sum. Obvious improvements that can be made to the algorithm ====================================================== 1) The most obvious one, and I will get around to it one day, is to change the array's Vn and Vm, into arrays of integers. Then each array element can store more digits which will immediately improve the performance of the calculation. The change which I have made, from storing single digits, 0..9, in the array, to storing 2 digits, 0..99, pretty well doubled the performance of the algorithm. A similar improvement could be made by switching to an integer with 4 digits, 0..9999. The only thing to watch here is that none of the multiplcations or divides could result in numbers greater than MaxInt. 2) Another thing that might be worth considering once the array has been converted to integers would be to allow up to 8 digits per element but do all calulations with 64 bit integers. I believe 386's and up do support this, they use the eax and edx registers, but I don't think Delphi does. The question of course would be whether or not the extra work handling 64 bit integers would gain you much speed, I assume it would. 3) And of course, the most obvious change, try out Delphi's speed optimizations, I haven't gotten around to looking at these. The Results =========== Arctan Vax 11/780(?) PC 7600 CDC Digits 36,000 50,000 1,000,000 1/18 4h20m 9m33s 9h53m 1/57 3h20m 6m49s 7h04m 1/239 2h20m 5m03s 5h14m PI 1h 1h07m Total ~ 11h 21m25s 23h18m ****** French only here :-( ****** A propos de pi. ------------------------------------------------------------------------ Le nombre PI est à beaucoup de titres un nombre magique et depuis plus de 4 mille ans, il exacerbe la curiosité des mathématiciens. Il semble qu'il soit connu depuis longtemps que le rapport de la circonférence d'un cercle et de son diamètre soit constant. Ceci n'implique pas pour autant que ce rapport ait été associé à un nombre particulier. En effet, la notion du nombre PI n'apparaît qu'au XVIIe siècle et l'usage de la lettre grecque qui commence avec le gallois William Jones en 1706 (il lui attribue la valeur 3,14159) ne se répandra vraiment qu'après avoir été employée par Euler en 1737. Notons que seuls les nombres PI, e et i ont droit à une lettre pour les représenter. A titre indicatif, il est amusant de souligner la relation 1+eiPI=0 qui unit ces 3 nombres. Rappelons que i est le nombre complexe tel que i2=-1. Une des premières apparitions d'une valeur de PI se trouve dans une liste de spécifications concernant la construction du temple de Salomon, aux environs de 950 avant J.C. et elle vaut 3. Cette valeur manque évidemment de précision mais du temps des Egyptiens et Mésopotamiens, de meilleures estimations avaient déjà cours, à savoir 25/8 = 3,125 et Racine carrée de 10 = 3,162. On retrouve aussi trace de rapport circonférence/diamètre dans la Bible où on lui attribue la valeur 3. Le Papyrus Rhind cite pour PI la valeur de 256/81=4*(1-1/9)2=3,16049... Rappelons que ce papyrus est la copie faite vers 1650 avant J.C. d'un texte encore plus ancien et que la valeur den'apparaissait pas telle qu'écrite ci-dessus puisque les expressions algébriques étaient inconnues et que toute technique de résolution était exprimée en langage habituel. Cette expression est la déduction d'une règle permettant de calculer l'aire d'un cercle à partir de son rayon. En utilisant des propriétés géométriques, et plus près de nous (mais tout est relatif), Archimède de Syracuse (287-212 avant J.C.) encadra le cercle par des polygones inscrits et circonscrits pour en arriver à 223/71<PI<22/7. Avec l'affinement des techniques de calcul mais en se basant toujours sur l'encadrement d'Archimède, Ptolémée trouva au IIe siécle après J.C. la valeur sexagésimale 3+8/60+30/3600=3,141666... Vers 500, Aryabhatta utilise 62832/2000=3,1416. Au XVIe siècle, 30 décimales sont connues, 140 au XVIIIe et 707 par Shanks à la fin du XIXe (mais plus de 200 étaient fausses). La course à la recherche du plus grand nombre de décimales de PI ne date bien sûr pas d'aujourd'hui mais l'utilisation de l'ordinateur lui a donné un nouvel élan. En 1949, 2000 décimales étaient calculées par un des premiers ordinateurs. En 1995, après plus de 116 heures de calcul, l'ordinateur du professeur Yasumasa Kanada a déterminé 6.442.450.938 décimales de PI. Voici quelques formules permettant de calculer PI avec plus ou moins de vitesse. Formule de Leonhard Euler (1707-1783) PI 2= 6 * (1 + 1/22 + 1/32 + 1/42 + 1/52 ......) Développement en série de arctg x avec x=1 (W.Leibniz 1646-1716 ou James Gregory 1638- 1675) PI = 4 * (1 - 1/3 + 1/5 - 1/7 + 1/9 ......) Développement en série de arctg x avec x=PI 3/3 (Euler) PI = 2 * PI 3 * (1 - 1/3 * 1/31 + 1/5 * 1/32 - 1/7 * 1/33 + ...) Formule de John Machin (1685-1751) à partir de arctg 1/5 - arctg 1/239 PI = 16 * (1/51 - 1/3 * 1/53 + 1/5 * 1/55 - 1/7 * 57 + ...) - 4 * (1/2391 - 1/3 * 1/2393 + 1/5 * 1/2395 - 1/7 * 1/2397 + ...) Formule de John Wallis (1616-1703) PI = 2 * (2/1 * 2/3 * 4/3 * 4/5 * 6/5 * 6/7 * ...) Formule de François Viète (1540-1603) 2/PI = PI(1/2) * PI(1/2+1/2*PI(1/2)) * ... Formule de Brouncker (1620-1684) 4/PI = 1+12/(2+32/(2+52/(2+72/.....))) Voici les formules décrites ci-dessus mises en programme Pascal. {$N+} USES CRT; VAR S, Err, P, Q, r : EXTENDED; i : LONGINT; Signe : SHORTINT; BEGIN CLRSCR; {============================================================================} S:=0;i:=0;Err:=1; WHILE NOT (Err Des méthodes autres que géométriques ou analytiques ont été utilisées pour déterminer une valeur de <Image>. Par exemple les méthodes statistiques avec lesquelles, la précision n'est pas obligatoirement au rendez-vous. Il y a par exemple la méthode appelée "l'aiguille de Buffon" qui consiste en le lâcher au-dessus d'une grille de lignes parallèles distantes d'une unité de longueur. La probabilité que l'aiguille touche une des lignes est de 2k/<Image> où k est la longueur de l'aiguille. Lazzerini affirma avoir utilisé cette méthode en 1901 pour trouver, à l'aide de 34080 lancers, la valeur de 355/113 = 3,1415929 Voici une autre méthode statistique basée sur une propriété géométique. Traçons un carré dont le demi-côté mesure une unité et inscrivons-y un cercle de rayon unitaire. La surface du carré est de 4 et celle du cercle est de <Image>. Si vous choisissons au hasard un point du carré, la probabilité qu'il se trouve dans le cercle est de <Image>/4. Et par conséquent, en recommençant de plus en plus souvent le choix aléatoire d'un point du carré, le rapport entre le nombre de points se trouvant dans le cercle (dont la distance à l'origine est inférieure à 1) et le nombre de points choisis doit s'approcher de
. Les deux programmes ci-dessous réalisent l'implémentation de cette méthode en mode texte et avec une visualisation graphique. PROGRAM Monte_Carlo_Mode_Texte; USES CRT; VAR Cpt, {Cpt compte les lancers} CptIn : LONGINT; {CptIn compte les coups dans la cible} x, y : REAL; {Le point choisi au hasard} BEGIN TEXTCOLOR(YELLOW); {Texte en jaune} TEXTBACKGROUND(RED); {Fond en rouge} CLRSCR; {Efface l'écran} CptIn:=0;Cpt:=0; {Initialise les compteurs} WHILE NOT (KEYPRESSED OR (Cpt=MaxLongInt)) DO BEGIN {Cpt=MaxLongInt évite que Cpt ne devienne trop grand} x:=RANDOM; {Choix au hasard de x dans [0,1[} y:=RANDOM; {Choix au hasard de y dans [0,1[} INC(Cpt); {Un point de plus} IF x*x+y*y<1 THEN INC(CptIn); {Point appartient au quart de cercle --> CptIn+1} GOTOXY(36,13); {Amène le curseur en colonne 36 ligne 13} WRITE('pi = ',4*(CptIn/Cpt):9:7); {Affiche pi} END; END. PROGRAM Monte_Carlo_Graphique; USES CRT,GRAPH; VAR grDriver, grMode, ErrCode : INTEGER; {Paramètres graphiques} x, y, r, xp, yp : WORD; {Coordonnées des points} Cpt, {Cpt compte les lancers} CptIn : LONGINT; {CptIn compte les coups dans la cible} Dx, Dy : REAL; S : STRING[20]; {Pour convertir pi en chaîne de caractères} BEGIN grDriver := Detect; {Détecte les paramètres du PC} INITGRAPH(grDriver, grMode,''); {Initialise le mode graphique} ErrCode := GraphResult; {Erreur à l'initialisation graphique?} IF ErrCode<>grOk THEN WRITELN('Erreur ', GraphErrorMsg(ErrCode),' à l''initialisation graphique.') ELSE BEGIN x:=200;y:=400;r:=400; DIRECTVIDEO:=FALSE; SETCOLOR(YELLOW); {Affichage en couleur jaune} CLEARDEVICE; {Efface l'écran en mode graphique} SETFILLSTYLE(EmptyFill,BLACK); {Paramètres pour BAR} SETTEXTSTYLE(SmallFont, VertDir, 1); {Paramètres d'affichage du texte} RECTANGLE(x,y-r,x+r,y); {Dessine le carré de côté r} ARC(x, y-r, 270, 360, r); {Dessine l'arc de cercle de rayon r} CptIn:=0;Cpt:=0; {Initialise les compteurs} WHILE NOT (KEYPRESSED OR (Cpt=MaxLongInt)) DO BEGIN {Cpt=MaxLongInt évite que Cpt ne devienne trop grand} Dx:=RANDOM; {Choix au hasard de Dx dans [0,1[} Dy:=RANDOM; {Choix au hasard de Dy dans [0,1[} xp:=x+TRUNC(Dx*r); {x du point trouvé au hasard} yp:=y-r+TRUNC(Dy*r); {y du point trouvé au hasard} INC(Cpt); {Un point de plus} IF Dx*Dx+Dy*Dy<1 THEN BEGIN {Ce point appartient-il au quart de cercle?} INC(CptIn); {On augmente le compteur} PUTPIXEL(xp,yp,LIGHTGREEN); {Affiche le point} END ELSE PUTPIXEL(xp,yp,LIGHTRED); {Affiche le point en rouge clair} GOTOXY(6,25); {Amène le curseur en colonne 6 ligne 25} WRITE('ã = ',4*(CptIn/Cpt):9:7); {Affiche pi en mode texte} STR(4*(CptIn/Cpt):9:7,S); {Transforme 4*(CptIn/Cpt) en texte} BAR(100-TEXTHEIGHT(S),100,100,100+TEXTWIDTH(S)); {Efface l'ancien pi} SETCOLOR(LIGHTBLUE); {Affichage en couleur jaune} OUTTEXTXY(100,100,'pi = '+S); {Affiche pi en mode graphique} END; READKEY; {Attend qu'une touche soit enfoncée} CLOSEGRAPH; {Quitte le mode graphique} END; END. Le nombre PI a un site Internet The Uselessness of Pi and its irrational friends qui lui est dédié et d'où proviennent certaines des information reprises sur cette page. Visitez-le. Vous y découvrirez un tas de renseignements passionnants.