ハクソク

世界を動かす技術を、日本語で。

HNに表示: 非重複区間の集合で動作する計算機を作りました

22日前原文(victorpoughon.github.io)

概要

Interval Union Arithmetic は、実数だけでなく 区間の合併 上で計算を行う新しい電卓システム。 ゼロを含む区間での除算 にも対応し、演算結果が 閉じた集合 として保たれる特徴。 不確実性の表現 や 浮動小数点誤差への耐性 に優れる。 シンプルな構文 で使いやすく、 オープンソース で公開。 今後の拡張 も活発に計画中。

区間合併演算電卓とは

  • Interval Union Arithmetic （区間合併演算）の実装例

    • 区間 [a, b] ：a 以上 b 以下の全ての数を表現
    • 区間合併 [a, b] U [c, d] ：重なりのない複数区間の集合

  • 通常の区間演算の拡張

    • ゼロを含む区間での除算が可能
      • 例：2 / [-2, 1] → [-∞, -1] U [2, +∞]
    • 閉じた演算体系 の維持

  • 包含性質 （Inclusion Property）

    • 入力区間から任意の実数を選び、同じ式を実数で計算した場合、結果は必ず出力区間合併に含まれる

  • 不確実性の表現

    • 例：50 * (10 + [-1, 1]) → [450, 550]

  • 複雑な式や合併演算もサポート

    • 例：([5, 10] U [15, 16]) / [10, 100] → [0.05, 1.6]

主な演算例

  • 加算 ：[90, 100] + [-2, 2] → [88, 102]
  • 減算 ：[14, 16] - [8, 12] → [2, 8]
  • 乗算 ：[-5, 10] * [2, 4] → [-20, 40]
  • 除算 ：[2, 4] / [-1, 2] → [-∞, -2] U [1, +∞]
  • 指数 ：[2, 3] ^ [-2, 3] → [0.1111, 27]

関数・定数サポート

  • 定数 ：inf, ∞, pi, e など
  • 下限・上限 ：lo([1, 2]) → [1, 1]、hi([1, 2]) → [2, 2]
  • 絶対値・平方根 ：abs([-10, 5]) → [0, 10]、sqrt([9, 49]) → [3, 7]
  • 対数・指数 ：log10([1, 10000]) → [0, 4]、exp([-∞, 0] U [1, 2]) → [0, 1] U [2.718, 7.389]
  • 三角関数 ：cos([pi/3, pi]) → [-1, 0.5]、tan([pi/3, 2*pi/3]) → [-∞, -1.732] U [1.732, +∞]
  • min/max ：min([1, 2], [0, 6]) → [0, 2]、max([0, 10], [5, 6]) → [5, 10]

構文と使い方

  • 区間表記 ：[a, b]、単独数値は [a, a] として扱う
  • 合併演算 ：U で区間を合併
  • ネストや関数も可能
    • 例：[0, cos(2*pi)] → [0, 1]
  • 例外的な合併例 ：1 / [-2, 1] → [-∞, -0.5] U [1, +∞]

フル精度モード

  • IEEE 754倍精度浮動小数点 に基づく
  • 外向き丸め で常に真の値を含む区間を保証
  • 入力値解釈・出力表示の切替 が可能
  • 例：0.1 + 0.2 → [0.29999999999999993, 0.3000000000000001]

バグ・オープンソース・今後の展望

  • バグ報告 ：GitHubで受付
  • エンジン（not-so-float）もTypeScriptで公開
  • 今後の拡張
    • フル精度モードの細分化
    • 前回結果(ans)変数の追加
    • 合併の優先順位改善
    • 空集合入力サポート

区間合併演算の意義と背景

  • 従来の区間演算 ではゼロを含む区間の割り算が困難
    • 例：1 / [-1, 2] → [-∞, +∞] または未定義
    • 区間合併演算 なら [-∞, -1] U [0.5, +∞] と明確に分離
  • 非連続関数（tanなど）も閉じた体系で計算可能
  • 2017年の論文「Interval Unions」 （Schichl ら）に基づく理論
  • TypeScript製のインタラクティブ電卓 として実装
  • 浮動小数点誤差にも強い 設計

区間合併演算電卓 は、数値計算における不確実性やゼロ割りなどの課題を柔軟に解決し、より信頼性の高い計算結果を提供する 革新的なツール です。

Hackerたちの意見

ここに作者がいます。外向きの丸めは、精度の問題を解決するために間隔算術で最も知られていることですが（「フル精度モード」を有効にして0.1+0.2を試してみてください）、私にとっては本当に残念です。外向きの丸めはクールだけど、研究論文で知られている「包含特性」は、あらゆるスケールで機能します！これが、例えば50 * (10 + [-1, 1]) [450, 550]のようなことを可能にするんです。素晴らしいと思います。これにユニオンレイヤーを追加すると、平方関数の真の逆数のようなさらにクールなことができるようになります。実はそれはsqrtじゃないんですよ。「sqinv(64)」を試してみてください。私は間隔計算機を、別のプロジェクトのために必要だった間隔ユニオン算術の実装をテストする手段として作ったんです。[0] https://github.com/victorpoughon/not-so-float [1] https://victorpoughon.github.io/bidicalc/ [2] https://news.ycombinator.com/item?id=46234734

└

いいね！君が実装した算術がIEEE 1788の区間算術標準とどう違うのか、すごく興味あるよ（そしてその2つの論文がどう関係してるのか）。君が言ってた課題に対処するために、最初からやり直さなきゃいけなかったの？それともIEEE標準の上に構築できるものだったの？

└

すごく面白いね！もっと色々試してみるつもりだよ！二つ質問があるんだけど：

  • これに多値関数を追加するのはどれくらい難しいかな？asin(1)から[π/2, π/2] + n[2π, 2π]の全ての値を得られたらめっちゃ便利なんだけど、Mathematicaを使わずに済むし。
  • それと、

ユーザーが入力した数値は、入力された10進数表現に最も近いIEEE 754値を含む最小の区間として解釈されるが、どちらの境界もその値には等しくない。 これって何か見落としてる？それとも逆にすべきじゃない？つまり、出力の境界は入力数を含む最も近い2つのIEEE 754数値であるべきじゃないかな？書き方からすると、最小の区間はIEEE754(input)+[-epsilon, epsilon]、で、epsilonは無限に小さい値って解釈するけど。

これ素晴らしいですね！マット・キータの暗黙のサーフェスに関する研究や、その最適化に間隔数学を使っていることに興味があるかもしれません：https://youtu.be/UxGxsGnbyJ4?si=Oo6Lmc4ACaSr5Dk6&t=1006

これ、間隔算術を使って作ったグラフ計算機に興味があるかもしれません：https://memalign.github.io/m/formulagraph/index.html これがどう機能するかの詳細や、関連する間隔数学のコードへのリンクもあります：https://memalign.github.io/p/formulagraph.html

とても良いですね、共有してくれてありがとう！もしかしたら、どの上限や下限の値が間隔に含まれているかを示すといいかも？私が知っている表記法では、値が間隔に含まれていない場合は外向きの括弧を使います。それは常に無限大に適用されます。ここでのケースに適用すると、]-∞, -1] U [0.5, +∞[ となります。間に除外された間隔は]-1, 0.5[になりますよね。これがmin（そして同様にmax）が機能する方法です、合ってますよね？min(A, B) = [lo(A,B), lo(hi(A), hi(B))]。編集：アイデア：ユーザーが結果セクションから入力フィールドに数式をコピーできるようにする。

└

私もこれには少し混乱しました。標準の表記法は丸括弧だと思ってたんですが、ASCIIではうまく機能しないのかもしれませんね？

└

リンクされた論文[0]を読むと、閉区間についてだけ説明されています。「間隔のユニオンは、極端な間隔の境界が±∞である閉じた非重複の間隔の集合です。」[0]: https://www.ime.usp.br/~montanhe/unions.pdf

└

それをサポートすることは可能ですが、コードが非常に複雑になります。最初からサポートしないことに決めました。でも、クールな追加機能になるでしょうね！

素晴らしい！！間隔算術が大好きで、グラフ計算機プロジェクトのためにTS実装も書きました。確かに、すごく過小評価されていると思いますし、指向された丸めがもっと多くの言語で使えるようになればいいなと思います。

└

そうだね、めっちゃ面白いよね。君が言ったように、IEEE 754の仕様では、浮動小数点数の完全な実装がプログラム的に丸めモードを選べる方法を提供することが求められてるんだ。私の知る限り、これができるのはCだけで、しかもハードウェアのサポートに依存するんだよね。JSでは、汚いTypedArrayキャストを使わなきゃいけなかった。これってエンディアンの関係で偶然うまくいく感じだけど、技術的にはそのためのAPIがあるはずなんだ！IEEE 754には、他にも使われてないものがあって、例えば不正確ビットやシグナルNaNとかね！

すごいね！いくつかの操作は完全には理解できてないけど、理解できる部分は結構面白いよ。授業で、区間に対する算術の概念を紹介してもらえたらよかったなと思う。基本的な統計の信頼区間では±が出てくるし、二次方程式でもそうだよね。結果として得られた一連の操作を連鎖させられないのがちょっと不満だった。±の2つの値に対して操作を繰り返さなきゃいけなかったから。先生は、一般的な応用に戻したいから、こういうことにこだわりたくないのは分かるけど、もうちょっとこういうことができるってヒントをくれたらよかったな。君が持ってるものはこれを超えてるのは分かってるけど、区間をデータの一部として扱うことが一定の操作の振る舞いを持つっていうのは、ある意味で納得できることだなって思った。

最近、集合のメンバーシップの観点から似たようなものを実装したんだ。だから、区間のメンバーシップの完全なブール解析ができるように、補集合の操作を含める必要があった。君の区間はすべて閉じた集合だから、補集合は開区間になるんだよね。実用的な目的のために、端点が集合のメンバーかどうかは重要じゃないから、開区間と閉区間を区別しないことにしたよ。もちろん、不正確な算術では、その集合が開いているか閉じているかはあまり明確じゃないかもしれないね。

最初にtickっていうClojureの時間区間ライブラリを書いたときに、区間算術について知ってたらよかったな。これにはアレンの区間代数の実装が含まれてるんだ。実用的な計算に役立つ離散区間の集合の概念も取り入れてるし、特定の年の休暇の区間を決定するのに使えるんだ（人事計算のためにね）。アレンの研究をあまり知らなかったけど、これらの集合の利点に偶然気づいたんだ。 https://github.com/juxt/tick https://en.wikipedia.org/wiki/Allen's_interval_algebra

区間の和に論理を拡張するのは面白そうだけど、その複雑さはどうなの？区間に対する操作が2つの区間を生み出す可能性を導入するから、N回の操作を実行するのは指数的な複雑さになりそうだよね。残念ながら、抽象解釈のような一般的な区間のアプリケーションで使うのは難しくなると思う。十分な区間があるときに近似を導入しない限りは。

└

うん、これはよく知られてるよね（例えば、抽象解釈の中で）。君が言ったように、通常はこれらのオブジェクトのサイズに「上限」を設定して、上限に達したら区間をマージし始めるんだ。でも、少なくとも抽象解釈では、彼らは単に区間よりも洗練されたドメインを考慮しているようだね。

これ、ネイティブの日時型をサポートできるのかな？私は繰り返しイベントやスケジュールを管理するために、もっとひどいものを作ったことがあるよ。