3

興味深い数学の問題に出くわしました。これには、 281桁を超える数字を使って数学を行う必要があります。各桁に1つのメモリユニットがあるシステムでは、これほど大きな数を表すことは不可能であることを私は知っていますが、これを回避する方法があるかどうか疑問に思いました。

私の最初の考えは、基数10（10進数）の代わりに非常に大きな基数を使用することでした。いくつか考えた後、最適な基数は桁数の平方根になると私は信じています（したがって、2 81桁の数の場合は、基数2 40 ishを使用します）。これは改善ですが、スケーリングがうまくいかず、それでも実際には実用的ではありません。

では、どのようなオプションがありますか？私は多くの任意精度ライブラリを知っていますが、この種の算術をサポートするためのスケールはありますか？

ありがとうo7

編集：もう少し考えた後、私は「最適なベースは桁数の平方根になる」について完全に間違っているかもしれないことに気付きましたが、a）それが理由です。

編集2：基数10の1000,000=基数16のF4240=基数8の364110基数16では、基数8に数値を格納するために20ビットが必要なので、基数を増やすと合計が10進数になるように見えます必要なビット数。（これも間違っている可能性があります）

4

3 に答える 3

3

This is really a compression problem pretending to be an arithmetic problem. What you can do with such a large number depends entirely on its Kolmogorov complexity. If you're required to do computations on such a large number, it's obviously not going be arrive as 2^81 decimal digits; the Kolmogorov complexity would too high in that case and you can't even finish reading the input before the sun goes out. The best way to deal with such a number is via delayed evaluation and symbolic rational types that a language like Scheme provides. This way a program may be able to answer some questions about the result of computations on the number without actually having to write out all those digits to memory.

于 2012-02-08T05:18:57.837 に答える
1

科学表記法を使用するだけでよいと思います。精度は失われますが、2^81 桁を格納するには 10^24 ビット (約 1000 億テラバイト) を超える必要があるため、精度を失うことなく大きな数値を格納することはできません。

于 2012-02-08T04:42:17.567 に答える
1

2^81 桁を超えるもの

2^81 ビットの非分数は、3*10^11テラバイトのデータを使用します。数ごと。

これは、すべての数字が必要であり、データが圧縮できないと仮定しています。

ゼロ以外の要素にのみメモリを割り当てるある種のスパース配列に格納するデータを圧縮しようとすることはできますが、それはデータがどこにでも収まることを保証しません。

このような精度は役に立たず、最新のハードウェアでは処理できません。2 ^ 81ビットは、単純に数値を調べるのに非常に長い時間がかかります（1バイトが1ミリ秒かかると仮定すると、9584兆年）。乗算/除算は気にしません。また、そのような精度を必要とする問題も考えられません。

唯一の選択肢は、精度を最初の N 桁まで減らし、浮動小数点数を使用することです。データは double に収まらないため、非常に大きな浮動小数点数を提供する浮動小数点をサポートする bignum ライブラリを使用する必要があります。2^81 (指数) はビットで表現できるため、非常に大きな浮動小数点数を使用して数値の先頭を格納できます。

十進法で 1000,000

ベースに関係なく、正の数を格納するには少なくとも floor(log2(number))+1 ビットかかります。base が 2 でない場合は、格納するのに floor(log2(number))+1 ビット以上かかります。数値基数は、必要なビット数を減らしません。

于 2012-02-08T05:24:12.333 に答える