問題タブ [bignum]

任意の大きな整数に対して Solovoy-Strassen 素数性テストを実装しようとしています。bignum も作成します (これは学術プロジェクトであるため、サードパーティの実装は使用できません)。bignum の次の構造を決定しました。

数字にはbase-32を使用します（したがって、部分積の場合はuint64_t、少なくとも部分積になると思います）。この決定は、以前に尋ねられた質問に基づいています。

私は立ち往生しています。任意のサイズの 10 進数として表された文字列を取得して、上記の bignum 構造に変換する方法がわかりません。

誰か教えてください。任意の文字列を uint16_t 配列に格納される 8 進数に変換するなど、より小さな例でもいいでしょう。

ありがとう。

宿題プロジェクト用の小さなbignumライブラリを書いています。カラツバ掛け算を実装するのですが、その前に単純な掛け算ルーチンを書きたいと思います。

オンラインで無料で入手できる「Modern Computer Arithmetic」というタイトルの Paul Zimmerman によって書かれたガイドに従っています。

4 ページに、小学校の乗算を実行する BasecaseMultiply というタイトルのアルゴリズムの説明があります。

B^j が 1, j 回の桁シフトであるステップ 2、3 を理解しています。しかし、A*b_j があるステップ 1 と 3 がわかりません。bignum の乗算がまだ定義されていない場合、この乗算はどのように実行されるのでしょうか?

このアルゴリズムの操作「*」は、単に繰り返し加算法ですか?

ここまで書いてきた部分です。私はそれらをユニットテストしたので、ほとんどの場合正しいようです：

bignum に使用する構造は次のとおりです。

現在利用可能なルーチン:

Ruby で NOT、AND、OR、XOR、<<、>> 演算子をいつ使用するかを知っているか、実際の例を誰かが持っているかどうか疑問に思っています。

私は 4 年間プログラミングをしてきましたが、これらのいずれかを使用する必要性に出くわしたことはありません。

ありがとう、-J

Rubyはこれをどのように行うのですか？イェルクや他の誰かが舞台裏で何が起こっているのか知っていますか？

残念ながら、私はCをよく知らないのでbignum.c、ほとんど役に立ちません。誰かが（平易な英語で）それが使用している奇跡のアルゴリズムの背後にある理論を説明できるのはちょっと興味がありました。

36806348825922326789470084006052186583833823203735320465595962143702560930047223153010387361450517521869134525758989639113039318944796977164583238219236607653663113200177617597793217865870366077846576581183082787698201412402294867197567813172495806442794990281049897327103078771678146741952418004073439899695293083250893411694596612017673512082315195977953685229009037745250223699083945341679064045611647113975154675004860218929102864097057476260018595022613824453018748921161586402113531207791201884463078030746220525280773775767209432069237310103251745951849752401512016516672418981676639724782417539480202822816002710062399887366743579907305461890685546048835142661131063402348904429186051035230191242660848880746231212659020683041378266455426041126637886662665375576362779656908293178564560081623689116814177499326748817170217219107273106921688166829462567949269614897699986871567144087420642721205671737309963971116890119744041659022652419278284289641541461168818739123204832773896582026593409310817205487518824659176087713165789563358657661185727701178249794352294501124843043920129701511946873071236400763937391081195343030947683245323012399675023571078708664107031028872538959513893678471527415042649541619666983267998025343680786418716005458904566402715881795854937449051239905544881914848704936367461166460989003008854959199246636005004256627034833091179548764704594930128661465865007129969565224526608067298992179934250929163533082787426478958730697447232771870430635244592599615561915378391323721271601041029499987756974528735342290344338756274645252286042041668901973291379807377328153357091020520776715712817418487335705083075277790004194325673849906782148842105387086902273869881605981057922100256088299988476325216174756689383517855896114234930446650640237355631870717571086698303531312206832110245782411201496938722547625934287286636355038384072001083290669536055355664754529584996627998083056124296001365452951499511358490905081301519892828320218919461550140343555306014771313976632319574332484804734757547322819849234323149658088505733051094905849052773866269748029358361223313450207818201434719252239144908773857908158579561354719859966127356766244149040186283981782268657311299866303886831497425976603934089402430838345103987467406116053824239280358075823275574931084369419478799155664790709184960070471200337110392696713740812571363139669934373328801425408481937938055517477702084356868992734894948420104259527193263068574761383538543442480702461516184822371598979717815516995112105228514915713769771885044970884333047530144037309461111963136170293634226321938279399689598833170189069368986245902077559943950687000513075042794974707139009525675920342667180337706810974462990976917631952683782436492684473054552464649432182624192510715804056160770636448491097834866938814201683879290292615897935543248361151758860596774539395

これは、Project Euler サイトの問題 3です。

私は解決策を求めているわけではありませんが、おそらく私のアプローチが何であるかを知っていると思います. 私の質問に対して、 unsigned int を超える数値をどのように処理しますか?

これに対する数学的アプローチはありますか?もしそうなら、どこでそれについて読むことができますか?

C++で任意のサイズの整数を2つ追加したいと思います。どうすればこれを行うことができますか？

JavaScriptまたはビルトイン用のbignumライブラリがありますか？

？

私のユーザーは、実行可能ファイルをダウンロードして「この実行可能ファイルはコンピュータに害を及ぼす可能性があります」という警告画面をクリックしてインストールするよりも、Webページに数字を入力して結果が出るまで7秒待つことを好むと思います。

http://github.com/silentmatt/javascript-bigintegerまたはhttp://www.mainebrook.com/john/fun/euler.htmlをベースにすることを検討しました。または、JavaScriptからapfloatなどのJava bignumライブラリを呼び出すことをお勧めしますか？

階乗計算を高速化する数学的な「最適な」ベースはありますか？

背景：楽しみのために、私は自分のbignumライブラリを実装しています。（-：これは私の最初の間違いですか？:-)。n階乗（n！）の正確な値（10進数）を出力することにより、内部表現と回帰テストで使用されるさまざまなベースを実験しています。

私のbignumライブラリが整数を表し、乗算を行う方法では、時間は内部表現n​​！の「1」ビットの総数に比例します。内部表現で2、4、8、16、2 ^ 8、2 ^ 30などを使用すると、特定の数値に対してまったく同じ「1」ビットの総数が得られます。

間違いがない限り、基数18で表される階乗（n！）は、基数10または基数16または基数19で表される同じ値よりも「1」ビットが少なくなります。したがって、（原則として）基数を使用します。 18を使用すると、10進数または2進数の2 ^ w基数または基数19を使用するよりも、bignumライブラリの実行速度が速くなります。これは、n！基数10または基数16または基数19よりも基数18で印刷した場合、より短いか、より多くの「末尾ゼロ」があるか、またはその両方です。基数18よりもさらにうまく機能する他の基数はありますか？言い換えれば、nを表すベースはありますか？ベース18よりもさらに少ない「1」ビットで？

これは、「bignumライブラリと素数判定アルゴリズムの便利なベースは何ですか？」の重複ではありません。「2と3の因子がたくさんある、大きな階乗であることがわかっている整数を処理するための最適なベース」は、「小さな因子を持たず、おそらくプライム」。（-：階乗計算を高速化していますか？おそらく他の種類の計算を犠牲にして-私の2番目の間違いですか？:-)

編集：例：

（私は多かれ少なかれ右側の数字をコンマなしで保存し、それにメタデータのオーバーヘッドもあります）。（「ベースを増やすと、特定の数値を表すために使用する「1」ビットが少なくなる」、または「ベースを増やすと、特定の数値を表すために使用するゼロ以外の数字が少なくなる」と考える人もいるかもしれません。例は、それが常に正しいとは限らないことを示しています。）

各桁を小さな整数（「int」または「longint」または「byte」）として格納しています。数字を保存する他の合理的な方法はありますか？私のコンピュータはこれらの整数を2進数で格納していると確信しています。各「1」、「2」、「4」、「8」、および「G」の数字は1つの「1」ビットを使用します。各「3」、「5」、「6」、「9」、および「A」の数字は、2つの「1」ビットを使用します。各「7」および「B」桁は3つの「1」ビットを使用します。各「F」桁は4つの「1」ビットなどを使用します。

この値（16！）の10進数と8進数の両方の表現には、14"1"ビットが必要です。そのため、以前の計算で間違いを犯しました。すべてのnについて、nを表します。8進数では、同じ値を10進数で表すよりも「1」ビットが常に少ないとは限りません。しかし、疑問はまだ残っています。大きな階乗を格納するために必要な1ビットの数が最も少ない他の「最適な」ベースはありますか？

誰かが尋ねます：「あなたはそれらの番号をどのように保存しますか？」さて、それはまさに私の質問です-nの形の数を保存する最良の方法は何ですか！？内部的には、基数10、2の累乗の基数、基数18、またはその他の基数の数字を使用できます。どれが一番いいですか？これらの整数を1Dの数字配列として内部的に格納できますが、すべての桁を格納するには長さが必要です。100を印刷する合理的な方法はありますか？そのような配列なしで10進数で？

私はRSA暗号をゼロから実装する方法を理解しようとしています(知的演習のためだけに)、私はこの点で立ち往生しています:

暗号化の場合、c = m ^e mod n

現在、e は通常 65537 です。m と n は 1024 ビットの整数です (たとえば、128 バイトの配列)。これは明らかに標準的な方法には大きすぎます。これをどのように実装しますか？

ここで累乗について少し読んでいますが、クリックしていません：

ウィキペディア - 二乗による累乗

この章(セクション 14.85 を参照)

ありがとう。

編集：これも見つかりました-これは私が見るべきものですか？ウィキペディア-剰余累乗

bignumの筆算を実装しようとしています。組み込みプログラミングの制限により、残念ながらGMPのようなライブラリを使用することはできません。その上、私はそれを実装する方法を学ぶ知的運動が欲しいです。これまでのところ、任意の長さのバイト配列を使用して加算と乗算を行っています（したがって、各バイトはベース256桁のようです）。

除算/モジュラスの実装を開始しようとしていますが、どこから始めればよいですか？ネット上で高度に最適化された（別名読み取り不可能な）コードをたくさん見つけましたが、それは私を助けません。また、理論と実装の間のギャップを埋めることができない高度に技術的な数学のホワイトペーパーをたくさん見つけました。 。

誰かが人気のあるアルゴリズムを推奨し、それが実装に傾いている簡単で理解しやすい説明を私に指摘できれば、それは素晴らしいことです。

-編集：被除数が約4000ビット、除数が約2000ビットの場合に機能するアルゴリズムが必要です

-編集：このアルゴリズムはbase-256で機能しますか？http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html

-編集：これは私が実際に使用すべきアルゴリズム（ニュートン除算）ですか？http://en.wikipedia.org/wiki/Division_(digital)#Newton.E2.80.93Raphson_division