最速のフィボナッチ数計算を考える

コメントをどうぞ

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) くらいなのだが、定数倍の部分で高速化する）

なお、記事タイトルには「最速の」と書いたが、この記事で紹介するアルゴリズムが最速だと主張するわけではない（筆者の知らない、もっと早いアルゴリズムが存在するかもしれない）。 続きを読む →

冬キャンと曇り空、ときどき流れ星

コメントをどうぞ

12月の天文現象といえば、中旬に極大を迎えるふたご座流星群だ。見たい。しかし東京では空が明るすぎる。空が暗いところで見たい。

車があれば荷物を載せて好きなところに移動できる（し、車中泊だってできる）が、一人ではコスパが悪い。公共交通機関で移動し、キャンプして星を見よう。

どこに行くか。この時期、内陸部（山梨や長野）は寒そうだ。筆者が冬にキャンプをするのは初めてなので、あまり寒いのは避けたい。太平洋に面した海沿いならまだ暖かいだろうか。東京からほど近くて海沿いで空が暗そう、となると伊豆か房総か。

房総は公共交通機関でのアクセスに便利そうなキャンプ場があまり見つからなかった。一方、伊豆は初めての冬キャンプにはちょっと遠いような気がした。

では、箱根はどうか。調べてみると、湖のそばに良さそうなキャンプ場があるようだ：芦ノ湖キャンプ村

芦ノ湖キャンプ村は、オフシーズンの平日はテントサイト1泊1000円とリーズナブルで、また、この時期は利用客が少ないので予約なしでも大丈夫そうだ。

星を見ることに関しては、小田原や沼津の市街地にやや近い（光害があるかも）ことが不安要素だが、そこそこの星空は期待できるだろう。 続きを読む →

圏論の入門書（2018年版）

1件のフィードバック

以前（2014年ごろ）このブログに「圏論の本」という記事を書いたが、あれ以降いろいろな本が出てきたようだ。特に、和書が増えた。

というわけで、この記事では2018年時点で手に入る圏論の本を独断と偏見で紹介する。ここで紹介するのは入門書、和書が中心となり、より専門的な話題に特化した本は省く。

圏論の入門書と一口に言っても、書き方や内容は著者によって様々である。読者にも代数学をやりたい人、プログラミングやロジックをやりたい人、色々いるだろうが、読者のバックグラウンドや興味の方向によって読むべき本は変わる。

読者が適切な本を選択する為に、この記事が（十分なガイドとまではならなくとも）なんらかのヒントを提供できれば幸いである。

適宜、Web上で他の方が書いた書評にリンクを貼る。 続きを読む →

LuaLaTeXでダウンロードカードを作った話

2件の返信

この記事は、TeX & LaTeX Advent Calendar 2018 の 15日目の記事です（遅くなってすみません）。

技術書典5で電子版を配布するのに利用したダウンロードカード（電子書籍をダウンロードするためのURLとシリアルコードが記載された紙）の話をします。技術書典の原稿執筆でやったことの全体像については、 同人誌「代数的数を作る」ができるまで／PandocとかLaTeXの話 を参照してください。 続きを読む →

アプリカティブ関手ってなに？モノイド圏との関係は？調べてみました！

1件のフィードバック

この記事は 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モノイド関手だよ、何か問題でも？」と言って他人を煙に巻くことができます。 続きを読む →

LaTeX処理自動化ツール ClutTeX をリリースした

1件のフィードバック

2年ほど前からマイペースで作っていたLaTeX処理自動化ツールClutTeXだが、ある程度の機能が整ったと判断し、バージョン0.1をリリースした。ClutTeXに関しては2年前にもブログ記事で紹介したが、初のリリースを迎えた今、改めてその機能と使い方を紹介する。 続きを読む →

技術書典5に初サークル参加した記録／当日

コメントをどうぞ

技術書典5の当日編。

前日までの話はこっち：技術書典5に初サークル参加した記録／前日まで

原稿の内容・技術面に関してはこっち：同人誌「代数的数を作る」ができるまで／PandocとかLaTeXの話

当日会場に来れなかったという方は、BOOTHで電子版（PDF版）を購入可能です：

代数的数を作る 多項式の根と因数分解のアルゴリズム – だめぽラボ – BOOTH（同人誌通販・ダウンロード）

続きを読む →