2025-11-17T19:07:12.711716

Fast Trigonometric Functions using the RLIBM Approach

Park, Nagarakatte
This paper describes our experience developing polynomial approximations for trigonometric functions that produce correctly rounded results for multiple representations and rounding modes using the RLIBM approach. A key challenge with trigonometric functions concerns range reduction with "pi", which reduces a given input in the domain of a 32-bit float to a small domain. Any rounding error in the value of "pi" is amplified during range reduction, which can result in wrong results. We describe our experience implementing fast range reduction techniques that maintain a large number of bits of "pi" both with floating-point and integer computations. The resulting implementations for trigonometric functions are fast and produce correctly rounded results for all inputs for multiple representations up to 32-bits with a single implementation.
academic

RLIBM手法を用いた高速三角関数

基本情報

  • 論文ID: 2510.13426
  • タイトル: Fast Trigonometric Functions using the RLIBM Approach
  • 著者: Sehyeok Park, Santosh Nagarakatte (ラトガース大学)
  • 分類: cs.PL (プログラミング言語)
  • 発表会議: International Workshop on Verification of Scientific Software (VSS 2025)
  • 論文リンク: https://arxiv.org/abs/2510.13426

概要

本論文は、RLIBM手法を用いた三角関数の多項式近似開発の経験について述べています。この手法は、複数の表現形式と丸め方式に対して正しく丸められた結果を生成することができます。三角関数の主要な課題は、πの範囲縮減に関わるもので、32ビット浮動小数点数領域の入力を小さな領域に縮減します。π値における任意の丸め誤差は、範囲縮減プロセス中に増幅され、誤った結果をもたらす可能性があります。著者は、浮動小数点演算と整数演算の両方で多数のπのビット数を維持する高速範囲縮減技術の実装経験について述べています。最終的な三角関数実装は高速であり、すべての入力に対して正しく丸められた結果を生成し、最大32ビットの複数の表現形式をサポートし、単一の実装のみが必要です。

研究背景と動機

核心的な問題

  1. 正確な丸めの課題: 科学計算は数学ライブラリが提供する基本関数を広く使用していますが、すべての入力に対して正確に丸められた結果を生成することは極めて困難です（いわゆる「表作成者のジレンマ」）。主流の数学ライブラリはすべての入力に対して正確な結果を生成することができません。
  2. 移植性と再現性の問題: 正確に丸められた数学ライブラリの欠如により、アプリケーションが異なるマシン上で全く異なる結果を生成し、移植性と再現性に影響を与えます。
  3. 複数の表現形式の必要性: カスタム形式（bfloat16、tensorfloat32、FP8など）の増加に伴い、複数の表現形式と丸め方式に対して正確な結果を提供できる参照ライブラリが必要です。

既存手法の限界

  • ミニマックス多項式近似: 従来の手法は、すべての入力の最大誤差を最小化する多項式近似を生成しますが、実数値の出力が丸め境界に非常に近い場合、自由度が大幅に減少します。
  • 性能と正確性のトレードオフ: 既存のライブラリは性能（Payne-Hanek実装など）または正確性（GCCのlibmなど）のいずれかで妥協しています。

核心的な貢献

  1. 効率的な範囲縮減技術: 浮動小数点演算と整数演算を組み合わせた効率的な範囲縮減アルゴリズムを開発し、正確な結果を生成するのに十分なπのビット数を維持できます。
  2. 複数表現形式の単一実装: 10ビットから32ビットの複数の表現形式とすべての標準丸め方式に対して、正確に丸められた結果を生成できる単一の多項式近似を実装しました。
  3. 性能最適化: 整数ベースの範囲縮減は、浮点戦略と比較して19%のパフォーマンス向上を実現し、全体的には主流ライブラリより高速またはパフォーマンスが同等です。
  4. 完全な三角関数ライブラリ: sin、cos、tan関数に対して高速で正確な実装を提供します。

方法の詳細

RLIBM手法の核心的な考え方

RLIBM手法の重要な洞察は、関数の実数値ではなく、正確に丸められた結果を直接近似することです。与えられた入力の正確に丸められた結果に対して、その区間内の任意の値が正確な結果に丸められる実数区間が存在します。これはミニマックス手法よりも大きな自由度（すべての入力に対して1 ULP）を提供します。

複数表現形式のサポート機構

複数の表現形式をサポートするために、RLIBMプロジェクトは(n+2)ビット表現の多項式近似を生成し、round-to-odd丸め方式を使用することを提案しています。このアプローチの利点は以下の通りです：

  • round-to-odd結果は、目標表現に直接丸めるために必要なすべての情報を保持します
  • その後、より低いビット幅表現に丸めることで、正確な結果を生成できます
  • 二重丸め誤差を回避します

範囲縮減アルゴリズム

基本原理

三角関数の範囲縮減は、入力x∈-∞,∞を縮減入力x'∈-π/2^(t+1), π/2^(t+1)にマッピングします。ここで：

x = x' + kπ/2^t
k = [2^t * x/π]
x' = π/2^t * r、ここでr = 2^t*x/π - k

浮動小数点実装戦略

小入力処理 (|x| < 2^30):

  • 80ビットの256/πを使用し、2つのdouble値に分割して保存
  • 中間丸め誤差を回避
  • 部分乗積を利用してkと分数部分rを正確に計算

大入力処理 (2^30 ≤ |x|):

  • バージョン1: 256/πを28ビットセグメントに分割してdouble配列に保存し、各セグメントは切り捨てモードを使用して生成
  • バージョン2: 53ビット精度セグメントを使用し、融合乗算加算命令を利用して丸め誤差を削減

整数実装戦略

小入力最適化:

  • 80ビットの256/πを使用し、2つの40ビット整数P1とP0に分割
  • ビットシフト操作を通じて整数kと分数ビットを識別
  • 浮動小数点演算の精度損失を回避

大入力処理:

  • 192ビットの256/πを使用し、3つの64ビット整数に分割
  • 128ビット部分乗積を計算
  • ビットシフト操作を通じて関連ビットを抽出

出力補正

三角恒等式を利用した出力補正：

sin(x) = sin(k'π/2^t)cos(x') + cos(k'π/2^t)sin(x')
cos(x) = cos(k'π/2^t)cos(x') - sin(k'π/2^t)sin(x')

事前計算表と周期性/対称性の最適化を通じて、必要な事前計算値を512個に削減します。

実験設定

テスト環境

  • ハードウェア: 2.10GHz Intel Xeon(R) Silver 4310サーバー、256GB RAM
  • オペレーティングシステム: Ubuntu 24.04.1 LTS
  • 測定ツール: パフォーマンスカウンター

比較ライブラリ

  • GLIBC: floatおよびdouble libm
  • Core-Math: 正確に丸められたライブラリ
  • RLIBM実装: 複数の範囲縮減戦略の変種

評価指標

  • 正確性: 完全列挙によるすべての入力の正確性検証
  • 性能: 他のライブラリに対する相対的な加速比

実験結果

正確性検証

  • RLIBM関数: 10ビットから32ビットのすべての表現形式のすべての入力に対して、正確に丸められた結果を生成
  • GLIBC float libm: 32ビットfloat入力のsin、cos、tanに対して数千の誤った結果
  • GLIBC double libm: float版よりも正確ですが、依然として誤りがあります
  • Core-Math: 32ビットに対してのみ正確な結果を生成し、10～32ビット範囲では二重丸め誤差により失敗

パフォーマンス結果

範囲縮減最適化の効果

混合方法（小入力は浮動小数点、大入力は整数）と他の戦略の比較：

  • 初期浮動小数点方法(FP V1)より19%高速
  • 代替浮動小数点方法(FP V2)より大幅に改善
  • 純整数方法より4%高速

他のライブラリとの比較

  • Core-Mathより平均10%高速
  • GLIBC double関数より平均137%高速
  • パフォーマンス向上は主に効率的な範囲縮減と整数演算の精度上の利点に起因

技術的革新点

1. 精度とパフォーマンスのバランス

  • 整数演算は64ビットdoubleより高い精度を提供（uint64_tおよびuint128_t）
  • 入力を縮減するのに十分な精度を得るために必要な部分乗積の数を削減

2. 混合範囲縮減戦略

  • 小入力は浮動小数点演算を使用（256*x/πの整数部分が十分に小さい場合）
  • 大入力は整数演算を使用（より高い精度とより単純なビット操作を提供）

3. ビット操作最適化

  • ビットシフト操作を使用して256*x/π内の縮減入力とkの低位に関連する部分を識別
  • 浮動小数点演算における丸め累積を回避

関連研究

従来の手法

  • ミニマックス近似: Remezアルゴリズムなど、ただし丸め境界付近での自由度は限定的
  • Payne-Hanekアルゴリズム: 古典的な範囲縮減方法ですが、実装効率が課題

正確な丸め研究

  • CR-LIBM: 初期の正確に丸められたライブラリですが、パフォーマンスが遅い
  • Core-Math: 現代的な正確に丸められた実装ですが、単一の表現形式のみをサポート

RLIBMプロジェクトの発展

  • 基本関数（e^x、logなど）から三角関数への拡張
  • 複数表現形式サポートの革新的なアプローチ

結論と考察

主要な結論

  1. 実現可能性の証明: 三角関数に対して高速で正確な実装を生成することが可能であることを証明
  2. 範囲縮減の重要性: 効率的な範囲縮減は低次多項式近似と同等に重要
  3. 整数演算の利点: 整数ベースの実装は大入力時に浮動小数点方法より大幅に優れている

限界

  1. 複雑性: 実装の複雑性が高く、正確なビット操作と複数の戦略が必要
  2. メモリオーバーヘッド: 事前計算表と多精度定数の保存が必要
  3. スケーラビリティ: より高い精度表現への拡張には再設計が必要

今後の方向性

  1. GPUプラットフォーム: GPUプラットフォーム向けの正確に丸められたライブラリの探索
  2. 標準化: IEEE-754標準委員会への参加を通じた正確な丸めの強制推進
  3. 主流統合: 主流の数学ライブラリ開発者との協力によるこれらの方法の統合

深い評価

利点

  1. 理論と実践の結合: RLIBM理論を課題のある三角関数に成功裏に適用
  2. 包括的なエンジニアリング最適化: アルゴリズムから実装までの全方位的な最適化
  3. 厳密な検証: 完全列挙による正確性検証
  4. 実用的価値: 実際のアプリケーションにおける重要な問題を解決

不足点

  1. 実装の複雑性: 複数の戦略の組み合わせが実装と保守の複雑性を増加
  2. 可読性: 大量のビット操作コードの可読性と保守性に改善の余地
  3. 理論的分析: 整数方法がより優れている理由についての深い理論的分析が不足

影響力

  1. 学術的貢献: 数値計算分野に新しい正確に丸められた実装方法を提供
  2. 実用的価値: 高精度数値計算が必要な科学計算に直接適用可能
  3. 標準推進: 将来の浮動小数点標準の発展に影響を与える可能性

適用シーン

  1. 科学計算: 高精度と再現性が必要な数値シミュレーション
  2. 金融計算: 正確な結果が要求される金融モデリング
  3. 組み込みシステム: 複数の浮動小数点形式をサポートする必要があるシステム
  4. 参照実装: 他のライブラリの正確性基準として

参考文献

本論文は、数値解析、浮動小数点演算、正確な丸めの分野における重要な文献を引用しており、以下を含みます：

  • Mullerの基本関数参考書
  • MPFR高精度ライブラリ
  • Payne-Hanek範囲縮減アルゴリズム
  • IEEE-754浮動小数点標準関連研究

本論文は数値計算分野に重要な貢献をしており、理論的手法を実用的で高性能な実装に成功裏に変換し、科学計算における正確な丸めの問題に対して効果的な解決策を提供しています。