Effizient Berechnung aller pythagoräischen Dreifach

Question

Bei einer Hypoteneuse (c in der typischen Gleichung a*a + b*b = c*c), was ist eine effiziente Möglichkeit, alle möglichen Ganzzahlwerte von zu berechnen a und b, so dass a < b?

Hinweis: Ich habe gesehen c größer sein als 1e12, daher c*c ist größer als long.MaxValue, was ich sagen kann, c*c passt in a decimal, obwohl.

Answer 1

Es gibt eine mathematische Lösung, die auch für große Werte von c schnell A und B findet. Leider ist es nicht so einfach. Ich versuche eine kurze Erklärung des Algorithmus zu geben. Ich hoffe es ist nicht zu verwirrend.

Da C gegeben ist und Sie nach A und B suchen, möchten Sie im Grunde genommen Diophantinenzeichen der Form lösen

n=x^2+y^2,

wo n gegeben ist. Es hilft nicht viel, dass n = c*c ein Quadrat ist und ich daher eine Lösung für jede n beschreibe. Wenn n eine Primzahl wäre, könnten Sie verwendenFermat's Theorem, um zu entscheiden, ob Ihre Gleichung lösbar ist, und die Verwendung, wie Idiot auf den Hermite-Seret-Algoritm hinwies, um die Lösungen zu finden, wenn es welche gibt.

Um den Fall zu lösen, in dem N nicht primär ist, ist es eine gute Idee zu verwendenGaußsche Ganzzahlen. (Gaußsche Ganzzahlen sind nur komplexe Zahlen mit integralen Koeffizienten). Insbesondere stellt man fest, dass die Norm von x+yi ist

N(x+yi) = x^2+y^2.

Daher muss man die Gaußschen Ganzzahlen x+yi finden, deren Norm n ist. Da die Norm multiplikativ ist, reicht es aus, diese Gleichung für die Faktoren von N zu lösen und dann die Gaußschen Ganzzahlen der einzelnen Gleichungen zu multiplizieren. Lassen Sie mich ein Beispiel geben. Wir wollen lösen

65 = x^2 + y^2.

Dies ist gleichwertig, um X zu finden, y so, dass

N(x+yi) = 65

über die Gaußschen Ganzzahlen. Wir fakten 65 = 5 * 13, dann verwenden wir Fermat, um zu beachten, dass sowohl 5 als auch 13 als Summe von zwei Quadraten dargestellt werden können. Schließlich finden wir entweder mit der Brute-Kraft von den Hermite-Seret-Algorithmus

N(2+i) = N(1+2i) = ... = 5
N(2+3i) = N(3+2i) = ... = 13

Beachten Sie, ich habe die Gaußigkeitszahlen 2 -i, -2+i usw. mit negativen Koeffizienten ausgelassen. Das sind natürlich auch Lösungen.

Daher können wir diese Lösungen jetzt miteinander multiplizieren, um zu bekommen

65 = 5 * 13 = n (2+i) * n (2+3i) = n ((2+i) * (2+3i)) = n (1+8i)

und

65 = 5 * 13 = n (2+i) * n (3+2i) = n ((2+i) * (3+2i)) = n (4+7i).

Daher bekommt man die beiden Lösungen

1*1 + 8*8 = 65
4*4 + 7*7 = 65

Die anderen Kombinationen, z. B. mit negativen Koeffizienten, müssen ebenfalls überprüft werden. Sie geben keine anderen Lösungen als Permutationen und veränderte Zeichen.

---

Um alle Lösungen zu berechnen, kann man auch hinzufügen, dass es keine Notwendigkeit besteht, jemals c*c zu berechnen. Das Finden der Faktoren von C ist alles, was notwendig ist. Auch da A und B beide kleiner als C sind, wird es nicht vorkommen, dass Produkte von Gaußschen Ganzzahlen nicht mit 64-Bit-Ganzzahlkoeffizienten dargestellt werden können. Wenn man also vorsichtig ist, sind 64-Bit-Ganzzahl genügend Präzision, um das Problem zu lösen. Natürlich ist es immer einfacher, nur eine Sprache wie Python zu verwenden, die diese Art von Überlaufproblemen nicht hat.

Answer 2

Alle pythagoräischen Tripel (a, b, c) erfüllen das Eigentum, das für einige Ganzzahlen K, M und N,.

a = k (m^2-n^2), b = 2kmn, c = k (m^2 + n^2)

Beginnen Sie also mit der Aufnahme c. Dann finden Sie für jeden unterschiedlichen Faktor k von C (dh für jede unterschiedliche Teilmenge der Faktoren zusammen) alle m und n, die C/K = (m^2 + n^2) erfüllen. Letzteres dauert erheblich weniger Zeit als der Brute-Force-Ansatz, den andere vorgeschlagen haben (Sie müssen nur Quadrate finden, die zu C/K anstelle von C^2), aber alle Dreifachungen identifizieren (a, b, c) . Sie müssen auch keine Bignums verwenden, da alle Zwischenergebnisse in lange passen.

Ich schlage auch vor, dass Sie sich die Webseite ansehen http://www.maths.surrey.ac.uk/hosted-sites/r.knott/pythag/pythag.html Unter der Überschrift "Ein allgemeinerer pythagoräischer Triple Calculator" enthält ein eingebetteter Taschenrechner, der in JavaScript geschrieben wurde, genau das, was Sie wollen.

Answer 3

Könnte auch eine Bignum -Bibliothek gehen.

Wie für eine effiziente Art, a und b zu finden:

Berechnen Sie für jeden Wert von B (beginnend bei C -1 und nach unten b * B <C * C / 2) C * C - B * B, und überprüfen Sie dann, ob es sich um ein perfektes Quadrat handelt.

Answer 4

Beginnen Sie mit einem Wert von 1 für a und einem Wert von C für b.

Vergleichen c*c - b*b zu a*a. Wenn sie gleich sind, haben Sie ein Match.

Ändern Sie A und B in Richtung einander, je nachdem, welche Seite größer ist, bis sie gleich sind.

Answer 5

Gegeben AC:

Da b> a, wenn a minimal ist (a = 1), ist b = sqrt (c*c - 1).

Daher muss B zwischen diesem Wert und c -1 liegen.

Da B eine Ganzzahl sein muss, müssen Sie den ersten Wert finden, für den dies eine Ganzzahl ist.

Now, a property of squares:
The squares are: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, ...
The differences: -, 3, 5, 07, 09, 11, 13, 15, 17, 019, 021, ...
That means a square can be written as a summation of ODD numbers:
    1 + 3 + 5 + 7 + n+...
where n = number the summation is a square of.

Es gibt also genau C -Quadratnummern, die weniger als C*C sind, und Sie können sie anhand einer einfachen Subtraktion identifizieren.

Zurück zum Anfang, nehmen Sie b = sqrt (cC - 1), rund und behle BB, wir bekommen das Quadrat B müssen oben sein und aa = 1. finde cc - (aa + bb). Dies sollte Ihnen die Zahl geben, die hinzugefügt werden muss, um C*c zu erreichen.

Da können Sie hinzufügen 3 + 5 + 7 + ... zu a und und b+2 + b+4 + b+6 + ... Zu B muss man nur den richtigen Begriff basierend auf den Summen und nicht auf dem Quadrat selbst finden :)