カテゴリー別アーカイブ: プログラミング

「週刊 代数的実数を作る」創刊

コンピューター上で実数を取り扱うには、いくつかの方向性がある。普通は浮動小数点数によって近似することが多いと思うが、多倍長計算を始めとする、「コストをかけてでも正確に」計算するという方向性もある。

そのような「正確に取り扱える」実数のクラスとしては、整数(多倍長整数)や有理数はある程度普及していると思う(標準で備えているプログラミング言語がある)。それよりも広いクラスとして、代数的実数、つまり(整数または有理数係数)代数方程式の根となるような実数全体、というものがある。

代数的実数が計算機で取り扱えるということ自体は割と知られた事実だと思うが、実装は割と大変で、工夫の余地がある。有理数のように「GCD さえ実装すればよい」というものではない。

かくいう私も最近までその辺を真面目に勉強しようとは思っていなかったわけだが、何となくモチベーションが湧いてきたので、代数的実数に関するアルゴリズムを勉強しつつまとめたものを記事として Web 公開してみようかと思った次第である。

実装には筆者の好みで、 Haskell を使う。実際のところ、 Haskell による代数的実数の実装は既にあるようだが、まあ気にしない(自身の勉強が主目的なので)。

というわけで、以下のページで公開している:

https://miz-ar.info/math/algebraic-real/

「週刊」と名乗っているが、毎週末に更新することを目指している。果たしていつまで続くかは不明である。 続きを読む

交差型 (intersection types)

型システムの勉強の続き。

有界量化を持つ体系 System F<: (Fsub) に続いて、交差型を持つ体系 F (Finter) を実装する。

作ったものは、前と同じ GitHub に置いてある:

https://github.com/minoki/LambdaQuest

TaPL でも交差型について言及されているが、あまり詳しく書いてあるとは言えない。そこで、B. C. Pierce の Programming with Intersection Types and Bounded Polymorphism (1991) という論文を参考にした。著者のサイトにPDFが置いてある。似たようなトピックの論文が他にもあるようだが、それらとの関係は確認していない。

論文の Finter では有界量化の上界に関して反変な部分型関係を入れているが、それをやると(TaPLにもあるように)部分型関係が決定手続きでなくなるらしいので、今回実装した Finter には(前回実装した Fsub にも)それは入れていない。

続きを読む

型システムの勉強

型システムを自分で設計したいと思ったので「型システム入門 プログラミング言語と型の理論」(原題:Types and Programming Languages, 略して TaPL)を読んで勉強している。

この記事は私の雑な理解を吐き出したものであり、あまりまとまっていない。しかし、何かしらをアウトプットすることに意義がある(キリッ 続きを読む

Haskell でオレオレ Num クラスを作るための考察

以前の記事に書いたように、 Haskell 標準の Num クラスには色々と不満がある:

Haskell の Num クラスに対する不満

結論としては「過去に遡って Num クラスの定義を変えるしかない」だったわけだが、時間干渉も因果律への反逆もできない我々としてはその選択肢は現実的ではないので、独自の Num クラス(オレオレ Num クラス)を作ることにする。この記事は、筆者がオレオレ Num クラスを作った際に考えたことをまとめたものである。

続きを読む

C++ から OpenCL を使う(その0):準備

21世紀を生きる者として、並列コンピューティング技術の一つや二つは扱えなければならない。

この間書いた Haskell で並列評価する記事は CPU のマルチコアを活用するものだったが、今度は CPU 以外のデバイス(GPU を念頭に置く)を活用できる技術を使いたい。いわゆる GPGPU をやりたい。(技術に入門するのが目的であって、計算能力を活かして特にこれがしたいという訳ではない。そもそも筆者の手持ちの GPU の計算能力などたかが知れているが……)

N 社の GPU を前提にするなら CUDA という選択肢もあるだろうが、ここでは移植性を重視して OpenCL を試すことにする。(というか、 Mac ユーザー的には CUDA という選択肢は存在しないも同然)

続きを読む

雰囲気で並列プログラミングをやってみる

Haskell での並列プログラミングをマスターしたい、とは言わないが、「全然わからない、俺たちは雰囲気で並列プログラミングをやっている」程度のことは言えるようになりたい。

今回は「データ構造の各要素を並列で評価する」ことを目指す。以下の内容は筆者がいい加減な知識で書いているので、そういうつもりでテキトーに読んでほしい。 続きを読む