問題タブ [bignum]

任意のサイズの符号なし整数 (バイナリ形式で格納されている) を 10 進数に変換するアルゴリズムが必要です。つまり、人間が読めるようにするためです ;)
現在、10 の除算によるモジュラスと剰余を継続的に計算する、おそらく (または明らかに) やや素朴な方法を使用しています。
残念ながら、速度はやや... ラメです。

たとえば、2000^4000 を (bignum ライブラリを使用して) 計算すると、約 1.5 秒かかります (炎上しないでください xD)。ただし、必要な基本変換を含む印刷には約 15 分かかり、かなり面倒です。

私は bc をテストしましたが、これは両方を 1 秒未満で実行します。
それはどのように行うのですか？（fftsを使用した乗算や、基数変換のみではありません）

大きくて「一意の」整数（実際にはSHA1ハッシュ）があります。

注：ここでSHA1ハッシュについて話している間、これは暗号化/セキュリティの質問ではありません！私はSHA1を壊そうとはしていません。それが役立つ場合は、SHA1の代わりにランダムな160ビット整数を想像してみてください。

私は（楽しむ以外の理由はありませんが）そのSHA1ハッシュをコンピューターで生成された（疑似）英語のフレーズにマップするアルゴリズムを見つけたいと思っています。マッピングは双方向である必要があります（つまり、アルゴリズムを知っていると、そのフレーズから元のSHA1ハッシュを計算できる必要があります）。

フレーズは意味をなす必要はありません。私はナンセンスの段落全体でさえ解決するでしょう。（ただし、段落の品質（英語性）は、単なるフレーズよりも優れているはずです。）

より良いアルゴリズムは、より短く、より自然に見える、よりユニークなフレーズを生成します。

バリエーション：ハッシュの一部しか扱えなくても大丈夫です。たとえば、最初の6桁の16進数で問題ありません。

生成されたフレーズの可能な使用法：GitコミットIDの人間が読めるバージョン。そのコミットから構築された、特定のプログラムバージョンのモットーとして使用します。（私が言ったように、これは「楽しみのため」です。これが非常に実用的であるとは言いません。または、SHA1自体よりもはるかに読みやすくなっています。）

考えられるアプローチ：過去に、SHAから読み取ったビットに従って、（単語の）確率テーブルを作成し、マルコフ連鎖としてフレーズを生成し、ジェネレーターをシード（確率ツリーからブランチを選択）しようとしました。これはあまり成功しませんでした、結果として生じるフレーズは長すぎて醜いものでした。これがバグなのか、アルゴリズムの一般的な欠陥なのかはわかりません。十分に早く放棄しなければならなかったからです。

今、もう一度問題を解決しようと考えています。これにアプローチする方法について何かアドバイスはありますか？マルコフ連鎖アプローチがここで機能すると思いますか？他に何かありますか？

最近、インストールしたrspecのバージョンを-v 2.5.0から1.3.0に変更して、rails2.xで動作するようにしようとしていました。cucumber、rspec-rails、およびrspecをアンインストールした後、再インストールして、「エラー：gemの実行中に...（RangeError）bignumが大きすぎて「long」に変換できません。他のgemsrspec-railsをインストールしてみました。同じエラーが発生する前にインストールされたrspec-v2.5.0をインストールしようとしても、他のgemを正常にインストールできます。エラーが発生するのは、 rspecに関連付けられているgem（rspec、rspec-rails、cucumber）をインストールしてみてください。これは、railsアプリケーションでいくつかのキュウリテストを実行する必要があるため、非常に苦痛です。

10 進数で表された UUID (128 ビット数) を取得しました。これを C で数値形式に解析する必要があります。ターゲットのデータ構造は char[16] であり、bignum ライブラリを使用することはできません。誰かが適切なアルゴリズムを教えてくれますか?

私は長整数を持っていますが、10進数ではなく、剰余のセットとして格納されています。

だから、私はN数を持っていませんが、そのような残りのセットを持っています：

Nはこれらの素数の乗算よりも小さいので、中国の剰余定理はここで機能します（http://en.wikipedia.org/wiki/Chinese_remainder_theorem）。

Nこの6つの余りがある場合、10進数で復元するにはどうすればよいですか？これを行うためのプログラム（C / C + GMP / C ++ / perl / java / bc）は素晴らしいでしょう。

たとえば、最小のNがこの剰余のセットを持つことができるものは次のとおりです。

正確性と効率性をテストする必要がある任意精度の有理数パッケージを作成しています。もちろん、アドホックなテスト セットを自分で作成することもできますが、これを行うのは初めてではないので、質問する価値はあると思います。使用できる既存のテスト セットを推奨できる人はいますか?

編集：ループのたびに3つの乱数を生成し、さまざまな算術アイデンティティが保持されることを検証するテストルーチンを作成しました。これまでのところ、数値コードにいくつかのバグが見つかりました。実際のコードは次のとおりです。

％f変換を使用する私のPerlのprintf（darwin-thread-multi-2level用に構築されたActiveState v5.10.1）は、bignumを使用している場合でも、1e-6桁を超える私の値を尊重しません。

精度を損なうことなく入力を印刷するにはどうすればよいですか？

私の本当の問題は、この番号を操作する必要があることです（たとえば、$ x / 0.000_000_001、さらに悪いことに、substr（）関数呼び出しでは偽造できない$ x / 0.000_001_024）。私が「楽しい」部分に到達する前に、現在の削減は私を困惑させました。

私は GNU Bignum でプログラムを書いています。私がやりたいことは、単純にバイナリ ファイルを読み取り、生データを Bignum 整数として使用することです。 67 や 300 などの非常に小さな数値が表示されます。別のファイルで試してみましたが、すべて同じように動作します。以下のソースコードは、私が話していることのアイデアを皆さんに与えるかもしれません.

ここで何が間違っている可能性がありますか?

Perlbignum bigintとbigratプラグマにはin_effect、ヒント ハッシュをプローブすることによって、プラグマがスコープにロードされているかどうかを検出する関数が含まれています。ただし、これはバージョン 5.9.4 以降の perl でのみ機能します。これは、レキシカル ヒント ハッシュが導入されたときからです。

これらのプラグマが以前のバージョンの perl で有効かどうかを判断する良い方法はありますか? 私の用途では、バージョン 5.8.8 までサポートしたいと思います。

更新: 以下の暴徒の解決策は、有効である可能性のある字句スペースにアクセスできる場合に機能bignumします。ただし、私のユースケースでは、そのスペースから呼び出される関数を作成しており、その関数内で呼び出し元のスコープがbignum読み込まれたかどうかを判断する必要があります。(つまり、私のコードではbignum::in_effect(2)、呼び出しスタックの数フレームを検索するようなものを呼び出しています)

私は、大きな数を操作するための独自の bignum クラスを作成しています。これまでのところ、operator=andをオーバーロードしてきましたoperator+。長い除算を実行するにはどうすればよいですか?

また、現在、整数の範囲内の値のみを bignum オブジェクトに割り当てることができます。int の範囲外の値を割り当てるにはどうすればよいですか? 文字列なしでこれを行うことは可能ですか?