コンピューター上で実数を取り扱うには、いくつかの方向性がある。普通は浮動小数点数によって近似することが多いと思うが、多倍長計算を始めとする、「コストをかけてでも正確に」計算するという方向性もある。
そのような「正確に取り扱える」実数のクラスとしては、整数(多倍長整数)や有理数はある程度普及していると思う(標準で備えているプログラミング言語がある)。それよりも広いクラスとして、代数的実数、つまり(整数または有理数係数)代数方程式の根となるような実数全体、というものがある。
代数的実数が計算機で取り扱えるということ自体は割と知られた事実だと思うが、実装は割と大変で、工夫の余地がある。有理数のように「GCD さえ実装すればよい」というものではない。
かくいう私も最近までその辺を真面目に勉強しようとは思っていなかったわけだが、何となくモチベーションが湧いてきたので、代数的実数に関するアルゴリズムを勉強しつつまとめたものを記事として Web 公開してみようかと思った次第である。
実装には筆者の好みで、 Haskell を使う。実際のところ、 Haskell による代数的実数の実装は既にあるようだが、まあ気にしない(自身の勉強が主目的なので)。
というわけで、以下のページで公開している:
https://miz-ar.info/math/algebraic-real/
「週刊」と名乗っているが、毎週末に更新することを目指している。果たしていつまで続くかは不明である。
内容について
現時点では「#0 イントロダクション」と「#1 一変数多項式環」を公開している。今後、スツルム列を使った実根の数え上げ、終結式による四則演算などが公開される予定である。整数係数多項式の因数分解アルゴリズムも必要になるが、それはこれから勉強しなければならない。
計算機代数といえばグレブナー基底だが、それをこの連載で取り上げる(&実装する)ことになるかはまだよくわかっていない。「代数的実数を係数とする多項式の実根を求める操作」なんかはモロに多変数多項式な感じがするが、果たしてどう処理するのが一番良いのか。
当面は代数的「実数」を扱うが、それを複素数を含む真の代数的数 \(\overline{\mathbf{Q}}\) に拡張するのはそう難しくないはずだと思っている。たぶん。範囲を実数に絞るメリットとしては、標準的な全順序を利用できる、というものがある。
その他
原稿は Markdown で書いて、 Hakyll/Pandoc で処理している。やろうと思えば Pandoc で LaTeX に変換し、 PDF を出力することもできる。 Markdown であっても Pandoc で処理するのが前提なら LaTeX の数式を使えるし、 \newcommand によるマクロも使える。しかし定理・証明環境みたいなものは Markdown には対応物がない。また、 Markdown は英語圏発祥なので、ルビなどの機能も弱い。もしかしたらそのうち別のフォーマットに移行するかもしれない。
せっかく気合を入れて書くのだから、何らかのマネタイズの手段(それで生活できるわけではないが、モチベーションの足しになる程度のもの)も考えたいが、どうするのが一番良いか。私程度の知名度で、このようなマニアックなテーマのページに広告を設置しても数十円にもならないだろう。日本で合法的かつ手軽に使える Web 投げ銭みたいなシステムはあるだろうか。電子書籍版を有料で販売する、という風な方法が一番良いのだろうか。
初めまして,ehito(えひと)と申します.私は maxima で
>「代数的実数を係数とする多項式の実根を求める操作」
などを実装しており,大変不躾(&せっかち)ではございますが,「週刊 代数的実数を作る」の(サブ)ゴールをどの辺りにお考えなのかが気になっております.
こんにちは。
当面の、妥当な目標としては「代数的実数を係数とする多項式の実根を求める操作」およびその複素版(代数的数の代数閉体としての操作)あたりかと考えています。
一通り機能が揃ったら、実装の効率化・高速化を目指すかもしれません。
そのほかの計算機代数のトピックに関しては、やっていたらキリがなくなりそうなので、現時点では消極的に考えています。
更新,ご苦労様です.少し間があいたのでいよいよ多項式の因数分解に突入かと思いきや,区間数とは,...
私は Maxima 上に Loos-Trager の方法による(CAD には重過ぎる)primitive element ベースのソルバーを実装した程度ですが,Berlekamp アルゴリズムから代数体上の多項式の分解までとなると,Julia の Nemo を超える実装ですから,連載のタイトルが「計算機代数システムを作る」とかになりそうな気配さえ漂います.
なお,既存の CAS のマニュアルもちょっとしたサーベイになっていたりしますね.
http://magma.maths.usyd.edu.au/magma/handbook/text/217#1883
次回も期待しています.
ピンバック: 「週刊 代数的実数を作る」を終えて | 雑記帳
ピンバック: 技術書典5に代数的数を作る本を出します | 雑記帳
ピンバック: 同人誌「代数的数を作る」ができるまで/PandocとかLaTeXの話 | 雑記帳