生成具有一個固定值的畢達哥拉斯四元組？

Question

如果我想生成唯一的（忽略負數）固定d（在這種情況下爲2^15 - 1）的畢達哥拉斯四元組（形式爲a^2 + b^2 + c^2 = d^2）還有比O（n^3）更好的方法嗎？

現在我幾乎用蠻力迫使：

int r = (1 << 15) - 1; 

for(int i = 0; i < r; i++) 
for(int j = i; j < r; j++) 
    for(int k = j; k < r; k++) 
    if(i * i + j * j + k * k == r * r) 
    //add to list 

這是O（n^3），有沒有更快的方法？我發現了一些可能會產生四倍的小竅門，但他們都表示他們可能會錯過一些。我看到他們的方程式，我認爲可能有一些線性方程組的方式？

Answer 1

在previously-mentioned Wikipedia page第二個參數說

所有畢達哥拉斯四元組...可以由兩個正整數a，奇數和b生成，甚至... 設p是任意因子a^2 + b^2，使得p^2 < a^2 + b^2。然後c =（a^2 + b^2 - p^2）/ 2和d =（a^2 + b2^+ p^2）/ 2 ...。 ..

這似乎是一個簡單的爲O（n^2）的方法來產生所有畢達哥拉斯四邊形，但沒有明顯的方法來對利用 d固定

。

這裏是另一個ö，無需數學洞察力，只是一些基本的數據結構的能力（N^2）方法：

for(k=0; k<r; ++k) 
    insert r^2 - k^2 into BST [*] 

    for(i=0; i<r; ++i) 
    for(j=i; j<r; ++j) 
     if i^2 + j^2 is in BST report i,j,k [**] 

[*]的任何高速字典數據結構可以使用;二叉搜索樹不是強制性的。但是，AA trees速度很快，並且易於編碼。

[**]從k^2 = r^2 - i^2 - j^2計算k。

Answer 2

嘗試使用參數化，Wikipedia page提及其中2個參數。

Answer 3

它仍然會爲O（n^3），但你可以通過不搜索是太大的數字加速它一點：

... 
for(int i = 0; i < r; i++) 
    for(int j = i; j < sqrt(r^2 - i^2); j++) 
    for(int k = j; k < sqrt(r^2 - i^2 - j^2); k++) 
...