在Java中優化Collat​​z猜想

Question

我正在研究一個程序，該程序確定使用Collat​​z猜想將數字變爲1所需的步驟數（如果n是奇數，3n + 1;如果n是偶數，則n/2）。程序每完成一次計算就增加一個計算的數字，並測試它可以在幾秒鐘內計算出多少個數字。這裏是工作程序我目前有：

public class Collatz { 
    static long numSteps = 0; 
    public static long calculate(long c){ 
     if(c == 1){ 
      return numSteps; 
     } 
     else if(c % 2 == 0){ 
      numSteps++; 
      calculate(c/2); 
     } 
     else if(c % 2 != 0){ 
      numSteps++; 
      calculate(c * 3 + 1); 
     } 
     return numSteps; 
    } 
    public static void main(String args[]){ 
     int n = 1; 
     long startTime = System.currentTimeMillis(); 
     while(System.currentTimeMillis() < startTime + 60000){ 

      calculate(n); 
      n++; 
      numSteps = 0; 
     } 
     System.out.println("The highest number was: " + n); 
    } 
} 

它目前可以在一分鐘內計算約100萬個號碼，但是我正在尋找如何進一步優化程序，以便它可以計算出更多的數字建議一分鐘。任何和所有的建議，將不勝感激:)。

Answer 1

可以

• 優化假設的計算方法是c % 2 == 0比c % 2 != 0假的必須是真實的。您還可以假設c * 3 + 1必須是偶數，所以您可以計算(c * 3 + 1)/2並將兩個添加到numSteps。您可以使用循環而不是遞歸，因爲Java沒有tail-call優化。

• 通過記憶得到更大的改善。對於每個數字，您都可以記住您得到的結果，以及在返回該值之前是否計算了該數字。你可能想要記住一個上限，例如不高於您想要計算的最後一個數字。如果你不這樣做，一些價值將是最大價值的許多倍。

爲了您的利益

public class Collatz { 
    static final int[] CALC_CACHE = new int[2_000_000_000]; 

    static int calculate(long n) { 
     int numSteps = 0; 
     long c = n; 
     while (c != 1) { 
      if (c < CALC_CACHE.length) { 
       int steps = CALC_CACHE[(int) c]; 
       if (steps > 0) { 
        numSteps += steps; 
        break; 
       } 
      } 
      if (c % 2 == 0) { 
       numSteps++; 
       c /= 2; 
      } else { 
       numSteps += 2; 
       if (c > Long.MAX_VALUE/3) 
        throw new IllegalStateException("c is too large " + c); 
       c = (c * 3 + 1)/2; 
      } 
     } 
     if (n < CALC_CACHE.length) { 
      CALC_CACHE[(int) n] = numSteps; 
     } 
     return numSteps; 
    } 

    public static void main(String args[]) { 
     long n = 1, maxN = 0, maxSteps = 0; 
     long startTime = System.currentTimeMillis(); 
     while (System.currentTimeMillis() < startTime + 60000) { 
      for (int i = 0; i < 10; i++) { 
       int steps = calculate(n); 
       if (steps > maxSteps) { 
        maxSteps = steps; 
        maxN = n; 
       } 
       n++; 
      } 
      if (n % 10000000 == 1) 
       System.out.printf("%,d%n", n); 
     } 
     System.out.printf("The highest number was: %,d, maxSteps: %,d for: %,d%n", n, maxSteps, maxN); 
    } 
} 

打印

The highest number was: 1,672,915,631, maxSteps: 1,000 for: 1,412,987,847 

更高級的答案是使用多線程。在這種情況下，使用遞歸與記憶更容易實現。

import java.util.stream.LongStream; 

public class Collatz { 
    static final short[] CALC_CACHE = new short[Integer.MAX_VALUE-8]; 

    public static int calculate(long c) { 
     if (c == 1) { 
      return 0; 
     } 
     int steps; 
     if (c < CALC_CACHE.length) { 
      steps = CALC_CACHE[(int) c]; 
      if (steps > 0) 
       return steps; 
     } 
     if (c % 2 == 0) { 
      steps = calculate(c/2) + 1; 
     } else { 
      steps = calculate((c * 3 + 1)/2) + 2; 
     } 
     if (c < CALC_CACHE.length) { 
      if (steps > Short.MAX_VALUE) 
       throw new AssertionError(); 
      CALC_CACHE[(int) c] = (short) steps; 
     } 
     return steps; 
    } 

    static int calculate2(long n) { 
     int numSteps = 0; 
     long c = n; 
     while (c != 1) { 
      if (c < CALC_CACHE.length) { 
       int steps = CALC_CACHE[(int) c]; 
       if (steps > 0) { 
        numSteps += steps; 
        break; 
       } 
      } 
      if (c % 2 == 0) { 
       numSteps++; 
       c /= 2; 
      } else { 
       numSteps += 2; 
       if (c > Long.MAX_VALUE/3) 
        throw new IllegalStateException("c is too large " + c); 
       c = (c * 3 + 1)/2; 
      } 
     } 
     if (n < CALC_CACHE.length) { 
      CALC_CACHE[(int) n] = (short) numSteps; 
     } 
     return numSteps; 
    } 

    public static void main(String args[]) { 
     long maxN = 0, maxSteps = 0; 
     long startTime = System.currentTimeMillis(); 
     long[] res = LongStream.range(1, 6_000_000_000L).parallel().collect(
       () -> new long[2], 
       (long[] arr, long n) -> { 
        int steps = calculate(n); 
        if (steps > arr[0]) { 
         arr[0] = steps; 
         arr[1] = n; 
        } 
       }, 
       (a, b) -> { 
        if (a[0] < b[0]) { 
         a[0] = b[0]; 
         a[1] = b[1]; 
        } 
       }); 
     maxN = res[1]; 
     maxSteps = res[0]; 
     long time = System.currentTimeMillis() - startTime; 
     System.out.printf("After %.3f seconds, maxSteps: %,d for: %,d%n", time/1e3, maxSteps, maxN); 
    } 
} 

打印

After 52.461 seconds, maxSteps: 1,131 for: 4,890,328,815 

注：如果我更改第二個計算呼叫

 steps = calculate((c * 3 + 1)) + 1; 

它打印

After 63.065 seconds, maxSteps: 1,131 for: 4,890,328,815