問題タブ [modular-arithmetic]

非再帰的なべき乗剰余を実装しました

もう1つは再帰的です

しかし、2 つのコードは正しい結果を生成しません。ウィキペディアの反復コードは正しい結果をもたらします。再帰バージョンで何が間違っていて、それを修正するにはどうすればよいですか?

h(y)として定義された関数を とします(a*y+b)mod m。したがってh(y)、値を取ることができますfrom 0 to m-1. 。これで、7 つの整数が与えられますa,b,x,n,c,d,m。h(x),h(x+1),h(x+2)...h(x+n)私たちのタスクは、 の値がh(x+i)の範囲に収まる[c,d]ようなの合計数を見つけることです。ここで、0<=i<=n 整数の制限は次のとおりです。

例えば。入力set {1,0,0,8,0,8,9}の場合、出力は 9 である必要があります。効率的なアルゴリズムを提案してください。ありがとう！！！

JavaScript には、それぞれ 16 進数を文字列として含む 2 つの変数があります。例えば：

今、私はそれらを追加したいです (したがって、結果は になるはずです'c0cb')。物事を少し簡単にするために、これにいくつかの制約を加えましょう:

• 数値は常に同じ桁数で構成されます (つまり、文字列の長さは同じです)。
• 0必要に応じて数字の前にs が付くため'001a'、 だけでなく になり'1a'ます。

一方で、物事を少し難しくする制約があります。

• 数値は上の例のように 4 桁ではなく、20 桁です。したがって、単純に 10 進数に変換して加算し、元に戻すことはできません。つまり、数値が JavaScript のタイプに対して大きすぎます(これが、この回答が機能しないnumber理由です)。
• オーバーフローは許されません。と を足す'ffff'と'0001'、結果は'0000'ではなくになり'10000'ます。つまり、すべての計算はモジュロ除算を使用して行う必要があります。

私は現在、これらすべてを解決するアルゴリズムを持っていますが、それは長く、あまり効率的ではなく、エレガントではありません。その考え方は、文字列を 1 文字ずつ調べて、それらを 10 進数に変換し、それらを追加し、それらを元に変換し、潜在的なオーバーフローを記憶することなどです。前述のように、それは完全に機能しますが、最善の解決策ではないと思います。

どうすればこれをより良い方法で解決できますか?

PS: Node.js でこれを行う必要があるため、これを行う既製のモジュールが利用可能であれば、これでまったく問題ありません :-)

CPU の仕様によってパフォーマンスがどのように影響されるかについての知識が不足しています。次のパラメーターを使用して、Windows プラットフォームでモジュラー計算 (DH キー交換) を実行するアプリケーションを実行しています。

モジュラー: 素数 = 4096 ビット

ジェネレーター: 2

指数: 256 ビット

2.4 GHz プロセッサと 4G RAM を搭載した 32 ビット Windows 7 でアプリケーションを実行すると、3 ～ 4 秒かかります。ただし、同じプロセッサ速度と 8G RAM を備えた 64 ビット Windows 7 で同じアプリケーションを実行すると、1 ～ 2 秒かかります。

私は理解しようとしていますが、モジュラー計算速度がARMサイズまたはCPUサポート（64ビット対32ビット）の影響を受けるかどうか混乱しました

私は方程式を解こうとしています:

私の現在の解決策：

(n + k) の剰余逆数がない問題セットに到達するまで、問題なく動作していました。

だから私の質問は、モジュラー逆数による乗算を含まない、これを解決する別の方法はありますか? たとえば、これらの提案のいずれかが私の問題に有効でしょうか?

大きな数の代わりに剰余のみを保持する mod の概念。

計算する式:

=> i=1 から i=N への合計 { i%m }

制約

1 ≤ N ≤ 10^9 1 ≤ m ≤ 10^9

10 ^ 9（大きな数）まで合計する必要がないように、モジュラスをどのように使用できますか。Java コードは、タイムアウトまたは CPU コードが原因で終了し、大きな数値の実行時にエラーが発生します。

CODE: k は出力される加算結果です。

スペース効率の良いモジュラー算術クラスを構築したいと考えています。モジュラス M は、インスタンス化中に修正される不変の属性であるため、同じ M を持つ値の大きな配列 (std::vector または別のコンテナー) がある場合、M は一度だけ格納する必要があるという考えです。

コンパイル時に M を修正できる場合は、テンプレートを使用して修正できます。

ただし、私のアプリケーションでは、M ランタイムを表現できるはずです。私が持っているものは次のようになります:

これは機能しますが、mod M 値の大きなベクトルは、必要なスペースの 2 倍を使用します。

根底にある概念上の問題は、異なるモジュライの Mod は、異なるタイプである必要があるにもかかわらず、構文的には同じタイプであるということだと思います。たとえば、次のようなステートメント

「自然に」実行時エラーを発生させる必要があります（私のバージョンでは、「手動で」発生します。チェックは、実装するすべてのバイナリ演算子と同様に、コピーコンストラクターに組み込まれています）。

では、Mod オブジェクトの型がモジュラスを記憶するように、ある種の動的型付けを実装する方法はありますか? これを解決する方法を教えていただければ幸いです。

これは、さまざまな数学的構造 (たとえば、同じセットに多くの順列を格納する、同じグループの要素など) で繰り返し発生する問題です。

編集：私が理解する限り、

• テンプレートは、クラスまたはリテラルによってパラメーター化された型です。

• 私が欲しいもの： const オブジェクトによってパラメータ化された型（const numこの場合、const Group&またはconst Group *constグループなど）。

これは可能ですか？

C++ で剰余算術(または) ( % ) 演算子を使用すると、範囲を指定して連続する数値を循環できます。

例えば：

範囲が 5 (または) モジュロ 5 の場合は、次のように循環できます。

0 1 2 3 4 0 (5) 1(6) 2(7) 3(8) 4(9) 0(10)........0 1 2 3 など

質問：

同様の意味で、範囲を指定して増加する数値を前方に移動し（上限まで）、減少する数値を逆方向に移動する（下限または0まで）ために使用できる算術関係/ C++トリックがあります。

例えば：

範囲 = 5 の場合

0 1 2 3 4 3 2 1 0 1 2 3 4 3 2 1 0...................... 0 1 2 3 など

以下のプログラムでは、特定の範囲内で順方向/逆方向を繰り返すために 2 つのアプローチを使用しました。

しかし、私は興味があります-特定の範囲内で順方向と逆方向を反復する最良の方法(C++トリック/数学関係)はありますか?.