高速 GCD 計算アルゴリズムに関する情報を探しています。特に、その実現に注目したい。

私にとって最も興味深いもの: - Lehmer GCD アルゴリズム - Accelerated GCD アルゴリズム - k-ary アルゴリズム - FFT を使用した Knuth-Schonhage。高速化された GCD アルゴリズムに関する情報はまったくありません。中程度の入力 (〜 1000 ビット) で最も効果的で高速な gcd 計算方法として言及されている記事をいくつか見ただけです。

理論的な観点からは、それらを理解するのは非常に難しいように見えます。リストからアルゴリズム\パーツを実現したコード（C ++で望ましい）を共有するか、これを行った経験を共有してください。また、情報、コメント、アドバイス、調べるべき場所を教えていただければ幸いです。大きな整数を扱うクラスがありますが、それを扱うメソッドがありません。確かに、Euclid と Binary gcd アルゴリズムを除いて、今のところ私には明らかです。問題ありません。私が最後に取得したい主なもの: 実現のコード lehmer gcd. （リストのほうが簡単です）

私は混合数詞クラスを書いているので、すばやく簡単な「最大公約数」関数が必要です。誰かが私にコードまたはコードへのリンクを教えてもらえますか？

テキスト文字列 'a:b:c:d' になるメソッドを Objective-C で書きたいと思います。4 つの UISteppers があります (それらの値はそれぞれラベルに表示されます)。これらの 4 つの数値の比率を、0 の場合も含めて最小の整数形式で表示したいと思います。

例えば。a=6、b=4、c=0、d=0 文字列 = 3:2:0:0

http://macscripter.net/viewtopic.php?id=35759など、最大公約数を見つけるさまざまな方法を見つけました。しかし、私は本当に iOS に慣れていません。これは Hello World の後の最初のアプリであり、数学関数やメソッドの宣言、定義、呼び出しはまだ謎です。

手伝ってもらえますか？

私はSPOJ問題PGCDを解決しようとしています。これは、最大公約数のテーブルにいくつの素数が現れるかを尋ねます。

私の頭に浮かんだ最初のアイデアは、ふるい分けによって最初に素数を生成することです。

次に、各素数pについて、aとbが指定された境界よりも小さいペア（a、b）がいくつ満たされているかを確認します。GCD(a,b)=p

たとえば、（20、20）未満のペアがGCD（a、b）= 7を満たすペアはいくつありますか？

もちろん、前述のように、aとbは制限されています。

では、GCDを逆にすることは可能ですか？それとも、このソリューションは完全に無効ですか？

TI-Basic で任意の 2 つの数値 (非整数を含む) の GCD を検出できるプログラムを実装することにしました。私はこれを Java で問題なく使用したので、動作することはわかっています。TI-Basic では問題なく動作しますが、組み込み関数と比較するとgcd(非常に遅くなります。関数はgcd(ミリ秒単位で結果を取得するようですが、私の場合は数秒かかる場合があります。TI-Basic が定義済みの電卓関数よりも遅いのはなぜですか?

コード

検査用に、TI-Basic でのプログラムのコードを次に示します。

免責事項:これは、TI-84 を見てここに入力した結果です。誤字脱字があるかもしれませんが、なるべくそのままにしてみました

これが何を意味するのか分からない方のために、以下に疑似コードを示します。

まず第一に、小さな説明です。私はこの問題で AC を取得しましたが、私のより良いアプローチ (これは数学的に同等であり、AC ソリューションと仮定します) は WA の評決を得​​ることです。

1 つの友好的な番号と N の非友好的な番号があります。友好的な数を正確に分割し、非友好的な数を分割しない数がいくつあるかを見つけたいと考えています。

入力フォーマット:

入力の最初の行には、スペースで区切られた 2 つの数値 N と K が含まれています。N は友好的でない番号の数、K は友好的な番号です。入力の 2 行目には、スペースで区切られた N 個の不適切な数字が含まれています。

出力フォーマット：

答えを 1 行で出力します。

サンプル入力:

8 16
2 5 7 4 3 8 3 18

サンプル出力:

1

説明：

指定された友好的な数 16 の約数は { 1, 2, 4, 8, 16 } であり、非友好的な数は { 2, 5, 7, 4, 3, 8, 3, 18 } です。1 はすべての友好的でない数を割り、2 は 2 を割り、4 は 4 を割り、8 は 8 を割りますが、16 はそれらのどれも割りません。したがって、友好的な数を割り、非友好的な数を割り切らない数は 1 つだけ存在します。したがって、答えは 1 です。

私のアルゴ（ACを取得した）は次のとおりです。

1. 0<=i である可能性のある不適切な数値を input[i]

2. 各input[i]について、gcd(input[i],k)を見つけます。

3. セット内の範囲 (0,n) 内のすべての i について、gcd(input[i],k) のすべての因子を格納します。このセットを、PossibleFactors と呼びましょう。

4. k の因子ごとに、PossibleFactor のいずれかの要素を除算するかどうかを確認します。「いいえ」の場合は、回答数を増やします

以下を想定してアルゴリズムを修正しました。

gcd(input[i],k) のすべての因数を set に格納する代わりに、範囲 (0,n) 内のすべての i について gcd(input[i],k) の lcm を見つけます。これは、次の LOC で簡単に実行できます。

ここで、k のすべての因数について、それらが lcm を分割するかどうかを確認します。そうでない場合は、カウントを増やします。

しかし、この仮定は私にWAを与えています。それは私の論理に欠陥があるためですか？はいの場合、2つのアプローチの違いを（可能であれば数学的な証明で）指摘してください。

参照用の2番目のアプローチを使用したコードを次に示します（およびバグの可能性があります）

次の Euclid アルゴリズムの実装を考えてみましょう。

ウィキペディアの優れた証明は、アルゴリズムが「常に O(h) 未満の分割を必要とすることを示しています。ここで、h は小さい数 b の桁数です」。

ただし、チューリング マシンでは、a mod b を計算する手続きの時間計算量は O(a+b) です。私の直感といくつかの大規模なテストによると、ユークリッドのアルゴリズムの複雑さは、チューリング マシンではまだ O(a+b) です。

それを証明する方法について何か考えはありますか？

Haskellの人は初めてです。gcd実行可能ファイルを書き込もうとしています。

このコードをコンパイルすると、次のエラーが発生します。

問題がどこにあるのかわかりません...これが私のコードです。

私が知っているのはread、文字列をintに変換するのに役立つということだけです。

このプログラムでは、2 つの数値の GCD を見つけようとしています。しかし、私が得た結果は「浮動小数点例外（コアダンプ）」です。何が問題ですか？私が生成しようとしているコードは

私が生成したアセンブリファイルは次のとおりです。

一方、このアセンブリコードは機能します

ラベル.L0で、％eaxレジスタの値を確認すると、正しい値が得られます。しかし、ecxレジスタの値を確認すると、ゼロになります。どうしてか分かりません。おそらくこれが、浮動小数点のセグメンテーション違反が発生する理由です。誰かが私にその理由を理解するのを手伝ってもらえますか？

私が生成しようとしているロジックは

浮動小数点エラーを与えるアセンブリファイルは次のとおりです。