そこで、二次整数と有理数のサブセットを処理するための連分数ライブラリを実装しています。連分数項は符号なし整数で表されます。連分数を扱うとき、次の一般的なパターンに気付きました。
- ほとんどの用語は 1 桁の小さな数字で、1 が最も一般的です。
- 一部の用語は非常に大きくなる可能性があり、私のアプリケーションで可能な最大値は 366 ビットですが、これらは非常にまれです。
- 大きな項は、特に優れた数の近似を表します。これは、通常、大きな分数に対して全体的に少ない項があることを意味します。
- 連分数の最悪の可能性は黄金比であり、366 ビットの精度での有理近似は、約 525 個の 1 の連続に相当します。
- 乱数の有理数は、通常、同じ数の大きな連続はありませんが、2 つから 4 つ連続して存在する場合があり、1 が最も一般的です。
そのため、用語の数と用語のサイズの両方に制限があり、用語の数はそれらのサイズにほぼ反比例します。したがって、これらの項を機械語またはバイト単位で格納することは通常、スペースを非常に浪費し、最悪の場合でも複数語の演算を処理する必要があります。項のサイズと項の数の間のほぼ逆の関係 (どちらも分数の分子と分母のサイズにも依存します) を考えると、無駄にならないように、適切な圧縮スキームを見つけようとしてきました。整数項を格納する非常に多くのスペース。
エンコードとデコードの速度が優れているため、 Huffman encodingを検討しましたが、コード値の確率をどのように計算するかわかりません。連分数と直接的な関係を持つ二分木であるため、スターン-ブロコ木がヒントになるかもしれないという漠然とした直感があります。
同じ数の実行が通常短い（ただし、まれに長くなる可能性がある）ときどき巨大なものを使用して、多数の小さな数を処理するための優れた圧縮アプローチを知っている人はいますか? 特に、かなり高速にエンコードおよびデコードできる必要があり (たとえば、O(n*lg(n)) は私が許容できる最悪の速度であり、O(n) またはそれ以上の速度が望ましい)、個々のタームの位置を調べて、どのターム番号 (第 4 ターム、第 5 タームなど) で操作しているかがわかるようにします。
また、サードパーティの実数または連分数ライブラリの使用には興味がありません。私はいくつかを見てきましたが、それらは私のニーズに対して不十分かやり過ぎであり、私自身の啓発のためにこれを自分でコーディングする経験が欲しいです.
アップデート
また、0 と 1 の間で一様に分布する乱数の特定の連分数項の確率分布を与えるガウス クズミン分布についても学びました。k
P(k) = -lg(1.0 - 1.0/((k + 1.0)**2)Python 疑似コードでは、lg は 2 を底とする対数です。これはk無限に近づく限界であるため、私のケースはやや制限されています2**366(まだ巨大ですが)。Linas Vepstas による「連分数のエントロピー」は、ガウス クズミン分布の (情報) エントロピーを約 3.43 ビットとして提供します。私の分母の最大値は十分に大きいので、連分数の情報エントロピーはおそらくその限界に近くなりますが、リンクされた記事のグラフは限界に非常にゆっくりと近づいていることを示しており、分母が比較的小さい場合は異なります。