Finde magische Zahlen C ++

Diese Frage bezieht sich im Wesentlichen auf die Verifizierung der Collatz-Vermutung bis zu 5B.

Ich denke, der Schlüssel hier ist, dass wir für jede Nummer n prüfen, um das optimistische Szenario und das pessimistische Szenario zu sehen, und um das optimistische zu überprüfen, bevor wir zum pessimistischen zurückkehren.

Im optimistischen Szenario ändern wir n entsprechend n / 2; 3n + 1 Regel, die Reihenfolge der Zahlen wird:

• in einer endlichen Anzahl von Schritten wird kleiner als n (in diesem Fall können wir überprüfen, was wir über diese kleinere Zahl wissen).

• verursacht keinen Überlauf in den Schritten.

(worauf, wie TonyK richtig bemerkt, wir uns nicht verlassen können (nicht einmal auf den ersten)).

Für das optimistische Szenario können wir die folgende Funktion verwenden:

Beachten Sie Folgendes:

1. Die Funktion versucht nur, die Vermutung für die empfangene Nummer zu verifizieren. Wenn es true zurückgibt, wurde es verifiziert. Wenn es false zurückgibt, heißt das nur, dass es nicht verifiziert wurde (d. H. Es bedeutet nicht, dass es widerlegt wurde).

2. Er nimmt einen Parameter max_tries und prüft nur bis zu dieser Anzahl von Schritten. Wenn die Anzahl überschritten wurde, versucht es nicht zu erkennen, ob dies Teil einer Endlosschleife ist oder nicht - es gibt nur zurück, dass die Überprüfung fehlgeschlagen ist.

3. Es dauert ein unordered_set bekannter Zahlen, die fehlgeschlagen sind (wenn die Collatz-Vermutung wahr ist, ist diese Menge natürlich immer leer).

4. Es erkennt Überlauf über __builtin_*_overflow . (Leider ist dies dann gcc-spezifisch. Eine andere Plattform könnte einen anderen Satz solcher Funktionen erfordern.)

Jetzt für die langsame aber sichere Funktion. Diese Funktion verwendet die GNU MP Multi-Präzisions-Arithmetikbibliothek . Es wird nach einer Endlosschleife gesucht, indem die Reihenfolge der Zahlen beibehalten wird, die es bereits gefunden hat. Diese Funktion gibt true zurück, wenn die Vermutung für diese Zahl nachgewiesen wurde, und false , wenn diese Zahl widerlegt wurde (beachten Sie den Unterschied zur vorherigen schnellen Verifizierung).

Schließlich behält main unordered_set der widerlegten Zahlen bei. für jede Zahl versucht sie optimistisch, die Vermutung zu verifizieren, und wenn sie fehlschlägt (zum Überlaufen oder Überschreiten der Anzahl der Iterationen), verwendet sie die langsame Methode:

Wenn Sie den vollständigen Code (unten) ausführen, erhalten Sie:

Das heißt, keine widerlegten Zahlen gefunden, und die Laufzeit bei ~ 64 Sekunden.

Vollständiger Code:

Dein Code und Ami Tavorys Antwort ignorieren das Problem des Überlaufs vollständig. Wenn eine nicht magische Zahl in Ihrem Bereich wäre, würde die Collatz-Iteration entweder in eine Schleife eintreten oder ohne Bindung ansteigen. Wenn es ohne Bindung erhöht wird, wird es sicherlich überlaufen, unabhängig von der Größe Ihres unsigned long ; und wenn es in eine Schleife eintritt, könnte es gut überlaufen, bevor es dort ankommt. Sie müssen also dort einen Überlauf-Check setzen:

  

Was kann ich tun, um es zu beschleunigen? Fehle ich offensichtliche Optimierungsprobleme?

• für (vorzeichenlose Länge i = 1; i & lt; = 5000000000; i ++)

Eine for-Schleife ist nicht der schnellste Codierungsstil, um eine Methode fünfmal aufzurufen.

In meinem Code siehe unwind100 () und innerLoop (). Das Abwickeln, das ich kodierte, entfernte 99% des innerLoop Aufwands, der mehr als 5 Sekunden speicherte (auf meinem Desktop DD5). Ihre Ersparnisse können variieren. Wikipedia hat einen Artikel über das Abwickeln einer Schleife mit einer kurzen Beschreibung des Sparpotentials.

• if (i% 1000000 == 0)

Dieser Code generiert anscheinend Fortschrittsberichte. Zu einem Preis von 5 Milliarden Vergleiche, es führt nichts für die magischen Zahl überprüft.

Siehe meinen Code outerLoop, der innerLoop 10 Mal aufruft. Dies bietet a Praktischer Ort für 1 Fortschrittsbericht jeder äußeren Schleife. Überlege, ob du dich teilen willst Ihre Loops in einen 'InnerLoop' und einen 'OuterLoop'. Testen 5 Milliarden mal ist teurer als das Hinzufügen von 10 Aufrufen zu innerLoops.

• Wie in den Kommentaren gibt Ihre checkMagic () -Eingabe '1' zurück, unabhängig von den Testergebnissen. Ein einfacher Fehler, aber ich weiß nicht, ob dieser Fehler die Leistung beeinträchtigt.

Ich denke, Ihr checkMagic () erreicht keine Tail-Rekursion, was Ihren Code wirklich verlangsamt.

Sehen Sie sich meine Methode checkMagicR () an, die eine Tail-Rekursion hat und ein true oder zurückgibt falsch.

Auch in Ihrer CheckMagic (), in der Klausel für ungerade Eingabe, ignorieren Sie die Idee, dass (3n + 1) eine gerade Zahl sein muss, wenn n positiv und ungerade ist. Mein Code führt eine 'früh-div-by-2' durch und reduziert so den zukünftigen Aufwand wenn möglich.

• In meinen Methoden unwind10 () beachte ich, dass mein Code das bekannte geradzahlige / ungerade Muster der Eingabe für die Sequenz (2..5 Milliarden) ausnutzt, indem checkMagicRO () (für ungerade Eingaben) und checkMagicRE () () ( für gerade).

In meinen früheren Versionen hat der Code Zeit damit verschwendet, zu erkennen, dass die bekannte geradzahlige Eingabe gerade war, dann durch 2 zu teilen und dann wahr zurückzugeben. checkMagicRE () überspringt den Test und teilt, wodurch Zeit gespart wird.

CheckMagicRO () überspringt den Test für ungerade, führt dann das ungerade Zeug aus und fährt mit checkMagicR () fort.

• if (Zahl! = 1) {checkMagic (Zahl); }

Ihre Rekursion geht weiter bis zu 1 ... nicht notwendig und möglicherweise der größte Hit für die Gesamtleistung.

Siehe meine checkMagicR () "recursion termination clause". Mein Code stoppt bei ((n / 2) & lt; m_N), wobei m_N der Testwert ist, der diese Rekursion gestartet hat. Die Idee ist, dass alle kleineren Testeingaben bereits als magisch gelten, sonst hätte der Code behauptet. Es hält auch an, wenn der Wraparound unmittelbar bevorsteht ... was nicht passiert ist.

Ergebnisse:

Mein Desktop (DD5) ist älter, langsamer und läuft unter Ubuntu 15.10 (64). Dieser Code wurde mit g ++ v5.2.1 entwickelt und wird nur ohne Timeout-Assert mit -O3 abgeschlossen.

DD5 ist anscheinend 2x langsamer als die Maschine, die von Amy Tavory verwendet wird (vergleicht, wie sein Code auf DD5 lief).

Bei DD5 endet mein Code in Modus 44 mit ~ 44 Sekunden und Modus 2 mit 22 Sekunden.

Ein schnellerer Computer könnte diesen Code in 11 Sekunden (in Modus 2) vervollständigen.

Vollständiger Code:

Der eingereichte Code:

a) verwendet assert (x) für alle Prüfungen (weil assert ist schnell und hat       Nebeneffekte, die der Optimierer nicht ignorieren kann).

b) erkennt eine Endlosschleife durch Verwendung einer Bestätigung der Dauer.

c) behauptet, um jeglichen Umlauf zu verhindern.

Wenn eine Bestätigung auftritt, wird das Programm nicht normal beendet.

Wenn dieser Code normal beendet wird, bedeutet das:

Hinweise zum rekursiven checkMagicR (uint64_t n):

3 Formen von n sind in der Rekursion verfügbar:

• formaler Parameter n - typisch für Rekursionsaufrufe

• auto var nxt - empfängt den berechneten Wert von n für next                           rekursiver Aufruf

• Datenattribut: m_N - der Startpunkt des gerade laufenden                           Rekursionsaufwand

Ich habe darüber spekuliert, welche Änderungen der Optimierer für diese spezielle Tail-Rekursion gemacht haben könnte.

Also habe ich eine iterative Antwort aus meinem V9-Code (in meiner anderen Antwort) erstellt.

Ändern von:

Ändern zu:

Der Name wurde nicht korrigiert. Kommentare oder andere Erwähnungen von "Rekursion" in dieser oder anderen Methoden wurden nicht korrigiert. Ich habe einige Kommentare oben und unten bei dieser Methode geändert.

Ergebnisse:

• Die Leistung ist identisch. (44 Sekunden)

• Modus 1 und Modus 2 sind beide iterativ.

• Modus 3 ist (noch) rekursiv.