問題タブ [greatest-common-divisor]

次の疑似コードを使用して、2 つの数値を入力して最大公約数を取得するプログラムを作成します。

これは私の現在のバージョンで、エラー:52:オペコードとオペランドの無効な組み合わせが表示されます。

私はアセンブリと nasm にまったく慣れていません。エラーまたは誤った構文を見つけるのを手伝ってくれることを願っています。

バイナリ法を使用して 2 つの分数の GCD を計算しています。この方法は、特定の数値を互いに減算する場合を除いて、完全に正常に機能します。

たとえば、1/6 から 2/15 を引くと、GCD には繰り返し数などがあるためだと思いますが、間違っている可能性もあります。

これは、この操作を完了するために使用しているコードです。デバッグ メッセージは永久に出力されます。

スタックしたときにこれを回避する方法はありますか、または例外を設定する方法はありますか?

独自の BigInteger 実装を行っているときに、拡張 GCD アルゴリズムに行き詰まりました。これはモジュラー乗法逆数を見つけるための基本です。よく知られているユークリッド アプローチはパフォーマンスが遅すぎ、ハイブリッド アルゴリズムとバイナリ アルゴリズムは 5 ～ 10 倍しか高速ではないため、従来のアルゴリズムに対するレーマーの修正が選択されました。しかし難しいのは、Lehmer's について説明することになると、私が見つけたすべての本 (Knuth、Handbook of Applied Cryptography、Internets など) には同じ欠点があることです。

1. 説明はいくつかのトリックに基づいています。
   • 入力数値は常に同じ長さです。
   • 抽象 CPU には符号付きレジスタがあり、数字と符号の両方を保持できます。
   • 抽象的な CPU には半無制限のレジスタがあります。つまり、オーバーフローすることはありません。
2. 逆余因子に焦点を当てることなく、基本的な GCD アルゴリズムのみが提供されます。

最初の問題については、実際の実装が見つからないことに最初は驚きました (GNU MP ライブラリを紹介しないでください。学ぶためのソースではありません)。明らかに論文「<a href="http://www.csie.nuk.edu.tw/~cychen/gcd/A%20double-digit%20Lehmer-Euclid%」のアイデアに基づいている.Net 4.0から20algorithm%20for%20finding%20the%20GCD%20of%20long%20integers.pdf" rel="nofollow">長い整数の GCD を見つけるための 2 桁の Lehmer-Euclid アルゴリズム" by Jebelean. 結果の関数は大きく、恐ろしく見えますが、うまく機能します。

しかし、Microsoft のライブラリは基本的な機能のみを提供し、補因子は計算されません。正確に言うと、一部の補因子は速記ステップで計算され、最初のステップではそれらの補因子は単純に最初のものですが、筆記ステップが実行された後は一致しなくなります。私の現在の解決策は、「実際の」余因子を「代用」の余因子と並行して更新することですが (最初のステップを除く)、パフォーマンスがゼロ以下に低下します: 関数はバイナリよりも 25-50 % 速く完了します基本モードでの方法。したがって、問題は、入力数値が完全に更新されるのはロングハンド ステップのみであるのに対し、補因子は各ショートハンド ステップの反復でも更新されることです。、したがって、レーマーのアプローチからのほとんどすべての利益を破壊します。

少しスピードアップするために、「融合乗算加算」関数を実装しました。これは、「融合乗算乗算減算」が実際に入力数値の更新に役立つためですが、今回の影響はごくわずかでした。別の改善は、通常は 1 つの補因子のみが必要であるという事実に基づいているため、もう 1 つの補因子はまったく計算されない可能性があります。これにより、オーバーヘッドが半分になります (通常、2 番目の数値は最初の数値よりも大幅に小さいため、さらに半分になります)。ただし、実際には、オーバーヘッドは予想の25 ～ 50% しか減少しません。

したがって、私の質問は次のようになります。

1. 実世界のハードウェア (サイズが制限された符号なしワード) での実用的な実装に結び付けられた、レーマーのアルゴリズムの本格的な説明はありますか?
2. 上記と同じですが、拡張GCD 計算に関するものです。

したがって、基本的なアルゴリズムのパフォーマンスに満足しているのと同じように、拡張モードの操作には反対のことが当てはまります。

x86アセンブリでGCDを繰り返し見つけようとしています。どういうわけか、残り = 0 であるため、ループは最初の反復後に終了し続けます。理由はありますか？

amazon.interviewstreet.com で、一部の入力に対して間違った回答が返されます (テストケースに使用する入力が明らかにされていないため、どれかわかりません)。

また、この実装がスタックオーバーフローを提供し続ける理由(これも、どの入力についてはわかりません)

何が足りないのか教えてください。プログラミング初心者でまだまだ初心者です。

gcd 関数を再帰的および反復的に実装する方法に関する投稿しか見つけることができませんでしたが、これは見つかりませんでした。Stackoverflowにあると思いますが、見つけられなかったので、重複した投稿である場合はお詫び申し上げます。

ウィキペディアの分析 (こちら) を見ましたが、それらの再帰関係を理解できませんでした。

C で再帰的に実装された GCD 関数の次の実装を検討してください。これには、両方の数値が正でなければならないという前提条件がありますが、実行時間には関係ありません。

ランタイムの分析を実行すると、すべての操作が O(1) であることがわかります。したがって、これまでの再帰関係は T(n) = O(1) + ??? であることがわかります。再帰呼び出しを分析するために、 a (mod b) を再帰呼び出しとして解釈して、再帰関係を適切に記述する方法がわかりません。