問題タブ [bigint]

gmp を使用して複雑な操作を実行しています。Botan を使用して暗号化機能を実行したいと考えています。問題は、どちらも独自の Bigint 関数を持っていることです。そのため、gmp 関数で使用される bigint 値を Botan 関数に提供する際に問題が発生します。

誰でもこれを手伝ってもらえますか？

私は階乗プログラムに取り組んでいましたが、1000 の階乗を見つけようとするとプログラムが機能しませんでした。大きな整数が解決策だと思います。彼らはどのように機能しますか？(C または C++ のいずれか)

STLにはBigIntクラスの実装がありますか？（コンテナに保持されている桁数の多い数値）

私は、大きな数を除算するアルゴリズムについて考えていました。剰余でbigintCをbigintDで除算します。ここで、基数bでのCの表現がわかっており、Dの形式はb^k-1です。例で示すのがおそらく最も簡単です。C=21979182173をD=999で割ってみましょう。

• 数字を3桁のセットとして書き込みます：21 979 182 173
• 左から順に、連続するセットの合計（999を法とする）を取ります：21 001 183 356
• 「999を超えた」セットの前にあるセットに1を追加します：22 001 183 356

実際、21979182173/999=22001183および残りは356です。

複雑さを計算しました。間違いがなければ、アルゴリズムはO（n）で機能するはずです。ここで、nは基数b表現のCの桁数です。また、C ++で非常に大雑把で最適化されていないバージョンのアルゴリズム（b = 10のみ）を実行し、GMPの一般的な整数除算アルゴリズムに対してテストしましたが、実際にはGMPよりもうまくいくようです。私が見たところ、このような実装されたものはどこにも見つからなかったので、一般的な部門に対してテストすることに頼らざるを得ませんでした。

非常によく似た問題について説明している記事をいくつか見つけましたが、特に2とは異なるベースで、実際の実装に焦点を当てているものはありません。これは、数値が内部に格納される方法によるものと思われますが、前述のアルゴリズムは、たとえば、それを考慮しても、b=10です。私も他の人に連絡しようとしましたが、やはり役に立ちませんでした。

したがって、私の質問は次のようになります。前述のアルゴリズムが説明されている記事や本などがあり、実装について説明している可能性がありますか。そうでない場合、たとえばC / C ++でそのようなアルゴリズムを実装してテストすることは理にかなっていますか、それともこのアルゴリズムは本質的に悪いのでしょうか？

また、私はプログラマーではありません。プログラミングはかなり大丈夫ですが、確かにコンピューターの「内部」についてはあまり知識がありません。したがって、私の無知を許してください-この投稿には1つ以上の非常に愚かなことがある可能性が高いです。もう一度ごめんなさい。

どうもありがとう！

コメント/回答で提起されたポイントのさらなる明確化：

みなさん、ありがとうございました。すばらしい回答やアドバイスをすべて同じものでコメントしたくなかったので、多くの方が触れた1つのポイントについてお話ししたいと思います。

私は、ベース2 ^ nでの作業が、一般的に言って、明らかに最も効率的な方法であることを十分に認識しています。ほとんどすべてのbigintライブラリは2^32などを使用します。しかし、もし（そして、私が強調するのは、この特定のアルゴリズムにのみ役立つでしょう！）、基数bの数字の配列としてbigintsを実装するとどうなるでしょうか？もちろん、ここではbが「合理的」である必要があります。最も自然なケースであるb = 10は、十分に合理的であるように思われます。数値が内部に保存される方法を考慮すると、メモリと時間の両方を考慮すると、多かれ少なかれ非効率的であることはわかっていますが、私の（基本的でおそらく何らかの欠陥のある）テストが正しければ、GMPの一般的な区分よりも速く結果を生成することができました。これは、そのようなアルゴリズムを実装することに意味があります。

Ninefingersは、その場合、高価なモジュロ演算を使用する必要があることに気づきました。古い+新しい+1の桁数を見るだけで、古い+新しいがたとえば999と交差したかどうかを確認できます。4桁の場合は、これで完了です。さらに、old<999およびnew<= 999であるため、old + new + 1が4桁の場合（これ以上持つことはできません）、（old + new）％999は（の左端の桁を削除することになります） old + new + 1）、これは安くできると思います。

もちろん、私はこのアルゴリズムの明らかな制限に異議を唱えていませんし、改善できないと主張していません-それは特定のクラスの数でしか分割できず、ベースbでの配当の表現を事前に知っている必要があります。ただし、たとえばb = 10の場合、後者は自然に見えます。

さて、上で概説したように、bignumを実装したとしましょう。ベースbでC=（a_1a_2 ... a_n）、D = b^k-1と言います。アルゴリズム（おそらくはるかに最適化されている可能性があります）は次のようになります。タイプミスが少ないといいのですが。

• k> nの場合、明らかに完了です
• Cの先頭にゼロ（つまりa_0 = 0）を追加します（たとえば、9999を99で除算しようとする場合に備えて）
• l = n％k （「通常の」整数のmod-高すぎないようにする必要があります）
• old =（a_0 ... a_l）（最初の数字のセット、おそらくk桁未満）
• for（i = l + 1; i <n; i = i + k）（floor（n / k）程度の反復があります）
  • new =（a_i ... a_（i + k-1））
  • new = new + old （これはbigintの追加であるため、O（k））
  • aux = new + 1 （繰り返しますが、bigintの追加-O（k）-私は満足していません）
  • auxがk桁を超える場合
    • 補助の最初の桁を削除します
    • old = old + 1 （もう一度bigint加算）
    • 古いものを最初にゼロで埋めて、必要な桁数になるようにします
    • （a_（ik）... a_（i-1））= old （i = l + 1の場合、（a _ 0 ... a _ l）= old）
    • new = aux
  • newを最初にゼロで埋めて、必要な桁数になるようにします
  • （a_i ... a_（i + k-1）= new
• quot =（a_0 ... a_（n-k + 1））
• rem = new

そこで、これについて私と話し合ってくれてありがとう-私が言ったように、これは、致命的な欠陥が見当たらない場合に、実装、テスト、および議論を試みる興味深い「特殊なケース」のアルゴリズムのようです。これまで広く議論されていないものであれば、さらに良いでしょう。ご意見をお聞かせください。長い投稿でごめんなさい。

また、もう少し個人的なコメント：

@Ninefingers：私は実際にGMPがどのように機能するか、それが何をするか、そして一般的なbigint除算アルゴリズムについてある程度の（非常に基本的な！）知識を持っているので、あなたの議論の多くを理解することができました。また、GMPが高度に最適化されており、さまざまなプラットフォームに合わせてカスタマイズされていることも承知しています。そのため、一般的に「打ち負かそう」とはしていません。これは、先のとがった棒で戦車を攻撃するのと同じくらい実り多いようです。ただし、これはこのアルゴリズムの考え方ではありません。非常に特殊な場合に機能します（GMPではカバーされていないようです）。無関係なことに、一般的な分割はO（n）で行われていますか？私が見た中で最も多いのはM（n）です。（そして、私が正しく理解していれば、実際には（Schönhage–Strassenなど）O（n）に到達しない可能性があります）。それでもO（n）に到達しないフューラーのアルゴリズムは、私が正しければ、ほぼ純粋です。理論的。）

@Avi Berger：考え方は似ていますが、これは実際には「九去法」とまったく同じではないようです。しかし、私が間違っていなければ、前述のアルゴリズムは常に機能するはずです。

仲間のSOが、優れた軽量の固定サイズ整数型（128ビットまたは256ビット、場合によってはテンプレートのパラメーター化）ライブラリーを推奨できるかどうか疑問に思いました。

私はGMPと共同を見てきましたが、彼らは大事にしていますが、私の目的には少し大きすぎます。現時点では、単純なヘッダーのみのソリューションに興味があります。パフォーマンスは重要であり、ターゲットアーキテクチャはx86およびx86-64であり、これも妥当なライセンスです（GPLまたはLGPLは何もありません）。

Rails 3.0.5 を使用しています。MySQL をデータベース ストレージとして使用しています。列の 1 つを BIGINT にする必要があるモデルがあります。移行ファイルの作成で次を使用しています。

これは正常に動作します。

ただし、実行すると

rake db:移行

生成された「schema.rb」ファイルは、特定の列に対して次の行を作成します。

これは正しくありません。

私の質問は、それのどこが間違っているのですか? 正しい「schema.rb」ファイルを取得するために私がすべきことはありますか? 「schema.rb」ファイルの生成方法を変更できますか?

「schema.rb」ファイルが間違っているという事実は、テストを実行し、「schema.rb」ファイルを使用して (テストを実行する前に) 最初からデータベースを作成する継続的インテグレーション サーバーに問題を引き起こすことに注意してください。

bigint型のフィールドを持つテーブルがあります。このフィールドにはタイムスタンプが格納されます。次のようにフィールドの日付をフォーマットしたい：

次のエラーが発生します：

巨大な（1億行）SQLServerテーブルの1列をFLOAT（8）からBIGINTに変換します。フローティングポイントや精度の低下は気にしません。

私はSQLServerを所有していませんが、ローカルでmysqlを使用しているので、この操作によって、データベースの場合と同じようにテーブル全体がコピーされるのではないかと思います。一方、これは暗黙の変換であり、したがって、時間ではなく秒の問題であると読みました。

SQL Serverをセットアップしてローカルで再現するのではなく、かなり時間がかかる可能性があります。答えが単純な「はい、テーブルコピーを実行します」か、「float8からbigintになります。問題ありません」かどうかを尋ねたいと思います。 "。

あなたの助けのためのThx！

私はこのようなクラスを持っています：

私のメインでは、ポインタを操作している間、コピーを避けることはできません：

ベクターデザインで何かが欠けている/管理されていないと思います。新しいlargeIntをインスタンス化せずに、ポインターのコピーレス割り当てを実現できますか？専門家に感謝します！

ええと... BIGFLOAT http://www.fractal- Landscapes.co.uk/bigint.html、

0.4 ^(1000 または 100000000) のようなものを計算する必要があるのは、非常に長い時間がかかる問題です。並列プログラミングや分散プログラミングについてはまだ勉強していませんが、高速でわかりやすい解決策が必要です。この企画をあと6時間で配信!! :D

コードは次のとおりです。

ここで、K は 1000 、N は 1001 です