Programmieralgorithmus für eine Nicht-Brute-Force-Methode zum Lösen der Gleichung

Question

Was kann ein guter Programmieralgorithmus zur Lösung der folgenden Gleichung sein, außer der Brute-Force-Methode?

Finden Sie alle x, y und z für n = 100;

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

x, y, z sollten positive ganze Zahlen sein.

Answer 1

Hier ist eine Lösung in linearer Zeit mit Bezug auf 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); 

Es entfernt eine innere Schleife im Vergleich zu der Brute-Force-Lösung, indem den notwendigen Wert von z gegebenen x und y zu berechnen und zu überprüfen, ob es ganze Zahl.

Anzahl der erforderlichen Tests und Lösungen für die Werte von n gefunden:

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

Es scheint keinen Weg, um von der äußeren Schleife loszuwerden, weil Sie eine Schleife durch mehrere Lösungen benötigen, aber Sie können „früh out“ und zu vermeiden, dass die innere looop durch Prüfen, ob m the sum of two squares

ist Dies ist eine einfache Implementierung des verknüpften Algorithmus, aber es gibt viel weiter fortgeschritten Faktorisierung Algorithmen (zB Pollard 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; 
} 

Sie können Ihre innere Schleife in dieser Prüfung wickeln:

if(isSumOfTwoSquares(m)) 

Ergebnisse:

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

eine schnell genug isSumOfTwoSquares Funktion gegeben, könnte dies kommen voran heraus. Im Gegensatz zum einfacheren Algorithmus ohne frühes Ausgehen ist die Anzahl der Tests viel empfindlicher für den Wert von n.

Beide Algorithmen haben die Einschränkung x < = y < = z. Wenn Sie alle Lösungen ohne diese Einschränkung möchten, können Sie die Lösungen permutieren, es wird 6 (3!) Für jede eingeschränkte Lösung geben.