Oto wyniki kolejnego benchmarku Compute Pi.
Przetestowaliśmy dziesięć algorytmów obejmujących ponad dwa tysiące lat historii — od Archimedesa po Chudnovsky’ego — używając biblioteki MPFR w języku C.
Główny wniosek jest następujący: różnice w wydajności wynikają wyłącznie z matematyki, a nie z jakości kodu.
Algorytmy liniowe, takie jak metoda Newtona czy Machina, dodają stałą liczbę cyfr w każdej iteracji. Algorytmy kwadratowe, takie jak Gaussa-Legendre’a i Borweina, podwajają liczbę poprawnych cyfr przy każdym kroku.
Aby obliczyć dziesięć tysięcy cyfr liczby Pi, algorytm Chudnovsky’ego potrzebuje siedmiuset iteracji. Gauss-Legendre potrzebuje zaledwie dziewiętnastu. To czyni go ponad pięćset razy szybszym.
Dla wysokiej precyzji zbieżność kwadratowa to nie przewaga — to konieczność.
Slajdy:
Oto prezentacja video z treścią po polsku.
Koniec.