この間、フィボナッチ数を計算する記事を書いていたら、@fetburner氏にこういう問題を教えて頂いた：
「数学」カテゴリーアーカイブ
最速のフィボナッチ数計算を考える
Qiitaにこういう記事を書いた：
Haskellでフィボナッチ数列 〜Haskellで非実用的なコードを書いて悦に入るのはやめろ〜
↑の記事ではメモ化しない計算法が遅いこと、Haskellには遅延評価の罠があって正格にすると早くなること、「n番目のフィボナッチ数」をピンポイントで計算する場合は（行列またはQ(√5)の）冪乗を使う方法が早いこと、一般項（ビネの公式）をその辺の浮動小数点数で計算するのは使い物にならないこと、などを述べた。
まあ、「Haskellでは fib 0 = 0; fib 1 = 1; fib n = fib (n-1) + fib (n-2) でフィボナッチ数が計算できます！」に対する注意喚起としてはこれで十分すぎる内容なのだが、「n番目のフィボナッチ数をピンポイントで計算する方法」についてはもっと深掘りできる。
この記事では、数学的な考察も交えて、「n番目のフィボナッチ数をピンポイントで計算する方法」をより高速化してみたい。（計算量としてはどっちみち O(log n) くらいなのだが、定数倍の部分で高速化する）
なお、記事タイトルには「最速の」と書いたが、この記事で紹介するアルゴリズムが最速だと主張するわけではない（筆者の知らない、もっと早いアルゴリズムが存在するかもしれない）。 続きを読む
圏論の入門書（2018年版）
以前（2014年ごろ）このブログに「圏論の本」という記事を書いたが、あれ以降いろいろな本が出てきたようだ。特に、和書が増えた。
というわけで、この記事では2018年時点で手に入る圏論の本を独断と偏見で紹介する。ここで紹介するのは入門書、和書が中心となり、より専門的な話題に特化した本は省く。
圏論の入門書と一口に言っても、書き方や内容は著者によって様々である。読者にも代数学をやりたい人、プログラミングやロジックをやりたい人、色々いるだろうが、読者のバックグラウンドや興味の方向によって読むべき本は変わる。
読者が適切な本を選択する為に、この記事が（十分なガイドとまではならなくとも）なんらかのヒントを提供できれば幸いである。
適宜、Web上で他の方が書いた書評にリンクを貼る。 続きを読む
アプリカティブ関手ってなに？モノイド圏との関係は？調べてみました！
この記事は Category Theory Advent Calendar 2018 7日目 かつ Haskell (その2) Advent Calendar 2018 7日目の記事です。
Category Theory Advent Calendar 2018の6日目はcorollary2525さんの「随伴は あらゆるところに 現れる」、8日目は空席、9日目はt_uemura669101さんの「トポスと高階論理」です。
Haskell (その2) Advent Calendar 2018の6日目は空席、8日目はtakoeight0821さんの「Type defaultingについての初級的な解説」です。
この記事はどういう記事か
圏論の方から来た人向け：
デカルト積やテンソル積の一般化である「モノイド積」の話と、「内部ホム」の話をします。文献によっては内部ホムはモノイド積の右随伴として導入されますが、ここではモノイド構造を仮定せずに内部ホムの定式化（閉圏）をします。
Haskellの方から来た人向け：
この記事ではHaskellにおけるアプリカティブ関手の使い方は解説しません。Haskellの方から来た読者はすでにアプリカティブ関手をある程度知っており、圏論的な話にﾁｮｯﾄ興味がある、と仮定します。
これを読めば、「モナドは自己関手の圏におけるモノイド対象だよ、何か問題でも？」と同じノリで「アプリカティブ関手はモノイド圏における強laxモノイド関手だよ、何か問題でも？」と言って他人を煙に巻くことができます。 続きを読む
圏論における表記法いろいろ
圏論では図式（可換図式）が多用される。図式を使うメリットは何なのか、他の表記と比べて考えてみたい。 続きを読む
微分の連鎖律と関手性
1件のフィードバック
最近（ここ半世紀くらい）圏論が流行りですね。しかし圏論は抽象的で、具体例や圏論の言葉を使うことによるメリットが見えないと、なかなかとっつき難いかもしれません。
この記事では、高校数学に出てくるアレが、実は圏論の言葉でスッキリ（？）表せることを見てみます。
予備知識：高校数学、若干の圏論、あとは多変数の微分の知識があればなお良い 続きを読む
「週刊 代数的実数を作る」を終えて
すでに数週間経っているが、去年の10月に始めた「週刊 代数的実数を作る」を、一通り書き終えた。 続きを読む
OpenGL の投影行列
OpenGL での 3DCG で使われる投影行列について、自分用にメモっておく。
情報源：
- https://www.khronos.org/opengl/
- https://www.khronos.org/registry/OpenGL/index_gl.php
- OpenGL Core Profile, Compatibility Profile, GLU など
- OpenGL 2.1 Reference Pages
- https://www.khronos.org/registry/OpenGL/index_gl.php
- GLM (OpenGL Mathematics)
「週刊 代数的実数を作る」中間報告
この記事は 数学とコンピュータ Advent Calendar 2017 の14日目の記事です。
以前このブログでも告知しましたが、2ヶ月前から、「週刊 代数的実数を作る」と題して、代数的数の計算機上での実装について Web 上で連載しています：
この記事では、「週刊 代数的実数を作る」でこれまで扱ったトピックを振り返り、これからの方向性を述べます。この記事を読む前に連載に目を通している必要はなく、この記事で概要を把握してから連載の方を読むのでも構いません。
（本当は代数的数の実装を利用して有理関数の部分分数分解と不定積分でもやってやろうと思っていたのですが、現状の実装が遅すぎるので断念しました。） 続きを読む
「週刊 代数的実数を作る」創刊
コンピューター上で実数を取り扱うには、いくつかの方向性がある。普通は浮動小数点数によって近似することが多いと思うが、多倍長計算を始めとする、「コストをかけてでも正確に」計算するという方向性もある。
そのような「正確に取り扱える」実数のクラスとしては、整数（多倍長整数）や有理数はある程度普及していると思う（標準で備えているプログラミング言語がある）。それよりも広いクラスとして、代数的実数、つまり（整数または有理数係数）代数方程式の根となるような実数全体、というものがある。
代数的実数が計算機で取り扱えるということ自体は割と知られた事実だと思うが、実装は割と大変で、工夫の余地がある。有理数のように「GCD さえ実装すればよい」というものではない。
かくいう私も最近までその辺を真面目に勉強しようとは思っていなかったわけだが、何となくモチベーションが湧いてきたので、代数的実数に関するアルゴリズムを勉強しつつまとめたものを記事として Web 公開してみようかと思った次第である。
実装には筆者の好みで、 Haskell を使う。実際のところ、 Haskell による代数的実数の実装は既にあるようだが、まあ気にしない（自身の勉強が主目的なので）。
というわけで、以下のページで公開している：
https://miz-ar.info/math/algebraic-real/
「週刊」と名乗っているが、毎週末に更新することを目指している。果たしていつまで続くかは不明である。 続きを読む