求解方程的非蠻力方法的編程算法

Question

除蠻力方法之外，什麼可以是一個很好的編程算法來求解下列方程？

找到n = 100的所有x，y和z;

x^2 + y^2 + z^2 = n; 

x，y，z應該是正整數。

Answer 1

下面是相對於線性時間到n的溶液：

int x, y, z; 
int n = 1000; 
int tests = 0; 
int solutions = 0; 
// loop through all possible x values 
for(x = 1; x * x * 3 <= n; x++) 
{ 
    // compute target sum of y^2 + z^2 
    int m = n - x * x; 
    for(y = x; y * y * 2 <= m; y++) 
    { 
     tests++; 
     // compute z and check if it's an integer: 
     z = (int)(Math.sqrt(m - (y * y))); 
     if((x * x) + (y * y) + (z * z) == n) 
     { 
      System.out.println(""+x+" "+y+" "+z); 
      solutions++; 
     } 
    } 
} 
System.out.println(tests); 
System.out.println(solutions); 

它比蠻力溶液去除一個內環，通過計算z內給出x和y的必要值，並檢查它是否整數。

數規定的測試和解決方案，發現n值：

n   tests  solutions 
5000  1081  8 
500000  108749  45 
50000000 10879762 232 

似乎沒有要擺脫外環的任何方式，因爲你需要通過多種解決方案循環，但你可以在「早出」，並通過檢查避免了內德路，如果m是the sum of two squares

這是一個簡單的實現鏈接的算法，但也有很多更先進的分解算法（如波拉德的RHO）：

public static boolean isSumOfTwoSquares(int m) 
{ 
    for(int i = 2; i * i <= m; i++) 
    { 
     int exponent = 0; 
     while(m % i == 0) 
     { 
      m /= i; 
      exponent++; 
     } 
     if((m % 4 == 3) && ((exponent & 1) != 0)) 
      return false; 
    } 
    return true; 
} 

你可以用你的內循環在此檢查：

if(isSumOfTwoSquares(m)) 

結果：

n   tests  solutions 
5000  777   8 
500000  72162  45 
50000000 6511184  232 

給定一個足夠快的isSumOfTwoSquares功能，這可能會出人頭地。與沒有早期的簡單算法不同，測試的數量對n的值更加敏感。

這兩種算法都有約束條件x < = y < = z。我希望所有的解決方案都沒有這個約束，你可以對解決方案進行排序，每個約束解決方案將會有6（3！）個。