ヒポテネ人を知っているすべてのピタゴラスのトリプルを効率的に計算します

Question

ヒポテネイズを与えられた（c 典型的な方程式で a*a + b*b = c*c）、可能なすべての整数値を計算する効率的な方法は何ですか a と b, 、 そのような a < b?

注：見たことがあります c より大きくなります 1e12, 、 したがって c*c より大きい long.MaxValue, 、私が言うことができることから、 c*c に収まります decimal, 、 けれど。

Answer 1

cの大きな値でもaとbを高速にする数学的解決策があります。残念ながら、それほど単純ではありません。アルゴリズムの簡単な説明をしようとしています。混乱しすぎないことを願っています。

Cが与えられ、AとBを探しているので、基本的にはフォームのディオファンティン方程式を解きたいと思う

n=x^2+y^2,

ここで、nが与えられます。 n = c*cが正方形であることはあまり役に立たないので、nの解決策を説明しています。 nが素数であれば、使用できますフェルマットの定理, 、方程式が溶解性であるかどうかを判断し、使用して、モロンがエルマイトセレットアルゴリットを指摘して、ある場合は解を見つけました。

nがプライムではない場合を解決するために、使用することをお勧めしますガウスの整数. 。 （ガウス整数は、積分係数を備えた複雑な数値です）。特に、1つはそれを指摘しています 規範 x+yiの

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

したがって、標準がnであるガウス整数x+yiを見つける必要があります。標準は乗算的であるため、Nの因子のこの方程式を解くには十分であり、個々の方程式のガウス整数を掛けるには十分です。例を挙げましょう。解決したいです

65 = x^2 + y^2.

これは、x、yを見つけるのと同等です。

N(x+yi) = 65

ガウスの整数の上。因子65 = 5 * 13を使用してから、Fermatを使用して、5と13の両方を2つの正方形の合計として表すことができることに注意してください。最後に、Hermite-Serretアルゴリズムを使用することにより、ブルートフォースを使用することにより、

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

注意してください、私は負の係数を持つガウス整数2 -I、-2+Iなどを除外しました。もちろん、それらも解決策です。

したがって、これらのソリューションを一緒に掛けて取得することができます

65 = 5 * 13 = n（2+i） * n（2+3i）= n（（2+i） *（2+3i））= n（1+8i）

と

65 = 5 * 13 = n（2+i） * n（3+2i）= n（（2+i） *（3+2i））= n（4+7i）。

したがって、1つは2つのソリューションを取得します

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

たとえば、負の係数を伴う他の組み合わせもチェックする必要があります。彼らは、順列と変更された兆候以外の新しい解決策を提供しません。

---

すべてのソリューションを計算するには、C*Cを計算する必要がないことも付け加えます。 Cの要因を見つけることが必要です。また、AとBはどちらもCよりも小さいため、ガウス整数の生成物が64ビット整数係数で表現できないことは起こりません。したがって、注意している場合、64ビット整数は問題を解決するのに十分な精度です。もちろん、この種のオーバーフローの問題を抱えていないPythonのような言語を使用する方が常に簡単です。

Answer 2

すべてのPythagoreanトリプル（A、B、C）は、一部の整数K、M、Nの場合、その特性を満たしています。

a = k（m^2-n^2）、b = 2kmn、c = k（m^2 + n^2）

したがって、c。次に、Cのすべての異なる因子K（つまり、因子のすべての異なるサブセットについて、掛け合った）について、C/k =（m^2 + n^2）を満たすすべてのmとnを見つけます。後者を行うには、他の人が示唆しているブルートフォースアプローチよりも大幅に短い時間がかかります（C^2ではなくC/Kに合計する正方形を見つける必要があります）が、すべてのトリプルを特定します（A、B、C） 。また、中間の結果はすべて長いものに収まるため、ビグラムを使用する必要はありません。

また、Webページをチェックすることをお勧めします http://www.maths.surrey.ac.uk/hosted-sites/r.knott/pythag/pythag.html JavaScriptで書かれた埋め込み計算機を含む「より一般的なPythagoreanトリプル計算機」という見出しの下で、まさにあなたが望むものを行います。

Answer 3

Bignumライブラリにも行くかもしれません。

AとBを見つける効率的な方法については：

Bの各値（C -1から始まり、b * b <c * c / 2まで下がってください）について、C * c -b * bを計算し、それが完全な正方形かどうかを確認します。

Answer 4

aに対して1の値とbの値cから始めます。

比較 c*c - b*b に a*a. 。それらが平等であれば、あなたは試合をしています。

どの側が同じになるまで、どの側が大きいかに応じて、互いにAとBを変更します。

Answer 5

与えられたAC：

b> aであるため、aが最小（a = 1）の場合、b = sqrt（c*c -1）。

したがって、Bはその値とC -1の間でなければなりません。

また、Bは整数である必要があるため、これが整数である最初の値を見つける必要があります。

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.

したがって、C*Cよりも少ないc正方形数があり、単純な減算を使用してそれらを識別できます。

最初に戻って、b = sqrt（cを取得しますc -1）、丸くしてbを取るb、四角いbが上にある必要があり、a = 1. cc-（aa + bb）。これにより、c*cを達成するために追加する必要がある数が得られるはずです。

追加できるので 3 + 5 + 7 + ... と、 b+2 + b+4 + b+6 + ... Bには、正方形自体ではなく合計に基づいて正しい用語を見つける必要があります:)