Stap 12: Codering van Gauss formule
In onze vorige stap vonden we de formule:
Π/4=12*arctan(1/18) + 8*arctan(1/57) - 5*arctan(1/239)
We kunnen dit gemakkelijk omzetten in een functie in python als we aannemen dat we een arctangens-functie hebt gedefinieerd:
Nu moeten we een arctangens-functie maken. De snelste methode uit te voeren zou zijn om gebruik van de formule die we in stap 9 zagen:
arctan(x) = x - (x³/3) + (x⁵/5) - (x⁷/7) + (x⁹/9) - (x¹¹/11)...
echter zien als we alleen zijn berekening van arctans van getallen in de vorm van 1 / x het zinvoller te herdefiniëren van de formule als:
arctan(1/x) = (1 / x)-(1/3 x ³) + (1/5x⁵) - (1/7x⁷) + (1/9x⁹) - (1/11 x ¹¹)...
Dit geeft ons de volgende functie in Python:
Deze functie is een beetje meer gevorderd dan onze vorige functies zoals op niet de gebruiker vergen doet voor het invoeren van hoeveel herhalingen uit te voeren. In plaats daarvan het kijkt naar de waarde van getcontext () .prec en de kleinste waarde gezocht die het Python programma van nul onderscheiden kunt (bijvoorbeeld als getcontext () .prec = 2 dan de kleinste waarde Python van 0 onderscheiden kunt 0.1 is).
Het vergelijkt vervolgens de waarde van de vorige zittingsperiode in de volgorde: als het kleiner is dan de kleinste waarde python van 0 onderscheiden kunt, dan geen zin voort te zetten heeft zodat het programma stopt.
Als we de twee functies samen te stellen krijgen we het volgende programma (gauss_pi_method.py):
Als je dit om te zoeken naar 10.000 cijfers van π uitvoeren duurt het minder dan een minuut. Op mijn computer kostte het 17 seconden. Dat is veel beter dan de vorige beste programma we hadden, enerzijds op basis van de veelhoek-methode, die 43 seconden nam op mijn computer voor het berekenen van 100 cijfers van π.
Echter kunnen we veel beter met behulp van dezelfde functie voor het berekenen van π als we arctan(1/x) sneller kunnen berekenen.
Gelukkig, Euler kwam met een manier om enkel dat te doen:
arctan(1/x) = (x / (1 + x²)) + ((2 * x) / (3*(1+x²)²)) + ((2 * 4 * x) / (3*5*(1+x²)³)) + ((2 * 4 * 6 * x) / (3*5*7*(1+x²)⁴)) +...
De nth term in deze serie wordt gegeven door de functie f(n):
f(n) = f(n-1) * (2 * n) / ((2*n+1)*(1+x²))
waar is de eerste termijn (x / (1 + x²))
Zodat de code sneller lopen kunnen we berekenen 1 + x² voordat de lus zodat we slechts eenmaal berekenen. De geactualiseerde code (gauss_pi_method_accelerated_arctan.py) is:
Deze code duurde iets meer dan een halve seconde voor het berekenen van π tot 10.000 cijfers, dat is ongeveer 30 keer sneller dan vóór!
Er is een handige truc om de code nog sneller te maken. Tot nu toe hebben we met behulp van de decimale library in Python. Als we de berekeningen met behulp van gehele getallen doen zal het wel veel sneller. Om dit te doen we eerst vermenigvuldigt u de waarde voor de beginkleur met een grote macht van 10 en later, wanneer we het resultaat gebruiken willen, we het indelen door dat dezelfde macht van 10. Hier is hoe de code eruit ziet (gauss_pi_method_fixed_point.py):
Deze versie van de code berekend 10.000 decimalen van π in slechts 0,26 seconden, dat is bijna twee keer zo snel als de vorige methode!