問題タブ [modulo]

128 ビットの符号なし整数 A と 64 ビットの符号なし整数 B があります。計算する最も速い方法は何A % Bですか? A を B で割った (64 ビット) 剰余ですか?

これを C またはアセンブリ言語で実行しようとしていますが、32 ビット x86 プラットフォームをターゲットにする必要があります。残念ながら、これは、128 ビット整数のコンパイラ サポートや、単一の命令で必要な操作を実行する x64 アーキテクチャの機能を利用できないことを意味します。

編集：

これまでの回答ありがとうございます。ただし、提案されたアルゴリズムは非常に遅いようです.128ビット×64ビットの除算を実行する最速の方法は、64ビット×32ビットの除算に対するプロセッサのネイティブサポートを活用することではないでしょうか? いくつかの小さな分割に関して、より大きな分割を実行する方法があるかどうかは誰にもわかりませんか?

Re: B はどのくらいの頻度で変わりますか?

主に一般解に興味があります。A と B が毎回異なる可能性がある場合、どのような計算を行いますか?

しかし、2 番目に考えられる状況は、B が A ほど頻繁に変化しないということです。各 B で割るために 200 もの A が存在する可能性があります。この場合、あなたの答えはどのように異なりますか?

C++ で 2 つの整数の間で mod 操作を実行するにはどうすればよいですか?

モジュラス(%) 演算子が除算の余りを計算することは知っています。モジュラス演算子を使用する必要がある状況をどのように特定できますか?

モジュラス演算子を使用して、数値が偶数か奇数か、素数か合成かを確認できることは知っていますが、それだけです。私は残りの点で考えることはあまりありません。モジュラス演算子は便利だと思います。それを活用する方法を学びたいと思います。

モジュラス演算子が適用される場所を特定するのに問題があります。さまざまなプログラミングの状況で、問題を見て「おい、除算の残りはここでうまくいくだろう!」と気付くのは難しいことです。

頂点とエッジの両方について、リンクリストを使用してグラフを実装しましたが、これがダイクストラアルゴリズムの問​​題になりつつあります。前の質問で述べたように、隣接行列を使用するこのコードを変換して、グラフの実装を操作しています。

問題は、最小値を見つけると配列インデックスを取得することです。グラフの頂点が代わりに配列に格納されている場合、このインデックスは頂点インデックスと一致します。そして、頂点へのアクセスは一定になります。

グラフの実装を変更する時間はありませんが、一意の番号（ただし、0で始まらないもの、100090000のようなもの）でインデックス付けされたハッシュテーブルがあります。これが問題です。必要なときはいつでも、モジュロ演算子を使用して、0から頂点の総数までの数値を取得します。

これは、数値からの配列インデックスが必要な場合には問題なく機能しますが、配列インデックスからの数値が必要な場合（一定時間で計算された最小距離頂点にアクセスするため）、それほど多くはありません。

100090000 mod 18000=10000や10000invmod18000 = 100090000のように、モジュロ演算を逆にする方法を検索しようとしましたが、その方法が見つかりませんでした。

次の方法は、上記の例でarr [10000] = 100090000のような参照配列を作成することです。これで問題は解決しますが、グラフ全体をもう一度ループする必要があります。

現在のグラフの実装で、より良い/より簡単なソリューションはありますか？

演算子を使用せずにモジュロ演算子を C の関数として実装するにはどうすればよいでしょうか?

プログラムでサイズ 16 の 1 次元整数配列として表す 4x4 ゲームボードがあるとします。

特定のインデックスの上、下、左、右の正方形のインデックスを取得するにはどうすればよいですか?

たとえば、次のようになります。

このボードを表すもの

現在、ボードのインデックス #8 (値 = 7) にいるとしましょう。4 (値 = 3)、5 (値 = 6)、10 (値 = 11) のインデックスを取得し、ボードの右端にあるため、右の正方形がないことを認識するにはどうすればよいですか。

モジュラス計算を使用する必要があることはわかっていますが、隣接する正方形のインデックスを取得する正しい方法を考え出すことができません。

みたいなことを考えている...

これは正しいアプローチのように思えますか?

モジュラス除算がどのように機能するのかよくわかりません。計算27 % 16してしまいましたが11、理由がわかりません。

オンラインで素人の言葉で説明を見つけることができないようです。誰かがここで何が起こっているかについて非常に高いレベルで詳しく説明できますか？

数値の数学モジュラス用のライブラリ関数がc＃にありますか？これにより、正の整数を法とする負の整数が正の結果を生成する必要があることを具体的に意味します。

例を提供するために編集：

-5モジュロ3は1を返す必要があります

このスクリプト言語には、% または Mod() がありません。数値の小数部分を切り取る Fix() があります。肯定的な結果だけが必要なので、頑固になりすぎないでください。

最近、モジュラー指数関数を実装しようとしています。私は VHDL でコードを書いていますが、よりアルゴリズム的な性質のアドバイスを探しています。剰余累乗器の主要コンポーネントはモジュラー乗算器で、これも自分で実装する必要があります。乗算アルゴリズムに問題はありませんでした。加算とシフトだけであり、すべての変数が何を意味するのかをうまく理解して、かなり妥当な時間で乗算できるようにしました。

私が抱えている問題は、乗算器でモジュラス演算を実装することです。繰り返し減算を実行するとうまくいくことはわかっていますが、遅くなります。モジュラスをシフトして、モジュラスの大きな倍数を効果的に減算できることがわかりましたが、これを行うためのより良い方法がまだあると思います。私が使用しているアルゴリズムは次のように機能します (奇妙な疑似コードが続きます)。

それで...これは良いアルゴリズムですか、それとも少なくとも始めるのに良い場所ですか? ウィキペディアではモジュロ演算を実装するためのアルゴリズムについてはあまり議論されていません。他の場所を検索しようとすると、非常に興味深いが信じられないほど複雑な (そして多くの場合無関係な) 研究論文や出版物を見つけることができます。私が見ていないこれを実装する明白な方法がある場合は、フィードバックをいただければ幸いです。