sequenza collatz - codice di ottimizzazione

Question

Come domanda aggiuntiva a un compito, ci è stato chiesto di trovare i 10 numeri iniziali (n) che producono la sequenza collatz più lunga. (Dove 0 < n. < 10.000.000.000) Ho scritto codice che, si spera, sarebbe stato utile, ma ho stimato che ci sarebbero volute ben 11 ore per calcolare una risposta.

Ho notato un paio di piccole ottimizzazioni come partire dal più grande al più piccolo, quindi l'aggiunta all'array viene eseguita meno e solo il calcolo tra 10.000.000.000/2^10 (= 9765625) e 10.000.000.000 perché ci devono essere 10 sequenze di più lunga, ma non riesco a vedere altro che potrei fare. Qualcuno può aiutare?

relativo codice La Sequenza Ricerca Alg

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 
    } 
} 

Lo stoccaggio 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

Si può fare qualcosa di simile

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++; 
} 

che dovrebbe essere più veloce come fa più passaggi a una volta ed evita i rami imprevedibili. numberOfTrailingZeros è intrinsecamente JVM che richiede solo un ciclo su CPU desktop moderne. Tuttavia, non è molto efficiente poiché il numero medio di zeri è solo 2.

Il Wikipedia spiega come eseguire più passaggi contemporaneamente. Ciò si basa sull'osservazione che conoscere i bit meno significativi k è sufficiente per determinare le fasi future fino al punto in cui si verifica il dimezzamento di k. Il mio miglior risultato basato su questo (con k=17) e filtering out some non-promising values è 57 secondi per la determinazione del massimo nell'intervallo 1 .. 1e10.