分離された区間集合上で計算する計算機

• 分離された区間の合併を入力として受け取り、四則演算、関数呼び出し、べき乗まで実行でき、interval union arithmeticをブラウザ上で直接計算可能
• 結果区間は、入力された合併から選んだ値で同じ式を実数上で計算したときの値を必ず含み、0を含む区間による除算も分離された合併の形で処理可能
• 1 / [-2, 1]では[-∞, -0.5] U [1, +∞]が、tan([pi/3, 2*pi/3])では[-∞, -1.732] U [1.732, +∞]が得られるように、不連続な区間結果と無限大境界の表現をサポート
• [a, b], [a, b] U [c, d], ネストした区間構文、lo, hi, hull, log10, cos, min, maxなど、多様な表記と関数をサポート
• 完全精度モードでは、IEEE 754倍精度に基づく外向き丸めで実際の値を包む区間を返し、0.1 + 0.2を[0.29999999999999993, 0.3000000000000001]として表示するのが特徴

---

概要

• 分離された区間の合併を対象に計算する計算機で、通常の実数だけでなくinterval union arithmeticの実装もサポート
  • 区間[a, b]はaからbまでのすべての数を意味し、[a, b] U [c, d]は互いに離れた区間の合併を意味する
  • 通常の区間演算を拡張した形で、0を含む区間による除算も閉性を保ったまま計算可能
• 包含性を保証
  • 入力された各合併からそれぞれ任意の実数を1つずつ選んで同じ式を実数上で計算すると、その結果は出力合併に必ず含まれる構造
• 不確かさを表現可能
  • 50 * (10 + [-1, 1])の計算結果として[450, 550]の例を提示
• 複雑な区間式の計算をサポート
  • U演算子を使って( [5, 10] U [15, 16] ) / [10, 100]のような式を入力可能
  • 結果[0.05, 1.6]の例を提示
• 演算結果が分離された合併になる場合がある
  • 1 / [-2, 1]の結果は[-∞, -0.5] U [1, +∞]
  • tan([pi/3, 2*pi/3])の結果は[-∞, -1.732] U [1.732, +∞]
• 完全精度モードでは通常の計算機のように使いつつ、浮動小数点精度の問題を含めた実際の値を包む区間結果を提供
  • 0.1 + 0.2の結果として[0.29999999999999993, 0.3000000000000001]の例を提示

構文

• 基本表記をサポート
  • 区間表記[a, b]をサポート
  • 例: [0.5, 0.6]
• 合併表記をサポート
  • [a, b] U [c, d]形式をサポート
  • 例: [0, 1] U [5, 6]
• 四則演算およびべき乗をサポート
  • 加算 A + B 例 ➤ [90, 100] + [-2, 2] 結果 [88, 102]
  • 減算 A - B 例 ➤ [14, 16] - [8, 12] 結果 [2, 8]
  • 乗算 A * B 例 ➤ [-5, 10] * [2, 4] 結果 [-20, 40]
  • 除算 A / B 例 ➤ [2, 4] / [-1, 2] 結果 [-∞, -2] U [1, +∞]
  • べき乗 A ^ B 例 ➤ [2, 3] ^ [-2, 3] 結果 [0.1111, 27]
• 関数と定数をサポート
  • 関数呼び出し function(...) 形式をサポート
  • log10([1, 10000]) の結果は [0, 4]
  • 定数名の入力をサポート
  • pi の結果は [3.1415926535897927, 3.1415926535897936]
• 数値と区間の混在入力が可能
  • [1, 2]のように角括弧構文で区間を入力可能
  • 3.14のような数値は幅0の狭い区間[3.14, 3.14]として解釈される
  • 完全精度モードではこれに関する細かな違いがある
  • 1.55 + [-0.002, 0.002] の結果は [1.548, 1.552]
• ネストした区間構文をサポート
  • [0, [0, 100]] を入力でき、結果は [0, 100]
  • 区間境界を定義する内部の数値まですべて区間として解釈される構造
  • ネストした区間で境界位置に入った区間は、その区間の上限を取る方式
  • この設計により境界そのものに算術を適用可能
  • [0, cos(2*pi)] の結果は [0, 1]

対応関数

• 定数をサポート
  • inf, ∞, pi, e をサポート
  • [-inf, 0] * [-inf, 0] の結果は [0, +∞]
• 境界抽出関数をサポート
  • lo(A) は下限を返す
    • lo([1, 2]) の結果は [1, 1]
  • hi(A) は上限を返す
    • hi([1, 2]) の結果は [2, 2]
• 区間外包の計算をサポート
  • hull(A) は合併を1つの区間で包む形
  • hull([1, 2] U [99, 100]) の結果は [1, 100]
• 基本的な数学関数をサポート
  • abs(A) 例 abs([-10, 5]) 結果 [0, 10]
  • sqrt(A) 例 sqrt([9, 49]) 結果 [3, 7]
  • sqinv(A) 例 sqinv([4, 64]) 結果 [-8, -2] U [2, 8]
• 対数および指数関数をサポート
  • log(A) 例 log([0, 1]) 結果 [-∞, 0]
  • log2(A) 例 log2([64, 1024]) 結果 [6, 10]
  • log10(A) 例 log10([0.0001, 1]) 結果 [-4, 0]
  • exp(A) 例 exp([-∞, 0] U [1, 2]) 結果 [0, 1] U [2.718, 7.389]
• 三角関数および逆三角関数をサポート
  • cos(A) 例 cos([pi/3, pi]) 結果 [-1, 0.5]
  • sin(A) 例 sin([pi/6, 5*pi/6]) 結果 [0.5, 1]
  • tan(A) 例 tan([pi/3, 2*pi/3]) 結果 [-∞, -1.732] U [1.732, +∞]
  • acos(A) 例 acos([-1/2, 1/2]) 結果 [1.047, 2.094]
  • asin(A) 例 asin([0, 1]) 結果 [0, 1.571]
  • atan(A) 例 atan([-10, 2]) 結果 [-1.471, 1.107]
• 最小値・最大値関数をサポート
  • min(A, B) 例 min([1, 2], [0, 6]) 結果 [0, 2]
  • max(A, B) 例 max([0, 10], [5, 6]) 結果 [5, 10]

完全精度モード

• IEEE 754倍精度浮動小数点上で外向き丸めを実装
  • JavaScriptのnumber型を使用
  • 同じ式を実数かつ無限精度で計算したときの実際の値を、結果区間が必ず含むことを保証
• 0.1 + 0.2 の事例を含む
  • 0.3 は倍精度浮動小数点で正確に表現できない
  • interval arithmetic は 0.3 を含む区間計算を行う
• 完全精度モード有効時の動作
  • ユーザーが入力した数値は、入力した10進表現に最も近いIEEE 754値を含みつつ、両端境界がその値と等しくない最小の区間として解釈される
  • 出力数値は利用可能なすべての10進桁で表示
  • Number.toString() を使用
• 完全精度モード無効時の動作
  • ユーザーが入力した数値は、入力した10進表現に最も近いIEEE 754値と両境界が等しい退化区間として解釈される
  • 出力数値は小数点以下最大4桁で表示
  • Number.toPrecision() を使用

バグ

• 計算機にはまだバグが残っている可能性があると言及
• 問題報告先としてGitHub Issuesリンクを案内

オープンソース

• Interval Calculator と計算機エンジン not-so-float はどちらもオープンソースとして公開
• GitHub Sponsors の支援リンクを含む

今後の作業

• 完全精度モードを2つの制御項目に分割予定
  • 入力解釈
  • 表示精度
• ans 変数を追加予定
  • 前回の入力結果を保存する変数
• 共通部分演算子または関数を追加予定
• U 演算子の優先順位の直感性を改善予定
• 空の合併の入力をサポート予定

[GN⁺]

Hacker News のコメント

• 作者として言うと、外向き丸めは精度問題への対処として interval arithmetic で最も有名だけれど、そこだけが注目されるのは少し残念だと思う。論文でいう 包含性質 はあらゆるスケールで機能し、そのため 50 * (10 + [-1, 1]) = [450, 550] のような結果が自然に得られる。ここに union レイヤーを載せると、平方関数の真の逆関数のようなものまで扱えるようになり、sqrt ではなく sqinv(64) を試すと感覚がつかめる。実際、この interval calculator は、別プロジェクトである backwards updating spreadsheet のために作っていた interval union arithmetic 実装を試す目的で作ったものだった。実装は not-so-float、関連プロジェクトは bidicalc と HN の議論 にある
  • 実装した arithmetic が IEEE 1788 標準とどう違うのか気になる。リンクされている 2 本の論文がその標準とどういう関係にあるのかも知りたい。記事で言及されている問題を解決するには完全に新しく始める必要があったのか、それとも IEEE 標準の上に積み上げられたのかも気になる
  • 本当にすばらしくて、もっと触ってみるつもり。特に 2 点気になる。第一に、多価関数 を追加するのがどれくらい難しいのか。たとえば asin(1) で Mathematica なしでも [pi/2, pi/2] + n[2pi, 2pi] の全体集合を得られるととても良い。第二に、ユーザー入力の数値を解釈する説明文が少しわかりにくかった。自分の理解では、入力値を含む最小区間の 出力境界値 は、入力値を挟む最も近い 2 つの IEEE 754 数であるべきだと思うが、今の文だと IEEE754(input)+[-epsilon, epsilon] のようにも読めて、意味が違って感じられた
• これは本当に良い。Matt Keeter の implicit surfaces の仕事と、interval math を使った最適化も興味深く見られるはず。この発表 で関連する内容を確認できる
• 自分も interval arithmetic で作ったグラフ描画計算機があるので、興味があるかもしれない。実際に試せる formulagraph があり、仕組みや関連コードの説明は この投稿 にまとめてある
  • 第一印象では GrafEq に似ていると感じた。昔の GrafEq を思い出す
• これが面白くて、自分も Raku で簡単な Math::Interval ライブラリを書いてみたことがある。raku-Math-Interval で、Raku の組み込み Junction と Range クラスを土台にした実験で、かなり興味深い体験だった
• とても良いし、共有してくれてありがとう。interval で 上限・下限を含むかどうか を表示してくれると、さらに良いと思う。自分が慣れている記法では、値を含まないときは外向きの括弧を使い、無限大にも常にそう適用する。たとえば ]-∞, -1] U [0.5, +∞[ のように書き、真ん中の除外区間は ]-1, 0.5[ になる。自分の理解では min と max もこのように解釈されるように見える。それと、結果欄の式をクリックまたはタップすると入力欄にコピーされる UI アイデア もあると便利そう
  • リンクされていた 論文 を読んでみたが、ここでは 閉区間 だけを説明していた。interval union は閉じていて互いに分離した区間の集合であり、両端の extreme interval の境界だけが ±∞ になりうると定義されていた
  • そういう表記をサポートすることは可能だが、コードが はるかに複雑 になる。だからかなり早い段階で対応しないと決めた。それでも、すてきな追加機能にはなりうる
  • 自分もこの部分は少し混乱した。自分が知っていた 標準的な記法 は丸括弧だったが、ASCII 環境ではあまり合わないのかもしれないと思った
• とてもすばらしい。すべての演算を完全に理解したわけではないが、理解できた部分だけでもかなり印象的だった。授業で 区間に対する算術 にもっと早く触れられていればよかったと思う。基礎統計の信頼区間や二次方程式の ± のように、すでに似た概念は出てくるのに、結果を 1 つのデータとして続けて計算することはできず、毎回 ± の 2 つの値を別々に扱わなければならないのが、いつも少し惜しく感じていた。もちろん教師が応用へ早く戻りたがるので深く扱わない理由は理解できる。それでも、こういう対象にも一般的な算術が可能だというヒントくらいはあってよかった。今示されているものはそこからさらに大きく進んだ形だが、interval を独自の振る舞いを持つデータとして見る視点が筋が通っているという 裏付け のように感じられた
• 以前 Clojure の時間区間ライブラリ tick を初めて使ったとき、interval arithmetic を知っていたらよかったのにと思う。このライブラリには Allen's Interval Algebra の実装も含まれていて、実務計算に役立つ 離散区間集合 の概念も取り入れていた。たとえば、ある年に属する休暇区間の集合を計算する HR 業務のようなものにうまく合う。自分は Allen の仕事のことだけ知っていて、こうした集合がもたらす利点は偶然見つけたようなものだった。コードは juxt/tick にある
• このツールの有用性は十分わかるが、個人的には 確率的計算機 の方がもっと役に立ちそうだと思う。たとえば 1 / [-1, 2] のような結果は、どの値がどれくらいもっともらしいかを教えてくれないし、入力が一様だと仮定しても出力は明らかに 一様分布 ではなさそうだ
• 自分も最近似たようなものを実装したが、観点は 集合への所属性 の側だった。だから interval membership の完全な Boolean 解析をするには 補集合演算 が必要だった。ここでの区間はすべて閉集合なので、補集合は開区間になるが、自分の用途では端点を含むかどうかは重要ではなかったので、開区間と閉区間をあえて区別しなかった。しかも、不正確な算術では集合が開いているのか閉じているのか自体がうまく定義できないこともあると思う
• union of intervals へと論理を拡張したのは見事だが、複雑性 が気になる。1 回の演算で区間が 2 つ生まれうるなら、N 回の演算で場合によっては 指数的増加 が起こりそうだ。そうなると、一定数以上で近似を導入しない限り、abstract interpretation のような一般的な用途には現実的でなくなるのではという懸念がある
  • もっともな指摘で、この問題は abstract interpretation の分野ではよく知られている。言うとおり、通常はオブジェクトサイズに cap を設け、限度を超えたら区間をまとめてしまう方法が使われる。ただ、少なくとも abstract interpretation では interval よりもさらに 精密なドメイン が使われることも多いようだ