問題タブ [modular-arithmetic]

Javascript は、次のコード スニペットを -1 に評価します。

剰余定理は a = bq + r で 0 ≤ r < b であることを理解しています。上記の定義を考えると、答えは 3 ではないでしょうか? JavaScript が -1 を返すのはなぜですか?

私のプロジェクトでは、問題の一部があります。しかし、簡単にするために、ここで問題が定式化されています。2 つの正の互いに素な整数があります:aとb、ここでa < b. a1 ～の倍数b-1がリストされ、その後に による剰余演算が続きbます。

a mod b, 2*a mod b, 3*a mod b, ... ,(b-1)*a mod b

さて、別の整数がありますn ( 1 <= n < b)。リストの最初の数字を通して、たとえば( )nよりも小さい数字がいくつあるかを見つける必要があります。これはブルート フォース アプローチで実行できるため、 .m1 <= m < bO(n)

例：

a=6, b=13, n=8, m=6

リストは次のとおりです。

6, 12, 5, 11, 4, 10, 3, 9, 2, 8, 1, 7

これは、1 から 12 までの数値の順列です。これは、別の数値、つまり を含めると、任意の 2 つの互いに素なモジュラス演算によって数値の順列が生成されるため0です。を取るa= 2, b=13と、リストは になり2, 4, 6, 8, 10, 12, 1, 3, 5, 7, 9, 11、パターンが得られます。aとが非常に大きい場合b(私のプロジェクトでは最大 10^20 になる可能性があります)、そのような大きな数のパターンを推測する方法がわかりません。

例に戻るとn = 8、リストから最初の数字を取得します。

6, 12, 5, 11, 4, 10, 3, 9

less-than演算子をで適用すると、以下のリストで説明するように、3m = 6未満の合計数が得られます。m

0, 0, 1, 0, 1, 0, 1, 0

ここで、0 は 未満ではないことを示しm、1 は未満であることを示しmます。

上記のアルゴリズムは でありO(n)、 の範囲では受け入れられない[0, 10^20]ため、コミュニティはヒント/手がかり/ヒントを提供して、O(log n )解決策、またはより良いO(1)解決策に到達できるようにすることができますか?

(a/b) % m (a = x1*x2*.... で、数値 x1、x2、.. は非常に大きい場合) をどのように計算しますか。

% m だけを見つける必要がある場合は、 (x1%m) * (x2%m) *... を使用して簡単に実行できますが、この場合、分母 'b' に何かがある場合、どうすればよいですか?それを計算することについて？

これが (a % (m*b)) / b として行われていることをどこかで読みました。これが本当かどうか疑問に思っていましたが、どうすればそれを証明できますか?

複数のプロセッサを使用して (大きな) 定数を法として大きな整数を乗算するための時間の複雑さについて知りたいと思っています。要するに、除算と剰余は乗算を使用して実装することもできるため、基本的には単なる整数乗算です (例:逆数乗算またはバレット削減)。

現在知られている整数乗算アルゴリズムの実行時間は、下限によっておおまかに制限されていることを知っていますo(n * log n)。私の調査では、これがシングル コアまたはマルチ コア マシン用であるかどうかを確認できませんでした。ただし、アルゴリズムは分割統治法を使用しているように見えるため、これはシングルコアマシン用であると考えています。

m私の質問は、コアに実装された並列整数乗算アルゴリズムの時間計算量の現在知られている下限は何ですか? o(n)十分なコアが与えられた場合、下限以下の時間計算量を達成できますか? (つまり ifは ?mに依存しnます) ここでo(n)は、手元にある整数の入力サイズについて説明します。

これまでの私の研究では、並列 FFT 乗算を使用した高速化を主張するいくつかの論文を読みました。残念ながら、これらは経験的な高速化 (たとえば、「これこれのコンピューターで 6 コアを使用して 56% の速度向上」) を主張するだけであり、時間の複雑さの境界で表される理論的な高速化を説明できません。

「最速」の整数乗算アルゴリズムがまだ見つかっていないことは承知しています。これはコンピューター サイエンスの未解決の問題です。私は単に、そのような並列アルゴリズムの現在知られている範囲について調べているだけです。

更新 #1 : ユーザー @delnan がNC 複雑性クラスに関する wiki ページにリンクしました。そのwikiページでは、整数乗算はNCにあると述べています。つまり、プロセッサにO((log n)^c)アルゴリズムが存在します。O(n^k)これは、答えに近づくのに役立ちます。今のところ答えられていない部分は、整数乗算のcおよびk定数とは何か、またどの並列アルゴリズムがこの目的に適しているかということです。

更新 #2 :コーネル大学のコンピューター サイエンス コースのこの PDF ファイルの 12/15 ページによると、NC 複雑度クラスの整数乗算はプロセッサでO(log n)時間がかかります。O(n^2)また、これを行う方法についてのアルゴリズムの例についても説明します。この質問に対する適切な回答をすぐに書きます。

私の好奇心を満たすための最後の質問: "just"またはプロセッサの現在知られている時間の複雑さについて何か知っている人はいO(n)ますか?O(sqrt(n))O(log n)

たとえば、モジュラー算術の基本的な数学的形式を理解しています。

ただし、次の暗号化と復号化のコード例では、他の数学と一緒に使用されており、何に使用されているのかわかりません。

誰か説明してくれませんか？

私はこの一見単純な問題に取り組んでおり、数字のすべての桁に 1 を追加する必要があります。例: 番号 = 1234 ; 出力 = 2345

それは簡単ですが、9 がそれらの数字の 1 つである場合、加算の法則により、その 9 は 0 に置き換えられ、左側の数字に 1 が追加されます (9 + 1 = 10、したがって、位の値 = 0 & キャリーオーバー = 1) 例: number = 1239 ; 出力 = 2350

誰かが私に説明してもらえますか、どのロジックを使用すればよいですか? 剰余算術の行に何かが見えますが、それを実装する方法が本当にわかりません。ありがとう ：）

次のモジュール式は可能ですか:

例：

たとえば Maple に聞いてみたいjのは、次のような場合です。

10^j mod 543 = 82

これをメイプルに聞いたらどうですか？

また、jパソコンを使わずに解決する方法はありますか?