はじめに
こんにちは、Techouse の人材プラットフォーム事業部でサーバーサイドエンジニアを担当している imayayoh と申します。
2026年4月22日から24日まで、北海道函館で開催された RubyKaigi 2026 に参加してきました。本日はそのなかで一番印象的だったセッション、tomoya ishida (tompng) さんの Digits, Digits, and Digits について紹介します。
発表スライドは Google Drive で公開されています。本記事中の図や引用も基本的にこちらから引用しています。
tompng さんとの「再会」
実は tompng さんの発表を聞くのは今回が初めてではなく、RubyKaigi 2024 の Day1 キーノート Writing Weird Code も現地で聴講していました。Ruby の文法を駆使した一見奇妙だが正しく動作するコード群が、実行するとスクリーン上で次々とアニメーションへ変化していく、インパクトの強い発表でした。
そんな tompng さんの今年の発表ということで、期待を膨らませて会場へ向かいました。
一行で言うと
BigMath.expを高速化する物語。段階ごとに違う「分け方」を試して、最後に辿り着いたのは40年前から知られていた Bit-burst アルゴリズムだった。
題材としてはシンプルですが、実際の改善幅は以下の通りです。
| 精度 | Before | After |
|---|---|---|
| 10,000 桁 | 2.2秒 | 0.005秒 |
| 100,000 桁 | 45分 | 0.08秒 |
| 1,000,000 桁 | 1,000時間 | 1.06秒 |
| 10,000,000 桁 | 60年 | 13.6秒 |
| 100,000,000 桁 | 60,000年 | 150秒 |
最終行は見間違いではなく、60,000年かかっていた計算が150秒で完了するようになった、という話です。
1,000,000桁の精度は何に必要か
気になったのはまず、そもそもなぜここまで高い精度が必要なのか、という点でした。tompng さんもスライドで先回りしてこう書いています。
円周率 π は 40桁もあれば宇宙スケールの工学計算に十分。では1,000,000桁は何に使う？
tompng さんの回答は "Dreamer's Dream" でした。宇宙旅行の夢、Ruby という魔法を使う夢、cosmic scale の桁で cos(x) を計算する夢、というように複数挙げられていました。実用というより「できるかどうか」自体に挑戦する、というスタンスです。
この動機からスタートして実装まで突き進んでいるところに、tompng さんらしさを感じました。
BigDecimal の内部構造
本題の前に、BigDecimal の内部構造をざっと押さえておきます。普段の Ruby 開発では Float と同様に意識せず扱う BigDecimal ですが、中身は意外と素朴です。
-1.2345678987654321 × 10^3456 sign: - ← 符号 frac: [1, 234567898, 765432100, ...] ← 整数部 + 小数部を9桁ずつ詰めた配列 exponent: +3456 ← 10の何乗か
「符号・仮数・指数」で数を表すというフォーマット自体は Float と同じで、仮数の桁列だけが可変長配列になっています。これが「任意精度（arbitrary precision）」の正体です。9桁ずつパックしているのは、10⁹ が uint32 の整数演算でそのまま扱えるサイズだから、という理解で問題ありません。
四則演算のなかで支配的なのは乗算です。素朴な実装では桁数 N の二乗、つまり O(N²) のコストになります。桁が増えるほど「乗算をいかに速くするか・回数をどう減らすか」が重要になります。ここが今回の発表の主題です。
sin / cos / exp / log / gamma といった BigDecimal の関数は実は Ruby で書かれています（lib/bigdecimal/math.rb）。tompng さん曰く「乗算と除算を減らす工夫を実装しやすくて、楽しい」とのことで、今回の話はこの Ruby 層の工夫が主役になります。
設計原則として、以下が示されました。
Focus on
expandsin. Every other function gets fast.
cos, tan, sinh, atan などは exp と sin で表現できるため、この2つを速くすれば連鎖的に他も速くなる、という考え方です。今回は exp に絞って解説していきます。
高速化の三層構造
60,000年 → 150秒 という改善は、3つの独立した工夫が重なって初めて成立する、というのがこの発表の核心です。順に見ていきます。
第1層: NTT による乗算の高速化
土台となるのが乗算の高速化です。素朴な筆算による乗算は O(N²) のため、桁数が増えるほど計算負荷が大きくなります。
そこで使われているのが NTT (Number Theoretic Transform) です。信号処理で使われる FFT の整数演算版で、これを通すことで乗算のコストが O(N log N) のオーダーまで落ちます。
第2層: Binary Splitting による乗算の「組み方」の最適化
発表中盤、"Arithmetic Break" というコーナーで以下の問題が出されました。1 × 2 × 3 × ... × 100,000（10万の階乗）を計算する、というものです。これを2つの方法で比較します。
方法A: 順番に積み上げる
まず 1×2 を計算し、答えに 3 を掛け、4 を掛け…と1つずつ累積していく方法です。直感的にはこちらの方法を思いつくはずです。
計算が進むほど「累積した結果（左側）」が肥大化していく一方、掛ける相手（右側）はずっと小さい数のままです。
1 × 2 → 2 2 × 3 → 6 6 × 4 → 24 24 × 5 → 120 120 × 6 → 720 ... (5万回ぐらい繰り返すと...) [巨大な累積結果] × 99,999 ← フルコストの掛け算 [巨大な累積結果] × 100,000 ← フルコストの掛け算
結果として「巨大数 × 小さな数」というアンバランスな掛け算を、5万回ほど繰り返すことになります。
方法B: 木構造で計算する
別の方法として、まず隣同士でペアを作って掛け、その積どうしでまたペアを作って掛け、を繰り返す木構造の計算があります。8個で試した場合は以下のような形になります。
1 2 3 4 5 6 7 8
\ / \ / \ / \ /
2 12 30 56 ← 1段目: 隣同士を掛ける
\ / \ /
24 1680 ← 2段目: その積どうしを掛ける
\ /
40,320 ← 3段目: 最後の1回
100,000個の場合も同様で、10万個 → 5万個 → 2.5万個 → ... と半分ずつ減っていき、約17段階で1個に集約されます。各段階で「だいたい同じ大きさの数どうし」を掛け合わせる形になり、最後の1段でのみ「巨大数 × 巨大数」を1回だけ掛けます。
結果
| 方法 | 時間 |
|---|---|
| 方法A（順番に積み上げる） | 4.85秒 |
| 方法B（木構造で計算する） | 0.045秒（100倍速い） |
計算結果は同じ（456,574桁の巨大数）で、乗算の回数も同じ N − 1 回です。それでも、組み方を変えるだけで100倍の差が出ます。
スライドで強調されていた原則は以下です。
Multiplying operands of similar size — Exploit the full potential of multiplication
NTT は「同サイズ × 同サイズ」の乗算で最も効率が良くなるアルゴリズムです。方法A はその強みを活かせず、方法B は最大限活かせる構造になっているため、100倍の差が出ます。
Binary Splitting は、この考え方を Taylor 級数（e^x = 1 + x + x²/2! + x³/3! + ... の式）の計算に応用したものです。素朴に計算すると分子と分母を毎項計算して足していくため、方法A と同じ「アンバランスな掛け算の連発」になります。Binary Splitting では、項を半分ずつのペアで束ねつつ有理数のまま計算し、除算は最後の1回だけ行う形に組み直します。
これにより、各掛け算が「同サイズ × 同サイズ」に揃うことで NTT が効きやすくなり、重い高精度除算も N 回から 1 回まで減る、という二重の効果が得られます。実際の改善幅としては、exp(1, 100_000) が 2.5秒 → 0.06秒、exp(1, 100_000_000) でも 150秒で完了するレベルになります。
Binary Splitting の限界
ただし、Binary Splitting だけでは解決できない問題があります。たとえば exp(1.1111..., 100_000) の計算は、依然として 70秒かかります。
理由は引数 x の桁が密に詰まっているためです。exp(x) の各項は xᵏ / k! の形をとります。x = 1.1111... という数では細かい桁が連続するため、xᵏ がすぐ数万桁の巨大数まで膨らみます。Binary Splitting で分割統治しても、各ノードで扱う数値がそもそも大きいため、頭打ちになります。
第3層: Bit-burst (Digit-burst) による引数の分解
そこで使われるのが、引数を「倍々に伸びる桁長のピース」へ分割する方法です。
x = 1.1111111111111... = 1 + 0.1 + 0.011 + 0.0001111 + 0.000000011111111 + ... ↑ ↑ ↑ ↑ ↑ 1桁 1桁 2桁 4桁 8桁
精度 100,000桁の場合でも、18 ピースで済みます。
ここで exp の以下の性質を活用します。
exp(x₁ + x₂ + x₃ + ...) = exp(x₁) · exp(x₂) · exp(x₃) · ...
加法が乗法へと変換できるため、分解した各ピースで exp を計算し、最後にそれらを掛け合わせるだけで済みます。各ピースは桁が少ない「小さい有理数」なので、Binary Splitting も効果的に効きます。このように、第2層と第3層は独立した工夫として組み合わせられる構造になっています。
トータルの効果としては、exp(1.1111..., 100_000) が 70秒 → 0.5秒、exp(1.1111..., 100,000,000) でも 30分で完了します。
tompng さんは発表のなかでこのように語っていました。
Split number + Binary Splitting でいける → 名前があるはず → Bit-burst だった
"They say don't reinvent the wheel. But they never tell you how fun it is."
「車輪の再発明はするな」とよく言われますが、自分でゼロから辿り着くプロセスにも価値がある、という一言が印象的でした。
なお BigDecimal は前述のとおり仮数を 9 桁ずつパックした内部表現を使っているため、ビット単位よりも桁単位で分割する方が自然です。tompng さんはこの点をふまえて "Digit-burst" と命名し直しています。命名のユーモアであり、ビット変換のオーバヘッドが減る分わずかに効率も良いとのことです。
精度管理の落とし穴
発表中盤では、以下のようなコードが紹介されていました。
def sinh(x, prec) (exp(x, prec) - exp(-x, prec)) / 2 # バグです end sinh(0.002, 10) # exp( 0.002, 10) = 1.002002001 # exp(-0.002, 10) = 0.9980019987 # 差 = 0.0040000022 ← 正しい桁は 7桁のみ # 要求精度10桁なのに。
exp(0.002) と exp(-0.002) はどちらも 10桁精度で正しく計算されています。それでも引き算した瞬間、先頭の 1.00... と 0.99... が打ち消され、有効な桁が一気に削られてしまいます。これは破滅的桁落ちと呼ばれる現象とのことです。対策はシンプルで、内部で余分な精度を持って計算し、最後に丸めればよい、という方法が紹介されていました。BigDecimal を使う側でも、知っておきたい話だと感じました。
設計哲学
最後のスライドでは、tompng さんの設計哲学が示されていました。
Numbers are fun — Not just data, but building blocks. Reinterpret the Reality. Slice and Rearrange, like Magic.
数を「データ」ではなく「組み立てブロック」として捉え直し、切ったり並べ直したりして本質へ迫る姿勢が、今回の発表全体を貫いていました。この3行にその姿勢が凝縮されていました。
感想
「BigMath.exp を速くする」というシンプルな題材から、60,000年 → 150秒 という大きな改善を実現するストーリーでした。NTT・Binary Splitting・Bit-burst という 3 つの独立した工夫を重ねた結果であり、非常に印象に残りました。
発表全体を通して感じた「ロマン駆動で深く掘る」「車輪の再発明を楽しむ」という姿勢は、業務でコードを書くなかでも参考にしたいと感じました。普段は「ベストプラクティスを踏襲する」「既存ライブラリを使う」を選択することが多いですが、自分の手で原理から辿り直す時間も意識的に確保していきたいです。
最後のスライドの締めくくりも印象的でした。
BigMath is now N times faster. N: your favorite uint32 number.
精度や引数によって 1倍〜4,294,967,295倍まで幅がある、というユーモアであり、冒頭の「9 digits per word（uint32 で 9桁パッキング）」への伏線回収にもなっています。発表全体の構成の妙を感じる一文でした。会場は大きな拍手に包まれていました。
RubyKaigi 2024 の "Writing Weird Code" のときも感じましたが、tompng さんの発表は毎回 Ruby のおもしろさを技術的に深いところから再認識させてくれます。来年も楽しみにしています。
Techouseでは、社会課題の解決に一緒に取り組むエンジニアを募集しております。 ご応募お待ちしております。
