Bei einer positiven Ganzzahl n wird die Summe der ersten n Dezimalstellen des Bruchteils von π n ausgegeben .
Beispiel Ein- und Ausgänge:
1 → 1
2 → 14
3 → 6
4 → 13
5 → 24
50 → 211
500 → 2305
5000 → 22852
Eingebaute Funktionen, die Ziffern von π berechnen oder entweder Potenzreihen oder fortgesetzte Brüche auswerten, sind nicht zulässig. Standard-Schlupflöcher gelten . Die Ein- / Ausgabe kann in einem praktischen Format erfolgen (stdin, stdout, Funktion in / output usw.).
Kürzester Code in Bytes gewinnt.
code-golf
math
arithmetic
pi
orlp
quelle
quelle
Antworten:
Python - 191 Bytes
~ 4x schnellere Version - 206 Bytes
Die Eingabe erfolgt aus stdin. Die Ausgabe für n = 5000 dauert mit dem zweiten Skript ca. 14 Sekunden (mit dem ersten Skript ca. 60 Sekunden).
Beispielnutzung:
Die verwendete Formel lautet wie folgt:
wo A n ist die n - te Alternating Anzahl , die formal als die Anzahl der alternierenden Permutationen auf einem Satz von Größe definiert werden kann n (siehe auch: A000111 ). Alternativ kann die Sequenz als die Zusammensetzung der Tangentenzahlen und Sekantenzahlen ( A 2n = Sn , A 2n + 1 = Tn ) definiert werden, dazu später mehr.
Der kleine Korrekturfaktor c n konvergiert schnell gegen 1, wenn n groß wird, und ist gegeben durch:
Für n = 1 bedeutet dies die Auswertung der Leibniz-Reihe . Annähern π als 10 ½ , kann die Anzahl der Begriffe erforderlich wie folgt berechnet:
die konvergiert (aufgerundet) auf 17 , obwohl kleinere Werte von n wesentlich mehr erfordern.
Für die Berechnung von A n gibt es mehrere Algorithmen und sogar eine explizite Formel, aber alle von ihnen durch quadratische sind n . Ich habe ursprünglich eine Implementierung von Seidels Algorithmus codiert , aber es wird zu langsam, um praktisch zu sein. Für jede Iteration muss ein zusätzlicher Term gespeichert werden, und der Betrag der Terme nimmt sehr schnell zu (die "falsche" Art von O (n 2 ) ).
Das erste Skript verwendet eine Implementierung eines Algorithmus, der ursprünglich von Knuth und Buckholtz angegeben wurde :
Obwohl nicht explizit angegeben, berechnet dieser Algorithmus gleichzeitig die Tangentenzahlen und die Sekantenzahlen. Das zweite Skript verwendet eine Variation dieses Algorithmus von Brent und Zimmermann , die je nach Parität von n entweder T oder S berechnet . Die Verbesserung ist quadratisch um n / 2 , daher die Verbesserung der Geschwindigkeit um das Vierfache.
quelle
Python 2, 246 Bytes
Ich habe eine ähnliche Herangehensweise an meine Antwort bei π mit quadratischer Konvergenz berechnen . Die letzte Zeile nimmt die N-te Potenz von pi und summiert die Ziffern. Der N = 5000-Test dauert ungefähr eine Minute.
Einige Tests:
Der ungolfed Code:
quelle
a=j
undp=j
zua=p=j
iirc. Könnte sein.Pyth, 33
Basierend auf dieser Antwort von isaacg . Könnte wahrscheinlich mehr Golf gespielt werden. Schleppend.
quelle