問題タブ [greatest-common-divisor]

たとえば、一般的な量のほぼ倍数である浮動小数点数のリストがあるとします。

2.468、3.700、6.1699

これはほぼすべて 1.234 の倍数です。この「近似 gcd」をどのように特徴付けますか?また、どのように計算または推定を進めますか?

この質問に対する私の答えに厳密に関連しています。

3 つ以上の数値の最大公約数アルゴリズムを見つける例を教えてください。

プログラミング言語は関係ないと思います。

1 つの方法は、 gcdを計算し、それが 1 かどうかを確認することです。

もっと速い方法はありますか？

上の関数のコードを自分の関数（下）と打ち負かそうとしています。ルーチンを最適化する方法について何かアイデアはありますか？

PS。これはただの楽しみです。

matlab で使用されている "gcd" 関数を別の言語で実装する方法を探していますが、それが機能する方法を本当に理解できません。

http://www.mathworks.com/access/helpdesk/help/techdoc/ref/gcd.htmlで次のように述べています。

"[G,C,D] = gcd(A,B) は、次の式を満たす最大公約数配列 G と配列 C および D の両方を返します: A(i).*C(i) + B(i) .*D(i) = G(i)"

ただし、C と D の計算方法については何も述べていません。

誰かがこの主題についてより明確な考えを持っていれば、私は感謝します! ありがとう：）

Python v3.1の分数モジュールを使用して、最大公約数を計算しています。どのアルゴリズムが使われているのか知りたいのですが。ユークリッド法を推測していますが、確かにしたいと思います。ドキュメント（http://docs.python.org/py3k/library/fractions.html?highlight=fractions.gcd#fractions.gcd）は役に立ちません。誰かが私を手がかりにできますか？

BigIntegerそのような関数が、つまり に存在することを見てきましたBigInteger#gcd。int他のタイプ ( 、longまたは)でも動作する Java の他の関数はありますIntegerか? これはjava.lang.Math.gcd（あらゆる種類のオーバーロードで）理にかなっているようですが、そうではありません。他の場所ですか？

(この質問を「これを自分で実装するにはどうすればよいか」と混同しないでください!)

一連の数値で最大公約数と最小公倍数を計算する最も簡単な方法は何でしょうか。この情報を見つけるために使用できる数学関数は何ですか？

与えられた数値の GCF を見つけたくありません。そのためにユークリッドを使用します。特定の GCF を持つ一連の数値を生成したいと考えています。たとえば、4 を選択した場合、100、72、または 4、8 などを取得する必要があります。

任意のポインタをいただければ幸いです。