Iteracje Bailey – Borwein – Plouffe
Widzieliśmy kilka wyzwań dotyczących pi na PPCG, ale żadne z nich nie dyktuje algorytmu, którego powinieneś używać. Chciałbym zobaczyć implementacje algorytmu Bailey – Borwein – Plouffe w dowolnym języku do iteracji n
. Wzór jest następujący:
Twój algorytm powinien wypisywać każdą iterację do n, pokazując sumy pośrednie, a także końcowy wynik, aby utworzyć „piangle”. Możesz także użyć zredukowanej postaci wielomianowej algorytmu pokazanej na stronie wikipedii. Przykład uruchomienia dla n=50
pokazano poniżej:
3
3.1
3.14
3.141
3.1415
3.14159
3.141592
3.1415926
3.14159265
3.141592653
3.1415926535
3.14159265358
3.141592653589
3.1415926535897
3.14159265358979
3.141592653589793
3.1415926535897932
3.14159265358979323
3.141592653589793238
3.1415926535897932384
3.14159265358979323846
3.141592653589793238462
3.1415926535897932384626
3.14159265358979323846264
3.141592653589793238462643
3.1415926535897932384626433
3.14159265358979323846264338
3.141592653589793238462643383
3.1415926535897932384626433832
3.14159265358979323846264338327
3.141592653589793238462643383279
3.1415926535897932384626433832795
3.14159265358979323846264338327950
3.141592653589793238462643383279502
3.1415926535897932384626433832795028
3.14159265358979323846264338327950288
3.141592653589793238462643383279502884
3.1415926535897932384626433832795028841
3.14159265358979323846264338327950288419
3.141592653589793238462643383279502884197
3.1415926535897932384626433832795028841971
3.14159265358979323846264338327950288419716
3.141592653589793238462643383279502884197169
3.1415926535897932384626433832795028841971693
3.14159265358979323846264338327950288419716939
3.141592653589793238462643383279502884197169399
3.1415926535897932384626433832795028841971693993
3.14159265358979323846264338327950288419716939937
3.141592653589793238462643383279502884197169399375
3.1415926535897932384626433832795028841971693993751
3.14159265358979323846264338327950288419716939937510
Dokładność każdej iteracji powinna być równa wartości n
przekazywanej do algorytmu, to znaczy, że każda iteracja powinna obliczyć liczbę pi do wartości przekazanej n
dla wszystkich k
.
Zasady:
- Wbudowane nie są dozwolone, nie
pi
trzeba też używać formuły. - Musisz wspierać
n
maksymalnie maksymalną dozwoloną przez Twój język liczbę obliczeń16^n
. Jeśli dane wejściowe powodują przepełnienie arytmetyczne podczas obliczeń pox<n
wykonaniu, ponieważ Twój język obsługuje tylko liczby dziesiętne do2^32-1
, jest to w porządku. Wszelkie inne założenian
nie są w porządku. - ty musi złożyć wyjaśnienie, w jaki sposób masz wyjścia, jeśli nie jest to oczywiste. Na przykład, jeśli piszesz w języku golfowym, podział jest wymagany w 100%. Ma to na celu upewnienie się, że korzystasz z określonego algorytmu.
- Standardowe otwory na pętle są niedozwolone.
- To jest golf golfowy, tutaj wygrywa najmniejsza liczba bajtów.
Kod referencyjny (kod użyty do wygenerowania przykładu):
public static void main(String[] args) {
(0..50).each {
n->
def x=(0..n).collect {
j->
def k=new BigDecimal(j)
def s={it.setScale(n)}
def a=s(1.0g).divide(s(16.0g)**s(k))
def b=s(4.0g)/(s(8.0g)*s(k)+s(1.0g))
def c=s(2.0g)/(s(8.0g)*s(k)+s(4.0g))
def d=s(1.0g)/(s(8.0g)*s(k)+s(5.0g))
def e=s(1.0g)/(s(8.0g)*s(k)+s(6.0g))
def f=a*(b-c-d-e)
}.sum()
println(n + "\t" + x.setScale(n, BigDecimal.ROUND_DOWN))
}
}
Ta implementacja kończy się na n=255
, możesz zmniejszyć na mniej lub więcej.
Wdrożenie zostało wykonane w Groovy.
Calculate foo via x method
wyzwań.Odpowiedzi:
05AB1E ,
635250 bajtówFormuła specjalizacji
Wypróbuj online!
Formuła BBP
Wypróbuj online!
źródło
Python 2,
109108 bajtówPrzetestuj na Ideone .
źródło
Python 2, 174 bajtów
Człowieku, to czas, w którym chciałbym, aby Python miał łatwiejszy sposób na zachowanie nieskończonej precyzji dziesiętnych. Możliwe, że wdrożenie własnego typu nieskończonej dokładności dla tego wyzwania jest krótsze, ale nie wyobrażam sobie, jak to zrobić. Formuła jest napisana dosłownie.
Przykładowe dane wyjściowe dla
n=100
(z dodanymi numerami wierszy):Wydaje się, że działa to dla większych liczb,
n=1000
działa w ciągu kilku sekund in=10000
nie wydaje mi się, że jeszcze popełniłem żadnych błędów!źródło
Haskell,
101100 bajtówDzięki @nimi za bajt.
Prosta implementacja. Oblicza
n
do 15 cyfr (standardowa podwójna precyzja).źródło
l<-[8*fromIntegral k]
zamiastlet ...
zapisuje bajt.J,
736462 bajtówPowoduje to wyprowadzenie każdego przybliżenia do n cyfr jako sformatowanego łańcucha. Wykorzystuje to wielomianowe uproszczenie formuły i otrzymuje pierwsze n cyfr, mnożąc sumę przez potęgę 10, dzieląc ją i dzieląc przez tę samą potęgę 10.
Dane wejściowe są traktowane jako rozszerzona liczba całkowita, co oznacza, że racjonalne są używane, gdy zachodzi podział, który zapewnia dokładne wyniki.
Stosowanie
Jest to wynik dla n = 100, pokazujący skumulowane sumy dla k w [0, 100].
Wyjaśnienie
Najpierw wykonaj zakres [0, n ], pokazany dla n = 5
Pomnóż każdy przez 8
Utwórz tabelę dodatków pomiędzy
[1, 4, 5, 6]
i produktami za pomocą 8Podziel każdy wiersz przez
[4, 2, -1, 1]
Następnie zmniejsz kolumny od dołu do góry za pomocą odejmowania
Podziel każde 16 k dla k w [0, n ] przez każdy wynik
Znajdź skumulowane sumy
Oblicz 10 k dla k w [0, n ] i pomnóż je przez każdy
Następnie podłóż każdy z produktów
Podziel go przez tę samą moc 10, aby uzyskać wyniki
źródło
PARI / GP, 86 bajtów
Lub bez przecinka dziesiętnego w 69 bajtach :
Zamiast dzielenia przez 16 k każdej iteracji poprzednia wartość p jest pomnożona przez 16 . Piętro p ÷ (8/5) k jest wówczas wartością π obciętą do prawidłowej liczby cyfr.
Przykładowe użycie
źródło
C GCC, 118 bajtów
Gra w golfa:
Nie golfowany:
Aby zmienić n, wystarczy zmienić while (k <15) na while (k <n)
wynik:
maksymalna precyzja to 15 miejsc po przecinku, mógłbym zwiększyć dowolną wartość za pomocą gmp, ale może następnego dnia pi: P
z ładnym nadrukiem, 143 bajty
Gra w golfa:
Nie golfowany:
wynik:
źródło
Formuła IBM / Lotus Notes, 125 bajtów
Formuła w polu obliczeniowym z innym polem o nazwie „a” dla danych wejściowych.
Zasadniczo port algorytmu z odpowiedzi Pythona z @shebang. Oblicza do 15 cyfr, po których obcina się z powodu ograniczenia języka (patrz dane wyjściowe). Musiałem zmarnować 12 bajtów z instrukcją @If na końcu, aby się pozbyć. po 3 na starcie: - /
Nie golfił
źródło
C #, 183 bajtów
Gra w golfa:
Nie golfowany:
źródło
3.14159265358979
zn >= 14
powodu podwójnej precyzji?APL (NARS), 206 znaków, 412 bajtów
Znajduje to approssimation w dużych wymiernych, niż użyć jednej funkcji, która przekształca duże wymierne w ciąg liczbowy ... test:
źródło