問題タブ [greatest-common-divisor]

更新：わからないときは3 %4 =0...

次のように機能すると思います。

私はこの質問に完全に行き詰まっているので、助けを探しています。

バイナリ GCD やユークリッド GCD などの基本的な GCD 計算アルゴリズムについては、誰もが知っていると思います。このようなメソッドを実装して 2 つの単精度数を計算することは問題ではありません。実際には、それはほんの数ストロークです。

このメソッドを (C 言語で) 多倍精度数 (10^5 ビット以上) 用に実装する必要があります。利用可能な GNU ライブラリ (GNU MP、MPFR、MPIR) がいくつかあり、それらには多倍精度数を定義し、それらに対してアクションを実行する手段があります。これは、「手足」とも呼ばれる単精度部分のカップルとしてメモリに格納された 1 つの多倍精度数のように見えます。

gcd(a, b) を見つけるためにいくつかのメソッドが実装されていますが、実際には、私のニーズに合わせて使用​​するのは困難です。a と b に正確に 2 つのリムが含まれる場合にのみ使用される GCD 計算のバイナリ メソッド。min(a,b) に 630 以上のリムが含まれる場合などに使用される HGCD メソッド。a と b の任意の長さで使用するためにこれらのメソッドをどのように拡張できるかを理解するのは難しいと思います。また、GNU ライブラリの異なるバージョンには、異なるバージョンと GCD アルゴリズムのメソッドが含まれていることもわかりました。

質問:バイナリ GCD アルゴリズムを「リム」に関して任意の長さの多倍精度整数で動作させることが可能かどうかを調べたいのですが、可能であれば、C でそれを実装する方法やアイデアを得るために.誰かがそれを実装する方法やコード部分を持っていますか?

その問題を解決するためのアドバイスやその他の解決策を検討したいと思います。

誰かが見てみるなら、これは (a = b = 2 limbs) の GNU MP バイナリ GCD メソッドの一部です。

上記のコード貼り付け。

GCD(a, b) = GCD(b, r) r = a%b のユークリッド アルゴリズムを使用するプログラムを作成しています。メインメソッドが吐き出す整数を返す必要があるメソッドを作成しましたが、これを行うために呼び出すと、整数を返していないと表示されます。ここにコードがあります

私はEdwardSchneinermanの数学者向けC++からC++を学んでいます。私は第2章の最大公約数のセクションに取り組んでいます。3つのファイルを作成しました。

gcd.h

gcd.cc

およびgcdtest.cc

これらのファイルはすべて同じディレクトリにあります。gcdtest.ccをコンパイルしようとすると

次のエラーが表示されます。

私はC++を初めて使用し、コンパイルとリンクを完全に理解していません。私は何が間違っているのですか？

モジュールの構造のどこかに機能がありますかnumpy?gcd

私は知っていますが、同等のものがおそらくより速く、データ型でよりうまく機能するfractions.gcdと考えました。numpynumpy

古いと思われるこのリンク以外に、グーグルで何かを発見することができず、_gcdそれが示唆する機能にアクセスする方法がわかりません。

素朴にしようとしている：

私のために働いていません...

だから、Javaを使ってRSAパスワードの公開鍵を見つけます。現在、自分が何をしているのか、それが正しいのかどうかもわかりません。

公開鍵に関するこの情報があります。

物事を複雑にしているのは BigInteger です。int と long の数値は非常に大きいため、ぎこちない BigInteger を使用する必要があります。私が理解している限り、次の方程式を解く必要があります。

euklidske アルゴリズムを使用して解決しようとしています。Javaでは、次の方法を使用できると思います：

phi(n) = 8271117252 および d = 53 に基づいてコードを作成します。次に、for ループで gcd を使用し、for ループから phi(n) の gdc に i 個の数値を試行します。結果が 1 の場合、i を i の反復回数に設定します。次に、e と phi(n) に対してモジュラス逆関数を使用します。これが phi(n) に等しい場合にのみ、答えが得られました。（私は、それが得るのと同じくらい間違っているかもしれないと思います）。

とにかく、ここにコードがあります。一般的に、どんな入力も私を少し狂わせるほど素晴らしいものです。

私のプログラムはユーザーに 2 つの数字を要求し、それらの数字を関数に渡す必要があります。私の関数は、「ユークリッドのアルゴリズムを使用して 2 つの値の最大公約数 (GCD) を特定することになっています。この値が 1 より大きく、2 つの数値の小さい方より小さい場合は true を返します。call-by-reference パラメーターを に設定します。 GCD の値。main() で、GCD と、関数が true または false を返したかどうかを出力します。」どうすればいいですか？

GCDを見つけるための連続整数チェックアルゴリズムがブルートフォースと見なされるのに、ユークリッドアルゴリズムはそうではないのはなぜですか? 私はそれについて混乱しています。いちいちチェックしているからでしょうか。

以下は私のコードで、出力は maghsom moshtarak is=24612 ですが、目標は 12 のみです。私を助けてください、

だから私はPythonでプログラムを書いて、任意の数のGCDを取得しています。

この関数は、数値のリストを受け取ります。これは 2 を出力するはずです。ただし、複数の数値を処理できるようにアルゴリズムを再帰的に使用する方法がわかりません。誰か説明できますか？

更新されましたが、まだ機能していません:

わかりました、解決しました

そして、次のようにreduceを使用します