Algorytmy liczące Pi w Pythonie

Dzisiaj będzie o długich licz­bach. Wiedzie­li­ście, że Python w stałej Pi zawiera tylko 48 cyfr po prze­cinku? (a przy­naj­mniej wersja 2.6) 3.141592653589793 (odtąd błęd­nie) 115997963468544185161590576171875. To stanow­czo za mało! Tyle to ja liczy­łem na liczy­dle w przed­szkolu A ja chciał­bym wiedzieć jaka jest liczba pięcio­ty­sięczna po prze­cinku ;-) Zade­mon­struję 3 metody licze­nia liczby Pi.

Od razu mówię, nie pytaj­cie mnie o nic w związku z tymi meto­dami, bo zazwy­czaj rozu­miem tylko wstęp i pierw­szy wzór z opisu.

I. Metoda Wallisa
Posłu­żymy się takim fajnym tworem jak gene­ra­tor (yield w pętli zamiast return)

def wallisFormulaGenerator(counterMax):
   counter = 0
   while(counter <= counterMax):
      counter += 1
      yield (4*(counter**2))/(4*(counter**2)-1)       
 
def gimmePiBaby(loops):
   result = 1
   for value in wallisFormulaGenerator(loops):
      result *= value
      return 2*result
 
print(gimmePiBaby(10000))

Ta metoda jest najsłab­sza, po 18 obro­tach mamy dopiero 3.1, po 492 3.14, a dopiero po 8476 3.1415.

II. Metoda Leib­nitza
W moim przy­padku mocno oszu­kana ta metoda, ale działa popraw­nie. I dużo szybciej!

minus = True
partial = 1
denominator = 3
for i in range(100000):
   if minus:
      partial -= 1/denominator
      minus = False
   else:
      partial += 1/denominator
      minus = True
   denominator += 2
   result = 4 * partial

Jest lepiej, obli­cze­nia wyko­ny­wały się 3x szyb­ciej niż poprzednio.

III. Metoda Abra­hama Sharpa
Najwy­daj­niej­sza z wyżej przed­sta­wio­nych. Na pewno są wydaj­niej­sze, ale dla okre­śle­nia liczby nr 5000 wystar­czy. Aby wypi­sać tyle liczb ile nas inte­re­suje, zwykły obiekt typu float nie wystar­czy, potrze­bu­jemy biblio­teki BigFloat. Niestety nie daje się zain­sta­lo­wać z wersją 3 Pythona mimo użycia 2to3, więc pozo­staje wbudo­wane w Ubuntu 2.6.

import bigfloat
with bigfloat.precision(17000):
   minus = True
   partial = bigfloat.BigFloat(1)
   denominator = 3
   for i in range(1, 500000):
      if minus:
         partial -= (1/((bigfloat.pow(3,i))*denominator))
         minus = False
      else:
         partial += (1/((bigfloat.pow(3,i))*denominator))
         minus = True
      denominator += 2
   result = 6 * ((1/bigfloat.sqrt(3)) * partial)

Mój procek za 45zł 500 000 obro­tów wyko­nał w 2339 sek., a dzisiej­szy wpis spon­so­ruje cyferka 1 będąca warto­ścią pięcio­ty­sięczną po przecinku.

Mam nadzieję, że chociaż gimna­zja­li­stom algo­rytmy się przydadzą…

Podobne wpisy:

  1. Śpie­chu liczy zawar­tość alko­holu w drinkach
  2. Stacja Soko­łów „ANATUM” w Ustroniu
  3. PHPowe cieka­wostki składniowe
  4. Nowa stara książka i inte­re­su­jąca zniżka 25% w Matrasie

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany.

Możesz użyć następujących tagów oraz atrybutów HTML-a: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <p> <pre lang="" line="" escaped=""> <q cite=""> <strike> <strong>