問題タブ [discrete-mathematics]

私の大学の離散数学コースでは、教師が学生にアッカーマン関数を示し、紙の上で関数を開発するよう学生に割り当てます。

再帰最適化のベンチマークであることに加えて、アッカーマン関数には実際の用途がありますか?

私の問題は(g^x) mod p、JavaScript ですばやく計算することです。^指数modはモジュロ演算です。すべての入力は非負の整数で、x約 256 ビットあり、p2048 ビットの素数であり、g最大 2048 ビットの場合があります。

JavaScript でこれを実行できるソフトウェアのほとんどは、JavaScript BigInt ライブラリ ( http://www.leemon.com/crypto/BigInt.html ) を使用しているようです。このライブラリでこのようなサイズの累乗を 1 回実行すると、遅いブラウザ (Firefox 3.0 と SpiderMonkey) で約 9 秒かかります。少なくとも 10 倍高速なソリューションを探しています。二乗と乗算 (二乗によるべき乗、http://en.wikipedia.org/wiki/Exponentiation_by_squaring ) を使用するという明白なアイデアは、2048 ビットの数値には遅すぎます: 最大 4096 の乗算が必要です。

ブラウザのアップグレードはオプションではありません。別のプログラミング言語を使用することはオプションではありません。番号を Web サービスに送信することはできません。

実装されているより高速な代替手段はありますか?

更新:以下の outis の回答に記載されている記事http://www.ccrwest.org/gordon/fast.pdfで推奨されているように、いくつかの追加の準備 (つまり、数百乗の事前計算) を行うことで、2048-最大で 354 のモジュラ乗算のみを使用するビット モジュラべき乗。(従来の平方乗算法は非常に遅く、最大 4096 の剰余乗算を使用します。) そうすることで、累乗剰余を Firefox 3.0 では 6 倍、Google Chrome では 4 倍高速化します。4096/354 の完全な高速化が得られない理由は、BigInt の累乗剰余アルゴリズムが、モンゴメリー削減 ( http://en.wikipedia.org/wiki/Montgomery_reduction )を使用するため、2 乗乗算よりも既に高速であるためです。 .

更新: BigInt のコードから始めて、手動で最適化された (およびインライン化された) カラツバ乗算 ( http://en.wikipedia.org/wiki/Karatsuba_algorithm ) の 2 つのレベルを実行する価値があるように思われ、その後でベース 32768 O( n^2) 乗算は BigInt で実装されます。これにより、2048 ビット整数の乗算が 2.25 倍高速化されます。残念ながらモジュロ演算は速くなりません。

更新: http://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf で定義されている修正された Barrett リダクションと、からつばの乗算と事前計算の累乗 ( http://www.ccrwest.org/gordon/で定義されている) を使用します。 fast.pdf )、Firefox 3.0 では、1 回の乗算に必要な時間を 73 秒から 12.3 秒に短縮できます。これは私ができる最善のようですが、それでも遅すぎます。

更新: Flash Player の ActionScript 2 (AS2) インタープリターは、Firefox 3.0 の JavaScript インタープリターよりも遅いように見えるため、使用する価値がありません: Flash Player 9 の場合は 4.2 倍遅く、Flash Player の場合は10、2.35倍遅いようです。数値計算における ActionScript2 と ActionScript3 (AS3) の速度の違いを知っている人はいますか?

更新: Flash Player 9 の ActionScript 3 (AS3) インタープリターは、JavaScript int Firefox 3.0 とほぼ同じ速度であるため、使用する価値はありません。

更新: Flash Player 10 の ActionScript 3 (AS3) インタープリターは、 の代わりに を使用し、intの代わりに を使用すると、Firefox 3.0 の JavaScript インタープリターよりも最大 6.5 倍高速になります。少なくとも、2048 ビットの大きな整数の乗算では 2.41 倍高速でした。そのため、可能な場合は Flash Player 10 で実行して、AS3 でべき乗剰余を実行する価値があるかもしれません。これは、Google Chrome の JavaScript インタープリターである V8 よりもまだ遅いことに注意してください。さまざまなプログラミング言語と JavaScript の実装の速度比較については、http://ptspts.blogspot.com/2009/10/javascript-and-actionscript-performance.htmlを参照してください。NumberVector.<int>Array

Update: There is a very fast Java solution, which can be called from the browser's JavaScript if the Java plugin is installed. The following solution is about 310 times faster than the pure JavaScript implementation using BigInt.

Can anyone translate this code to Silverlight (C#)?

私は基本的な大学の微積分以上の数学の授業を受けていません。しかし、プログラミングの過程で、ブログや読書から多くの数学や計算機科学を学びました。私はまともな数学の心を持っていると心から信じています。たとえば、プロジェクトオイラーを楽しんで成功しています。

私は飛び込んで、いくつかのクールな数学、特に離散数学、集合論、グラフ理論、数論、組み合わせ論、圏論、ラムダ計算などを学び始めたいと思っています。これまでの私の印象は、これらを受け入れる準備が整っているということです概念レベルではありますが、私は数学の言語と記号に非常に苦労しています。私はただ「言語を話す」ことはしません、そして私はそれを学ぼうとしていますが、私は行くのが非常に遅いです。数式や用語の重い段落を1つでも処理するには、数時間かかる場合があります。そして、ええ、私は用語と定義を調べることができますが、それは私が学ぼうとしていることの理論的な単純さを非常に曖昧にする非常に厄介なプロセスです。

中断したところに戻って、中級レベルの数学の教科書を手に入れ、その考え方を身につけるために演習に真剣に時間を費やさなければならないのではないかと本当に恐れています。しかし、これは驚くほど退屈に聞こえるので、他の誰かがこれについて何かアイデアや経験を持っているのだろうかと思いました。

10 進数 (基数 10) では、1/30.33333 の繰り返しにしか近似できません。

近似値としてしか表現できない 2 進法に相当する数は?

Michael Feather の SCNA トーク「Self-Education and the Craftsman」を見て触発されたので、離散数学が役立つことが証明されているソフトウェア開発の実際の例について聞くことに興味があります。

こんにちは私はRSA暗号システムをセットアップしようとしています。d個の選択された素数を除くすべての値がありp=1889ます：q=2003、、、、、n=3783667phi=3779776e= 61

私はdを見つけて行き詰まりました誰かが私がそれを理解するのを手伝ってくれるでしょうか？

RSA暗号システムのセットアップ

• 2つの大きな異なる素数pとqが選択され、n = pqとΦ(n) = (p − 1)(q − 1)が計算されます。

• 整数は、の逆数が計算eされるように選択されます。gcd(Φ(n), e) = 1d = e^(−1)ZΦ(n)

  ed≡1（modΦ（n））。

• その後、番号、、、pおよびqはΦ(n)破棄されます。

• ペア(e, n)は公開暗号化キーとして公開されます
• 番号dは秘密の復号化キーです。

#103 と #105 は解決しましたが、#106を理解するのに苦労しています。具体的には、25 という数字はどこから来たのでしょうか?

要素数が等しい 2 つの互いに素な部分集合について話している場合、

要素数が等しくない素集合を含めると、

ここで何が欠けていますか？前もって感謝します。

いくつかのオブジェクトを含む配列リストがあり、そのオブジェクトの順列を取得する必要がありますか?どうすればよいですか? MyList が、4 つのオブジェクトを含む配列リストであるとします。

arraylist count は 4 なので、4!=24 が必要です。そのオブジェクトの 24 個の順列が必要です。どうすればC#でそれを行うことができますか.私を助けてください.

ありがとう！

データ構造とアルゴリズムに関する本を読みたいのですが、データ構造の本に記載されている資料を理解するための前提条件として非常に重要と考えられる離散数学の特定のトピックがあるかどうかを知りたいです。

PS私は独学のプログラマーです。私はコンピュータサイエンスのコースを受講しませんでした。

私は、基本的にブルート フォース攻撃を使用して、Web アプリケーションがクラッシュしないことをテスト/検証するという壮大な考えを持っています。

単体テストや IoC のことを始めさせないでください。これはまったく別のものです。

私がやっていること、そして私が助けを求めていることは、プログラムの状態の一部を調査するインテリジェントな徹底的な検索を作成することです。

私が持っているのは、私ができることを含む Web ページです。クリックは 1 つのことであり、テキスト入力は別のことであり、ラジオ ボタンやドロップダウン リストなどの一部の入力は特定の値に制限されています。かなり基本的なこと。最終的にイベントと値のセットが有限になり、モデル化したいのは状態の進行です。これはある意味で FSM の最適化かもしれませんが、目標は、イベントと値の任意の順列を体系的に調べて、何が起こるかを確認することです。

問題が見つかった場合、明確なテスト ケースを提示できるように、できるだけ少ない労力でそのエラーを引き起こしたいと考えています。

これは正式な検証方法に関連しており、経験のある人からの助けや洞察を求めています.