Er bestaan diverse wiskundige methoden en rekenkundige procedures die door de eeuwen heen zijn ontwikkeld om de numerieke waarde van de wiskundige constante π (pi) te benaderen. Hedendaags worden hiervoor computers gebruikt om de algoritmes om pi te bepalen uit te voeren.

Omdat π een irrationaal getal is, kan de waarde niet exact worden geschreven als een breuk of een eindige reeks decimalen.

Meetkundige benadering De oudste algoritmes om pi te bepalen waren meetkundig van aard. Omdat de lengte van een gebogen lijn (de cirkelomtrek) wiskundig lastig direct te berekenen was zonder integraalrekening, probeerden wiskundigen de cirkel "in te klemmen" tussen veelhoeken met rechte zijden.

Methode van Archimedes thumb|Cirkel met in- en omgeschreven veelhoeken De eerste rigoureuze wiskundige benadering werd rond 250 v.Chr. ontwikkeld door Archimedes van Syracuse. Zijn aanpak, gebaseerd op de uitputtingsmethode, maakt gebruik van twee regelmatige veelhoeken: een die in de cirkel is beschreven en een die om de cirkel is beschreven.

De omtrek van de cirkel () ligt altijd tussen de omtrek van de ingeschreven veelhoek () en de omgeschreven veelhoek ():

Het algoritme werkt iteratief door het aantal zijden van de veelhoeken in elke stap te verdubbelen: Start met een regelmatige zeshoek (waarvan de zijden makkelijk te berekenen zijn). Pas de verdubbelingsformule toe om de omtrek van een 12-hoek te vinden. Herhaal dit proces voor een 24-, 48- en 96-hoek.

Archimedes berekende handmatig de waarden tot aan een veelhoek met 96 zijden. Hiermee kwam hij tot de beroemde grenswaarden:

Of in decimale notatie ongeveer:

De bovengrens is nog altijd een veelgebruikte breukbenadering voor pi. Deze veelhoek-methode bleef bijna 2000 jaar lang de standaard voor het berekenen van pi. De Nederlands-Duitse wiskundige Ludolph van Ceulen gebruikte in de 16e eeuw deze zelfde methode met een veelhoek van zijden om 35 decimalen te berekenen, wat hem jaren rekenwerk kostte.

Vroege analyse: Reeksen en producten In de 16e en 17e eeuw vond er een verschuiving plaats van meetkundige methoden naar analytische formules. Met de ontwikkeling van de rekenkundige reeks en later de integraalrekening (calculus), ontdekten wiskundigen manieren om pi uit te drukken als een oneindig product of een oneindige som.

Formule van Viète In 1593 publiceerde de Franse wiskundige François Viète de eerste formule voor pi die gebaseerd was op een oneindig proces, in plaats van een meetkundige constructie. Zijn formule maakt gebruik van geneste wortels:

Dit was het eerste voorbeeld van een oneindig product in de wiskundegeschiedenis. Hoewel theoretisch belangrijk, is de formule lastig te gebruiken voor handmatige berekeningen door de vele worteltrekkingen.

Wallis-product

De Engelse wiskundige John Wallis kwam in 1655 met een productformule die enkel rationale breuken gebruikt:

Gregory-Leibniz-reeks Met de ontdekking van de reeksontwikkeling voor de arctangens-functie, vonden James Gregory en Gottfried Wilhelm Leibniz onafhankelijk van elkaar een zeer eenvoudige formule. Door in te vullen in de reeks voor , ontstaat de volgende wisselreeks:

Hoewel deze formule wiskundig elegant is, is de convergentie voor praktische berekeningen onbruikbaar traag. Om slechts 10 decimalen nauwkeurigheid te krijgen, moeten er miljarden termen worden opgeteld.

Reeks van Euler Leonhard Euler loste in 1735 het beroemde Bazel-probleem op, waarmee hij een verband legde tussen pi en de priemgetallen (via de Riemann-zèta-functie):

Hoewel deze reeks sneller convergeert dan die van Leibniz, is ook deze methode niet efficiënt genoeg voor het berekenen van veel decimalen. Euler berekende met zijn reeks 127 decimalen waarmee hij het wereldrecord hield tot 1841.

Arctangens-reeksen en Machin-achtige formules De reeks van Gregory-Leibniz () convergeert zeer traag, omdat aan de rand van het convergentiegebied ligt. Wiskundigen realiseerden zich dat de Taylorreeks voor de arctangens veel sneller convergeert voor kleinere waarden van :

De uitdaging was om (wat gelijk is aan ) te schrijven als een som van arctangensen van kleine breuken. Deze formules staan bekend als Machin-achtige formules.

Formule van Machin

In 1706 ontdekte John Machin een formule waarmee de convergentiesnelheid drastisch werd verhoogd. Hij maakte gebruik van de goniometrische optelformules om uit te drukken in termen van en :

Het voordeel van deze formule is tweeledig: De term is klein genoeg om de reeks snel te laten convergeren, en delen door machten van 5 is rekenkundig eenvoudig in het decimale stelsel. De term is zeer klein, waardoor de reeks voor dit deel extreem snel convergeert (er zijn slechts enkele termen nodig voor een hoge precisie).

Met deze methode berekende Machin 100 decimalen. Deze familie van formules bleef tot in het vroege computertijdperk de standaardmethode om records te breken. Varianten hierop werden onder andere gebruikt door Carl Friedrich Gauss en William Shanks. Shanks berekende in 1873 met de hand 707 decimalen, waarvan later (met de eerste mechanische rekenmachines) bleek dat de eerste 527 correct waren.

Iteratieve methoden Met de opkomst van de elektronische computer in de 20e eeuw ontstond de behoefte aan algoritmes die sneller convergeren dan de traditionele reeksen. Waar Machin-achtige formules "lineair" convergeren (een vast aantal decimalen per term erbij), zijn er iteratieve methoden ontwikkeld met "kwadratische convergentie". Dit betekent dat het aantal correcte decimalen bij elke stap van het algoritme verdubbelt.

Algoritme van Gauss-Legendre (Brent-Salamin)

Dit algoritme werd onafhankelijk van elkaar herontdekt door Richard Brent en Eugène Salamin in 1976. Het algoritme is genoemd naar Carl Friedrich Gauss en Adrien-Marie Legendre die het eerder theoretisch uitgewerkt hadden, maar het nog niet konden toepassen.

Het algoritme begint met de volgende startwaarden:

Vervolgens worden in elke iteratie de volgende stappen herhaald:

De benadering voor na stappen wordt dan gegeven door:

De convergentie is extreem snel. Met minder dan 25 iteraties kan men al 45 miljoen decimalen van pi bepalen. Dit algoritme werd veel gebruikt voor supercomputer-berekeningen in de jaren 80 en 90.

Formules met superconvergentie De huidige wereldrecords voor het aantal decimalen van pi (in de orde van grootte van biljoenen decimalen) worden berekend met reeksen die gebaseerd zijn op de theorie van modulaire vormen. Deze reeksen convergeren nog veel sneller dan de iteratieve methoden en zijn goed geschikt voor parallellisatie op moderne hardware.

Ramanujan-formules In 1914 publiceerde de Indiase wiskundige Srinivasa Ramanujan een aantal bijzondere reeksen voor . Deze formules convergeren extreem snel; vaak leveren ze 8 decimalen per extra term op. Een van zijn bekendste formules is:

Omdat het wiskundige bewijs voor deze formules destijds ontbrak en steunde op complexe theorieën over elliptische functies, duurde het tot de jaren 80 voordat hun potentieel voor computerberekeningen volledig werd benut.

Chudnovsky-algoritme De gebroeders David en Gregory Chudnovsky publiceerden in 1988 een formule die gebaseerd is op de ideeën van Ramanujan, maar nog efficiënter is. Dit algoritme levert ongeveer 14 decimalen per term op:

Dit is het standaardalgoritme dat wordt gebruikt door software zoals y-cruncher om moderne wereldrecords te vestigen.

Spigot-algoritmes Een bijzondere klasse van algoritmes zijn de zogenaamde "spigot-algoritmes" (kraan-algoritmes). In tegenstelling tot traditionele methoden, die vaak alle voorgaande stappen in het geheugen moeten houden om het eindresultaat te geven, kunnen spigot-algoritmes cijfers produceren als een continue stroom.

Bailey-Borwein-Plouffe (BBP)

In 1995 werd een formule ontdekt door Simon Plouffe, samen met David Bailey en Peter Borwein, die het mogelijk maakt om het -de cijfer van pi (in het hexadecimale of binaire stelsel) te berekenen zonder de voorgaande cijfers te hoeven berekenen:

Dit was een verrassende ontdekking, omdat men lange tijd dacht dat dit onmogelijk was. Het algoritme is zeer efficiënt qua geheugengebruik.

Rabinowitz-Wagon Voor decimale cijfers bestaat er ook een spigot-algoritme, ontwikkeld door Stanley Rabinowitz en Stan Wagon. Dit algoritme produceert decimalen een voor één, maar heeft in tegenstelling tot de BBP-formule wel steeds meer geheugen nodig naarmate men verder komt in de reeks.

Monte-Carlo en probabilistische methoden Pi kan ook benaderd worden door middel van kansexperimenten. Deze methoden, vaak Monte-Carlosimulaties genoemd, zijn vooral van educatieve waarde omdat de convergentie extreem traag is (om de nauwkeurigheid met een decimaal te verbeteren, is een honderdvoudiging van het aantal steekproeven nodig).

Naald van Buffon Het naaldexperiment van Buffon is een klassiek meetkundig kansexperiment. Men laat een naald met lengte vallen op een vlak met evenwijdige lijnen die op afstand van elkaar liggen (waarbij ). De kans dat de naald een lijn raakt is:

Door het experiment vaak te herhalen en de fractie van de "raakworpen" te tellen, kan worden geschat.

Monte-Carlo-cirkelmethode thumb|150x150px Men neemt een vierkant met zijde 2 en schrijft daarin een cirkel (met straal 1). De oppervlakte van het vierkant is 4 en de oppervlakte van de cirkel is . Wanneer men willekeurige punten in het vierkant "gooit", zal de verhouding tussen het aantal punten in de cirkel () en het totaal aantal punten () bij benadering gelijk zijn aan de verhouding van de oppervlaktes:

Integralen en numerieke analyse Tot slot kan pi worden bepaald met methoden uit de numerieke wiskunde (numerieke integratie of kwadratuur). Men berekent dan de waarde van een integraal waarvan de exacte uitkomst pi bevat, bijvoorbeeld:

Of:

Door algoritmes zoals de Regel van Simpson of Gauss-kwadratuur (zoals Gauss-Kronrod) toe te passen, kan de waarde numeriek worden benaderd. Hoewel educatief nuttig, zijn deze methoden in de praktijk minder efficiënt dan de gespecialiseerde iteratieve algoritmes zoals Brent-Salamin of Chudnovsky.

Categorie:Algoritme