Pi mal e (oder Pie, wenn Sie mehrdeutige Notation mögen) auf 100 Dezimalstellen ist:
8.5397342226735670654635508695465744950348885357651149618796011301792286111573308075725638697104739439...
( OIES A019609 ) ( Argument für mögliche Irrationalität )
Ihre Aufgabe ist es, ein Programm zu schreiben, das eine positive ganze Zahl N aufnimmt und Pi * e auf N Dezimalstellen abgeschnitten ausgibt. zB wenn N = 2, dann sollte der Ausgang sein 8.53
.
Dies ist ein Optimierungsproblem, daher gewinnt die Übermittlung, die die richtige Ausgabe für den höchsten Wert von N liefern kann.
Um sicherzustellen, dass alle Einsendungen mit derselben Rechenleistung beurteilt werden, muss Ihr Code auf ideone ausgeführt werden und eine beliebige Sprache verwenden, die sie unterstützen. Gemäß der ideone-FAQ gibt es ein Laufzeitlimit von 5 Sekunden für nicht angemeldete Benutzer. Diese 5-Sekunden-Grenze müssen Sie verwenden, nicht die 15-Sekunden-Grenze für angemeldete Benutzer. ( Weitere Einschränkungen wie Speicher, Codegröße usw. finden Sie in der FAQ .)
Insbesondere sollte jeder, der nicht bei ideone angemeldet ist, in der Lage sein, Ihr Programm auf ideone für alle Werte von N von 1 bis zu einem maximalen Nmax auszuführen und fast immer die richtige Ausgabe zu sehen . ohne irgendwelche Time limit exceeded
oder Memory limit exceeded
usw. Fehler. Die Einreichung mit dem größten Nmax gewinnt.
(Ob die tatsächlich benötigte Zeit ein Smidge über 5 Sekunden ist, spielt keine Rolle, solange Ideone keine Fehler liefert. " Fast die ganze Zeit " wird als mehr als 95% der Zeit für ein bestimmtes N definiert.)
Einzelheiten
- Sie können eine beliebige mathematische Methode verwenden, um Pi * e zu berechnen, aber Sie dürfen die Ausgabe nicht über die ersten Dutzend Stellen von Pi, e oder Pi * e hinaus fest codieren .
- Ihr Programm sollte bei unbegrenzten Ressourcen für jedes N funktionieren können.
- Sie können eingebaute Pi oder e Konstanten verwenden, wenn Ihre Sprache diese hat.
- Sie dürfen nicht auf Websites oder Ressourcen außerhalb Ihres Codes zugreifen (sofern ideone dies überhaupt zulässt).
- Abgesehen von der Hardcodierung und dem Zugriff auf externe Ressourcen ist alles, was ideone zulässt, mit ziemlicher Sicherheit in Ordnung.
- Ihre Eingabe und Ausgabe muss (offensichtlich) mit dem Ideone funktionieren, das für I / O vorgesehen ist (nur stdin / stdout, wie es scheint). Es ist in Ordnung, wenn Sie Anführungszeichen um den Eingang N benötigen oder der Ausgang so etwas wie
ans = ...
usw. ist. - Bitte fügen Sie einen Link zu einem Ideone-Snippet Ihres Codes mit Ihrem Nmax als Eingabe hinzu.
- Wenn es ein Unentschieden gibt (nur wahrscheinlich, wenn mehrere Einsendungen die 64-KB-Ausgabezeichengrenze erreichen), gewinnt die Antwort mit den höchsten Stimmen.
quelle
Antworten:
Python - 65535
http://ideone.com/knKRhn
Ideone scheint nicht
gmpy2
installiert zu sein, was aus mindestens zwei Gründen bedauerlich ist. Erstens, weil es die Berechnung viel schneller machen würde, und zweitens, weil es jede Formel, die eine Quadratwurzel mit beliebiger Genauigkeit erfordert, unpraktisch macht.Die Formel, die ich für π verwende, wurde von Ramanujan als Formel (39) aufgeführt:
die mit einer Rate von ~ 5,89 Stellen pro Term konvergiert . Meines Wissens ist dies die am schnellsten konvergierende Reihe ihrer Art, für die keine Quadratwurzel mit beliebiger Genauigkeit ausgewertet werden muss. Formel (44) in dem gleichen Papier (Konvergenzrate ~ 7,98 Digits pro Term) wird am häufigsten als bezeichnen die Ramanujans Formel.
Die Formel, die ich für e verwende, ist die Summe der inversen Fakultäten. Die Anzahl der erforderlichen Terme wird mit Γ -1 ( 10 n ) berechnet , wobei eine Näherung verwendet wird, die ich bei mathoverflow gefunden habe . Die Lambert W 0 -Komponente wird nach der Newtonschen Methode gefunden.
Die Berechnung jeder dieser Summierungen erfolgt über die schnelle E-Funktionsbewertung (allgemein bekannt als binäre Aufteilung), die ursprünglich von Karatsuba entwickelt wurde. Das Verfahren reduziert eine Summation auf n Terme auf einen einzelnen rationalen Wert p / q . Diese beiden Werte werden dann multipliziert, um das Endergebnis zu erhalten.
Update: Die
Profilerstellung ergab, dass mehr als die Hälfte der für die Berechnung benötigten Zeit in der Endabteilung verbracht wurde. Es werden nur die obersten log 2 (10 n ) Bits von q benötigt, um die volle Genauigkeit zu erhalten, daher schneide ich vorher einige ab. Der Code füllt jetzt den Ideone-Ausgabepuffer in 3,33 Sekunden .
Update 2:
Da dies eine Optimierungsherausforderung ist , habe ich beschlossen, meine eigene Divisionsroutine zu schreiben, um die Langsamkeit von CPython zu bekämpfen. Die Implementierung von
divnr
oben verwendet Newton-Raphson Division . Die allgemeine Idee besteht darin, d = 1 / q · 2 n unter Verwendung der Newtonschen Methode zu berechnen , wobei n die Anzahl der Bits ist, die das Ergebnis benötigt, und das Ergebnis als p · d >> n zu berechnen . Die Laufzeit beträgt jetzt 2,87 Sekunden - und dies ohne Abhacken von Bits vor der Berechnung; es ist für diese Methode nicht notwendig.quelle
PARI / GP: 33000
Dies ist im Grunde das bei OEIS bereitgestellte Programm , das so geändert wurde, dass die Eingabe korrekt übernommen und formatiert wird. Es sollte als Basis dienen, um zu schlagen, wenn nichts anderes.
Ich gehe davon aus, dass dies korrekt ist. Ich habe es bei 100 und 20.000 gegen OEIS überprüft und es passte für beide. Es ist ziemlich schwierig, online weitere Ziffern zu finden, gegen die man prüfen kann.
Für 33.000 dauert es ungefähr 4,5 Sekunden, so dass es wahrscheinlich ein wenig gestoßen werden könnte. Ich habe es einfach satt, mit der Eingabe und der langsamen Submit / Compile / Run-Schleife von ideone herumzuspielen.
Ideone.com Link
quelle
Str(floor(frac(x)*10^m)
, geht es hunderte / tausende Male schneller.Python 3
Da die eingebauten pi und e nicht genügend Ziffern haben, habe ich beschlossen, meine eigenen zu berechnen.
IDEOne Link
Ausgabe für STDIN = 1000:
quelle
should be able to work for any N, given unlimited resources
Regel folgt . Der größte Teil der Ausgabe besteht aus Nullen bei etwa N = 10000.)NameError: name 'xrange' not defined
.Scala - 1790
IDEOne unter http://ideone.com/A2CIto .
Wir verwenden die Wetherfield-Formel für π (und den von hier grob portierten Machin- Formelcode ). Wir berechnen e mit den gewöhnlichen Potenzreihen.
quelle