Diese Herausforderung besteht darin, schnellen Code zu schreiben, der eine rechnerisch schwierige unendliche Summe ausführen kann.
Eingang
Eine n
By- n
Matrix P
mit ganzzahligen Einträgen, die kleiner als der 100
absolute Wert sind. Beim Testen gebe ich gerne Eingaben für Ihren Code in jedem sinnvollen Format ein, das Ihr Code benötigt. Die Standardeinstellung ist eine Zeile pro Zeile der Matrix, die durch Leerzeichen getrennt und in der Standardeingabe angegeben ist.
P
wird positiv bestimmt sein, was impliziert, dass es immer symmetrisch sein wird. Ansonsten muss man nicht wirklich wissen, was positives Bestimmtes bedeutet, um die Herausforderung zu beantworten. Dies bedeutet jedoch, dass tatsächlich eine Antwort auf die unten definierte Summe erfolgt.
Sie müssen jedoch wissen, was ein Matrixvektorprodukt ist.
Ausgabe
Ihr Code sollte die unendliche Summe berechnen:
innerhalb von plus oder minus 0,0001 der richtigen Antwort. Hier Z
ist die Menge der ganzen Zahlen und damit Z^n
alle möglichen Vektoren mit n
ganzzahligen Elementen und e
ist die berühmte mathematische Konstante , die ungefähr 2,71828 entspricht. Beachten Sie, dass der Wert im Exponenten einfach eine Zahl ist. Unten finden Sie ein explizites Beispiel.
In welcher Beziehung steht dies zur Riemann-Theta-Funktion?
In der Notation dieser Arbeit zur Approximation der Riemannschen Theta-Funktion versuchen wir zu berechnen . Unser Problem ist aus mindestens zwei Gründen ein Sonderfall.
- Wir setzen den
z
im verlinkten Paper aufgerufenen Initialparameter auf 0. - Wir erstellen die Matrix
P
so, dass die minimale Größe eines Eigenwertes ist1
. (Siehe unten, wie die Matrix erstellt wird.)
Beispiele
P = [[ 5., 2., 0., 0.],
[ 2., 5., 2., -2.],
[ 0., 2., 5., 0.],
[ 0., -2., 0., 5.]]
Output: 1.07551411208
Lassen Sie uns im Detail nur einen Begriff in der Summe für dieses P sehen. Nehmen Sie zum Beispiel nur einen Begriff in der Summe:
und x^T P x = 30
. Beachten Sie, dass dies wichtig e^(-30)
ist 10^(-14)
und daher unwahrscheinlich ist, um die richtige Antwort auf die angegebene Toleranz zu erhalten. Denken Sie daran, dass die unendliche Summe tatsächlich jeden möglichen Vektor der Länge 4 verwendet, bei dem die Elemente ganze Zahlen sind. Ich habe nur eines ausgewählt, um ein explizites Beispiel zu nennen.
P = [[ 5., 2., 2., 2.],
[ 2., 5., 4., 4.],
[ 2., 4., 5., 4.],
[ 2., 4., 4., 5.]]
Output = 1.91841190706
P = [[ 6., -3., 3., -3., 3.],
[-3., 6., -5., 5., -5.],
[ 3., -5., 6., -5., 5.],
[-3., 5., -5., 6., -5.],
[ 3., -5., 5., -5., 6.]]
Output = 2.87091065342
P = [[6., -1., -3., 1., 3., -1., -3., 1., 3.],
[-1., 6., -1., -5., 1., 5., -1., -5., 1.],
[-3., -1., 6., 1., -5., -1., 5., 1., -5.],
[1., -5., 1., 6., -1., -5., 1., 5., -1.],
[3., 1., -5., -1., 6., 1., -5., -1., 5.],
[-1., 5., -1., -5., 1., 6., -1., -5., 1.],
[-3., -1., 5., 1., -5., -1., 6., 1., -5.],
[1., -5., 1., 5., -1., -5., 1., 6., -1.],
[3., 1., -5., -1., 5., 1., -5., -1., 6.]]
Output: 8.1443647932
P = [[ 7., 2., 0., 0., 6., 2., 0., 0., 6.],
[ 2., 7., 0., 0., 2., 6., 0., 0., 2.],
[ 0., 0., 7., -2., 0., 0., 6., -2., 0.],
[ 0., 0., -2., 7., 0., 0., -2., 6., 0.],
[ 6., 2., 0., 0., 7., 2., 0., 0., 6.],
[ 2., 6., 0., 0., 2., 7., 0., 0., 2.],
[ 0., 0., 6., -2., 0., 0., 7., -2., 0.],
[ 0., 0., -2., 6., 0., 0., -2., 7., 0.],
[ 6., 2., 0., 0., 6., 2., 0., 0., 7.]]
Output = 3.80639191181
Ergebnis
Ich werde Ihren Code auf zufällig ausgewählten Matrizen P von zunehmender Größe testen.
Ihre Punktzahl ist einfach die größte, n
für die ich in weniger als 30 Sekunden eine korrekte Antwort erhalte, wenn der Durchschnitt über 5 Läufe mit zufällig ausgewählten Matrizen P
dieser Größe ermittelt wird.
Was ist mit einer Krawatte?
Bei Gleichstand gewinnt derjenige, dessen Code im Durchschnitt über 5 Läufe am schnellsten abläuft. Für den Fall, dass diese Zeiten auch gleich sind, ist der Gewinner die erste Antwort.
Wie wird die zufällige Eingabe erstellt?
- Sei M eine zufällige m mal n-Matrix mit m <= n und Einträgen, die -1 oder 1 sind. In Python / numpy
M = np.random.choice([0,1], size = (m,n))*2-1
. In der Praxis werde ichm
ungefähr seinn/2
. - Sei P die Identitätsmatrix + M ^ T M. In Python / numpy
P =np.identity(n)+np.dot(M.T,M)
. Wir sind jetzt garantiert, dassP
positiv definitiv ist und die Einträge in einem geeigneten Bereich liegen.
Beachten Sie, dass dies bedeutet, dass alle Eigenwerte von P mindestens 1 sind, was das Problem möglicherweise einfacher macht als das allgemeine Problem der Approximation der Riemann-Theta-Funktion.
Sprachen und Bibliotheken
Sie können eine beliebige Sprache oder Bibliothek verwenden. Zum Zwecke der Bewertung werde ich jedoch Ihren Code auf meinem Computer ausführen. Geben Sie daher bitte klare Anweisungen für die Ausführung unter Ubuntu.
Mein Computer Die Timings werden auf meinem Computer ausgeführt. Dies ist eine Standard-Ubuntu-Installation auf einem 8-GB-AMD FX-8350-Prozessor mit acht Kernen. Dies bedeutet auch, dass ich in der Lage sein muss, Ihren Code auszuführen.
Führende Antworten
n = 47
in C ++ von Ton Hospeln = 8
in Python von Maltysen
quelle
x
von[-1,0,2,1]
. Können Sie das näher erläutern? (Hinweis: Ich bin kein Mathe-Guru)Antworten:
C ++
Kein naiverer Ansatz. Nur innerhalb des Ellipsoids auswerten.
Verwendet die Bibliotheken Armadillo, ntl, gsl und pthread. Installieren Sie mit
Kompilieren Sie das Programm mit etwas wie:
Auf einigen Systemen können Sie hinzufügen müssen
-lgslcblas
nach-lgsl
.Führen Sie mit der Größe der Matrix aus, gefolgt von den Elementen in STDIN:
matrix.txt
:Oder versuchen Sie es mit einer Genauigkeit von 1e-5:
infinity.cpp
:quelle
-lgslcblas
Flag zum Kompilieren. Erstaunliche Antwort übrigens!Python 3
12 Sekunden n = 8 auf meinem Computer, Ubuntu 4 Core.
Wirklich naiv, habe keine Ahnung, was ich tue.
Dadurch wird die Reichweite so lange erhöht
Z
, bis eine ausreichende Antwort vorliegt. Ich habe meine eigene Matrixmultiplikation geschrieben, sollte aber numpy verwenden.quelle