HN 日本語サマリー

← 一覧へ戻る
プログラミング

Beeg floatライブラリ、Fabrice Bellard氏のlibbfのRustポート

Beeg float library, a Rust port of Fabrice Bellard's libbf (github.com)

14 pointsby serialx3 コメント

要約

libbeefは、Fabrice Bellard氏が開発した高精度浮動小数点ライブラリlibbfをRustで再実装したものです。IEEE 754のセマンティクスを完全にサポートし、超越関数や10進数浮動小数点も扱えます。Rustのみで依存関係がなく、no_std環境にも対応しており、バイナリサイズも小さいのが特徴です。

全文翻訳

🥩 libbeef

[画像: docs.rs]

Fabrice Bellard氏のlibbf — 極小の任意精度浮動小数点ライブラリ — のRustによる移植版です。名前は「Beeg Float」を意味します。

  • IEEE 754の完全なセマンティクス:符号付きゼロ、NaN、無限大、設定可能な指数幅、サブノーマル数、5つの丸めモードすべて、5つのステータスフラグすべて。
  • 超越関数:exp, log, pow, sin, cos, tan, atan, atan2, asin, acos。
  • 独立した基数10演算を備えた10進浮動小数点(BigDecimal)。
  • no_std互換(allocが必要)。
  • 依存関係ゼロの純粋なRust。

簡単な例

use libbeef::format::formats;
use libbeef::Float;

type Quad = Float<formats::Binary128>;

fn main() {
    let a: Quad = "3.14159265358979323846".parse().unwrap();
    let b: Quad = "2.71828182845904523536".parse().unwrap();
    let result = (a * b).sin();
    println!("{result}");
    // 0.773942685266708278263054855332479932...
}

Float<F>は値をコンパイル時フォーマットとペアにするため、*や.sin()は128ビット精度と最近接偶数への丸めを自動的に使用します — 各呼び出しサイトでフォーマット引数を指定する必要はありません。

パフォーマンス

libbeefはC言語版libbfと同じアルゴリズムを実装しています:NTTベースの乗算、除算/平方根のためのニュートン反復、超越関数のためのAGM/バイナリスプリッティング。各演算クラスで最適な漸近計算量です:

演算クラス計算量アルゴリズム
加算、減算、比較O(n)線形スキャン
乗算O(n log n)数論変換(NTT)
除算、平方根O(M(n))NTT乗算上のニュートン反復
exp, log, sin, …O(M(n) · log n)AGM / バイナリスプリッティング

経験的にも(全データはdocs/benchmark-report.mdにあり)、libbeefはRustの境界チェックとアロケーションモデルによる定数倍のオーバーヘッドを伴いつつ、C言語版libbfのスループットを追跡しています:

演算256ビット30,000ビット300,000ビットlibbf比rug (GMP/MPFR)比
乗算6.784100 ns/limb1.3–2.0倍0.9–1.3倍
除算17.3515659 ns/limb1.1–1.4倍2.6–3.5倍
平方根38.3384597 ns/limb1.2–1.3倍3.2–4.3倍
sin1051—— ns/limb0.7倍(高速)3.6倍

乗算の行が最も情報量が多いです:二次アルゴリズムであれば、オペランドサイズが10倍になるごとに約10倍の増加(47 → 469 → 4688リム)を示すはずですが、libbeefは4.2倍、次に1.2倍と増加しており、これはC言語版と同じ形状のO(n log n) NTTエンベロープです。300kビットでは、libbeefはlibbfの約2倍、GMPの約1.3倍であり、同時にnum-bigintの学校法/Toom乗算よりも4倍高速です。

超越関数については、libbeefはsin/cos/tan/powでC言語版libbfに匹敵するかそれを上回り、log/atanでは15%以内の差です。MPFRとの一様な3〜5倍の差はアルゴリズムによるものです(MPFRはこれらの関数に異なる、より優れたアルゴリズムを使用しており、C言語版libbfでも同様の差が見られます)。

除算と平方根は、GMP/MPFRに対してより大きな定数倍の差(約3倍)を示します。これは、GMPの調整された分割統治法に対するlibbfのニュートン逆数アプローチの固有の特性であり、C言語版でも同じ比率が現れます。

なぜlibbeefなのか?

1. 純粋なRust、システム依存なし。 rug/GMPはCコンパイラ、システムGMP/MPFRライブラリ、およびホストをプローブするビルドスクリプトを必要とします。libbeefは、ビルドスクリプトなし、-lmなし、pkg-configなしで、単一のcargo addで済みます。これは、設定ゼロで、WASM、組み込み、クロスコンパイルを含む、rustcがサポートするあらゆるターゲットでビルドできます。

2. 小さなバイナリフットプリント。 GMP/MPFRを静的にリンクした場合、2つの数値を乗算してsinを計算するだけの簡単なプログラムは以下のようになります:

ライブラリバイナリサイズ(stripped)
libbeef482 KiB
num-bigint(整数のみ、トリグなし)448 KiB
malachite(整数のみ、トリグなし)658 KiB
rug(GMP + MPFR 静的リンク)680 KiB

libbeefは、malachiteやrugが整数のみで必要とする容量よりも少ないスペースで、完全な浮動小数点演算と超越関数を提供します。num-bigintのバイナリが小さいのは、sinを全く計算できないためであり、浮動小数点レイヤーを持たないからです。

3. 正確かつ完全。 libbeefは、すべての演算、精度、丸めモードでlibbf自身の検証スイートに合格します。これは「十分な」近似ライブラリではなく、設定可能な指数幅とサブノーマル数を持つIEEE 754に準拠した正確に丸められた演算を実装しています。

4. no_std対応。 allocのみが必要です。ファイルI/O、スレッド、アロケーション以外のシステムコールはありません。

5. より寛容なライセンス。 libbeefはMITライセンスですが、GMP/MPFRはLGPLです。これにより、LGPLに対する追加の法的レビューが望ましくないライセンスに敏感なプロジェクトにとって、libbeefはより良い選択肢となります。

他のライブラリを使うべき場合
  • 大規模精度(>10kビット)での最大スループット: GMP/MPFR(rug経由)は、高度に調整されたFFTとToom-Cookスタックを備えており、乗算で約2〜3倍、除算で約3倍優れた定数を持っています。百万ビット精度の生のns/opがボトルネックである場合は、rugを使用してください。
  • 整数のみのワークロード: 浮動小数点、丸め、超越関数が不要な場合は、num-bigintまたはmalachiteが整数のみに焦点を当てたよりシンプルなAPIを提供します。
  • 大規模な10進数演算: libbeefの10進数パスは機能しますが、まだパフォーマンスチューニングされていません(ネイティブの基数10⁹カーネルではなく、バイナリ変換を経由します)。

ビルドとテスト

cargo build                    # ビルド(デフォルト機能:std)
cargo test                     # 全テスト実行
cargo test --test bftest       # libbf検証スイート(高速、単一シード)
cargo doc --open               # APIドキュメント生成と表示

機能

機能説明
std (デフォルト)stdサポートを有効にする
num-traitsnumエコシステム向けのトレイト実装
num-integer追加のnum整数トレイト
serdeシリアライゼーションサポート

ライセンス

MIT(libbfと同じ)。