Effizientes Vorhersagen der Ausgabe eines Zahlenverarbeitungsalgorithmus

Question

Ich arbeite an ein wenig Code, der in der Lage sein soll, die Ausgabe des folgenden Algorithmus effizient zu prognostizieren (vorzugsweise in O (1) Zeit), wenn er mit zwei Ints m und dargestellt wird n.

algorithm(m,n): 
history = set() 
while True: 
    if (m,n) in history: 
     return False 
    elif n == m: 
     return True 
    else: 
     history.add((m,n)) 
     if m>n: 
      x = m-n 
      y = 2*n 
      m = x 
      n = y 
     else: 
      x = 2*m 
      y = n-m 
      m = x 
      n = y 

Beachten Sie, dass, wenn (m, n) erscheint in der Geschichte des folgenden Algorithmus, haben Sie eine unendliche Schleife eingegeben (das heißt 2,1 -> 1,2 -> 2,1 ...); wenn m == n, kann der Algorithmus nur einen Schritt weitergehen und muss enden (d. h. 5,5 -> 10,0 -> 10,0 ...). Im Wesentlichen muss ich vorhersagen können, ob m (Strom) und n (Strom) jemals übereinstimmen werden.

PS, wenn dieser Algorithmus einen Namen hat, würde ich es gerne wissen. Wenn es darüber hinaus eine gute Lektüre zu diesem Thema gibt (Vorhersage von Zahlenfolgen usw.), würde ich mich gerne darauf beziehen.

Answer 1

Zuerst reduzieren wir den Update-Schritt auf eine einzige Zeile. Bei jeder Iteration m Aktualisierungen der absoluten Differenz; n Updates auf die doppelt so kleine Zahl.

else: 
    history.add((m,n)) 
    m, n = abs(m-n), 2 * min(m, n) 

Dies hebt die Nichtlinearität der Iteration hervor. Jedes Update bricht in die zwei Klassen ein, die Sie zuerst programmiert haben; Die Wiederholung zerfällt bei jeder weiteren Iteration in mehrere Klassen.

Ich glaube, dass die kurze Antwort für diese keine ist - Sie können das Ergebnis in einer Zeit nicht vorhersagen, die als die Ausführung des Algorithmus einigermaßen kürzer ist.

Der Teilungspunkt für das Umschalten von groß gegen kleiner ist, wenn eine Zahl dreimal so groß ist wie die andere. In diesem Raum schließt der Algorithmus die Lücke einfach: Subtrahiere die kleinere Form von der größeren, dann verdopple die kleinere. Sobald sie den Bereich von 3x erreichen, wird das System schnell chaotisch: Sie können nicht sagen, dass zwei nahe beieinander liegende Paare Ergebnisse haben, die bei fortschreitendem Algorithmus in der Nähe bleiben, nicht für benachbarte Paare.

Answer 2

Unter der Annahme einer positiven Ganzzahleingabe gibt dieser Algorithmus nur dann True zurück, wenn (m + n)/gcd (m, n) eine Potenz von Zwei ist.

Proof Skizze:

Dividieren sowohl m als auch n um gcd (m, n) zu Beginn des Algorithmus; Dies wird den Rückgabewert nicht ändern.

Wenn die Summe von m und n nach diesem Schritt durch eine ungerade Primzahl p teilbar ist, dann müssen sowohl m als auch n durch p teilbar werden, damit der Algorithmus Wahr liefert, aber weder m noch n können dies tun.

Wenn die Summe von m und n eine Zweierpotenz ist, dann werden m und n bei jeder Iteration um einen weiteren Faktor von 2 teilbar, bis beide gleich sind.