Schreiben Sie ein GOLF- Assembly-Programm, das eine Ganzzahl aus stdin (gefolgt von einer nachgestellten Newline) liest und die durch Newlines getrennten Primfaktoren ausgibt, gefolgt von einer nachgestellten Newline auf stdout.
Die Primfaktoren müssen nicht in einer bestimmten Reihenfolge sein. 1
ist kein Hauptfaktor.
Ihre GOLF- Binärdatei (nach dem Zusammenbau) muss in 8192 Bytes passen.
Ihr Programm wird durch zehnmaliges Ausführen mit einer der folgenden Eingaben bewertet:
8831269065180497
2843901546547359024
6111061272747645669
11554045868611683619
6764921230558061729
16870180535862877896
3778974635503891117
204667546124958269
16927447722109721827
9929766466606501253
Diese Zahlen sind grob nach Schwierigkeitsgraden sortiert. Die erste sollte durch die Teilung des Verfahrens leicht lösbar sein.
Die Optimierung in Richtung dieser Menge von Zahlen widerspricht dem Sinn der Frage. Ich kann die Menge von Zahlen jederzeit ändern. Ihr Programm muss für alle positiven 64-Bit-Eingabenummern funktionieren, nicht nur für diese.
Ihre Punktzahl ist die Summe der CPU-Zyklen, die zur Faktorisierung der oben genannten Zahlen verwendet werden.
Da GOLF sehr neu ist, füge ich hier einige Hinweise ein. Sie sollten die GOLF- Spezifikation mit allen Anweisungen und Zykluskosten lesen . Im Github-Repository finden Sie Beispielprogramme. Schauen Sie sich insbesondere das Beispielprogramm für Fakultäten an , das die Eingabe / Ausgabe demonstriert.
Kompilieren Sie Ihr Programm durch Ausführen in eine Binärdatei python3 assemble.py your_source.golf
. Führen Sie dann Ihr Programm mit aus python3 golf.py your_source.bin
, dies sollte auch die Zykluszahl ausgeben. Zeigen Sie die Werte des Registerinhalts beim Programmende mit dem -d
Flag an - verwenden Sie --help
diese Option, um alle Flags anzuzeigen.
1
es sich nicht um einen Primfaktor handelt, sollte nur die ganze Zahl ausgegeben werden?Antworten:
2.279.635 Zyklen - 7373 Bytes (deterministisch)
Einer nach dem anderen:
Zusammenfassung:
Ich verwende eine Kombination aus Testdivision und dem Brent-Pollard-Rho-Algorithmus zur Faktorisierung und Tabellensuche sowie Miller-Rabin für Primärtests. Ich werde morgen eine Erklärung hinzufügen.
Beachten Sie, dass die zweite Datentabelle aufgrund der Zeichenbeschränkung der Postlänge abgeschnitten wird. Diese Übersicht enthält die vollständige Tabelle.
quelle
mov o, 42
ist ein totes Werbegeschenk.Insgesamt 36.757.269.913 Zyklen
830B zusammengebaut
Faktorisierung durch Versuchsaufteilung mit einigen Optimierungen. Wahrscheinlich nicht die schnellste, aber wie noch niemand geschrieben hat, werde ich loslegen.
Volle Ausgabe aus meiner Timing-Schleife, falls jemand die Ergebnisse und / oder mein Copy-Paste und Mathe überprüfen möchte.
quelle
divu
: stackoverflow.com/questions/5558492/… . Wie für Ihre Antwort - diese Frage gedacht war nicht Probedivision gelöst werden: Pfactor * factor < number
- keine Zahl Faktoren größer als die Quadratwurzel haben darf.Score = 378.867.816 Zyklen
[randomisiert - Ihre Ergebnisse können variieren]
Verwendet den Miller-Rabin-Primalitätstest (eine deterministische Version, die bis zu 2 ^ 64 verarbeiten kann), ein bisschen Trial-Factoring und ECM Factoring. Alle algebraischen Operationen sind enthalten, einschließlich der modularen Addition, Subtraktion, Multiplikation, Exponentiation und Inversion (mod n <2 ^ 64).
Die modulare Multiplikation ist suboptimal - sie führt eine binäre Suche nach dem Quotienten durch. Das Berechnen des verbleibenden Teils einer 128 mal 64-Teilung ist ohne einen passenden eingebauten Befehl schwierig. Beschleunigen Sie das und das Ganze wird schneller gehen.
2290 Bytes kompiliert
Ausgabe:
quelle