colatz sequenz - Optimierungscode

Question

Als zusätzliche Frage zu einer Aufgabe wurden wir gebeten, die 10 Startnummern (n) zu finden, die die längste collatz-Sequenz erzeugen. (Wo 0 < n < 10.000.000.000) Ich schrieb Code, der dies hoffentlich erreichen würde, aber ich schätze, dass es volle 11 Stunden dauern würde, um eine Antwort zu berechnen.

Ich habe ein paar kleine Optimierungen bemerkt, angefangen vom größten bis zum kleinsten, so dass das Hinzufügen zu dem Array weniger ist und nur zwischen 10.000.000.000/2^10 (= 9765625) und 10.000.000.000 berechnet wird, weil es 10 Folgen von längere Länge, aber ich kann nichts mehr sehen, was ich tun könnte. Kann jemand helfen?

Relevante-Code Die Sequenz Alg Suche

long[][] longest = new long[2][10]; //terms/starting number 
long max = 10000000000l; //10 billion 

for(long i = max; i >= 9765625; i--) { 
    long n = i; 
    long count = 1; //terms in the sequence 

    while(n > 1) { 
     if((n & 1) == 0) n /= 2; //checks if the last bit is a 0 
     else { 
      n = (3*n + 1)/2; 
      count++; 
     } 
     count++; 
    } 
    if(count > longest[0][9]) { 
     longest = addToArray(count, i, longest); 
     currentBest(longest); //prints the currently stored top 10 
    } 
} 

Die Speicher alg

public static long[][] addToArray(long count, long i, long[][] longest) { 
    int pos = 0; 
    while(count < longest[0][pos]) { 
     pos++; 
    } 
    long TEMP = count; //terms 
    long TEMPb = i; //starting number 
    for(int a = pos; a < longest[0].length; a++) { 
     long TEMP2 = longest[0][a]; 
     longest[0][a] = TEMP; 
     TEMP = TEMP2; 

     long TEMP2b = longest[1][a]; 
     longest[1][a] = TEMPb; 
     TEMPb = TEMP2b; 
    } 
    return longest; 
} 

Answer 1

Sie so etwas wie

while (true) { 
    int ntz = Long.numberOfTrailingZeros(n); 
    count += ntz; 
    n >>>= ntz; // Using unsigned shift allows to work with bigger numbers. 
    if (n==1) break; 
    n = 3*n + 1; 
    count++; 
} 

tun können, die schneller sein sollte, da es mehrere Schritte tut an einmal und vermeidet unvorhersehbare Zweige. numberOfTrailingZeros ist JVM intrinsisch, das nur einen Zyklus auf modernen Desktop-CPUs dauert. Es ist jedoch nicht sehr effizient, da die durchschnittliche Anzahl der Nullen nur 2 ist.

Die Wikipedia erklärt, wie Sie mehrere Schritte gleichzeitig tun. Dies basiert auf der Beobachtung, dass das Wissen um k niedrigstwertige Bits ausreicht, um die zukünftigen Schritte bis zu dem Punkt zu bestimmen, an dem die k -te Halbierung stattfindet. Mein bestes Ergebnis basierend darauf (mit k=17) und filtering out some non-promising values ist 57 Sekunden für die Bestimmung des Maximums im Bereich 1 .. 1e10.