AtCoderで青色になった

コメントを残す

7月7日のAtCoder Beginner Contest 133で青色になりました。青色というのは上位7%に相当するらしいです。

「水色に上がった」記事からまだ1ヶ月ちょっとしか経っていないので、新しいHaskellネタも「青色に上がるためにこれを勉強した」みたいなネタもないのですが、適当に自分語りでもしてお茶を濁そうと思います。

続きを読む →

Haskellでの浮動小数点数の方向付き丸めを考える

コメントを残す

「週刊 代数的実数を作る」の #5 で、区間演算と方向付き丸めの話を書いた。浮動小数点数の計算は不正確だと思われがちだが、方向付き丸め等をうまく使えばある種の「正しい結果」（この数は確実に1.0より大きい、等）を得ることができる、という話だ。

MPFRのようなソフトウェア実装の浮動小数点数だと引数で丸めモードを指定できる。しかし、ハードウェア組み込み（注）の浮動小数点数（floatやdouble）の丸めモードを指定する方法は、言語や実行環境に依存する。

（注：環境によってはCPUに浮動小数点演算器が組み込まれておらず、floatやdoubleの演算もソフトウェア実装だったりするが、我々が普段使うPCではfloatやdoubleはほぼ確実にハードウェア実装されているため、以下「ハードウェア実装」で通す）

CやFortranのような低レベルかつ数値計算のニーズがあるようなプログラミング言語だと、丸めモードを変更する手段が用意されているが、JavaScriptやHaskellなど、そういうニーズが薄い言語では丸めモードの変更には対応していないことが多い。せいぜい、「浮動小数点数演算には最近接丸めを使用する」と規定されているのが関の山である。

しかし、「Haskellではできない処理がある」というのはどうにも気にくわない。どうにかして、ハードウェア組み込みの浮動小数点数の方向付き丸めをHaskellで扱う方法を考えたい。

ちなみに、ハードウェア組み込みの浮動小数点数にこだわらないのであれば、MPFRの丸めモード指定を使うHaskellライブラリーがすでに存在する：

http://hackage.haskell.org/package/rounded

続きを読む →

HaskellでAtCoderに参戦して水色になった

コメントを残す

3月下旬からAtCoderのRatedコンテストに参加しています（AtCoderプロフィール）。この度、5月26日のABC128でようやく水色になりました（AtCoder社長の記事によると、これは上位15%に相当するらしいです）。

使用言語はHaskellです。コンテストの時間中に提出したコードは全てHaskellだったと思います。

この記事では、Haskellを使う理由や、Haskellで競技プログラミングをするコツ、AtCoderでHaskellを使う際のアレコレなどを書いていきます。「水色になるための方法」みたいな話はしません（できません）。

続きを読む →

技術書典6の振り返り

コメントを残す

先日の技術書典6では、新刊「LaTeX文書処理自動化ツールClutTeX 使い方とその仕組み」を無事に（ほぼ）完売することができました。現地で手に取ってくださった皆様、（現地またはBOOTHで）購入してくださった皆様、ありがとうございました。

新刊の電子版（PDF版）をBOOTHで販売中です：LaTeX文書処理自動化ツールClutTeX 使い方とその仕組み – だめぽラボ – BOOTH

続きを読む →

技術書典6に、ClutTeX（LaTeX文書処理自動化ツール）の本を出します

コメントを残す

4月14日（日曜日）に池袋で開催される技術同人誌即売会「技術書典6」に、「だめぽラボ」としてサークル参加します。

技術書典6（公式サイト）

サークル詳細 | だめぽラボ | 技術書典 ←気になる方はサークルチェックリストに入れてください

サークル（だめぽラボ）としてのページ：https://lab.miz-ar.info/

日時と場所について

公式サイトより：

日時 2019/04/14 (日) 11:00〜17:00
場所 池袋サンシャインシティ2F 展示ホールD（文化会館ビル2F）
主催 TechBooster/達人出版会
一般参加は11時～13時のみ有料

https://techbookfest.org/event/tbf06

当サークルの配置は か15 です。

頒布物について

筆者が作っているLaTeX処理自動化ツール「ClutTeX」についての本を出します。

利用ガイドの他に、LaTeX処理の自動化に関する知見を詰め込んでいます（第3章）。そのため、単なるマニュアル以上の価値があるかと思います。

この他、既刊「代数的数を作る 根と因数分解のアルゴリズム」のダウンロードカードも販売します（紙の本は販売しません。紙の本は見本として置きます）。なお、既刊は BOOTH でも購入可能です： https://damepo-lab.booth.pm/items/1051034

さらに、新刊または既刊をお買い上げの方に、「だめぽラボステッカー」を配布します！今回の技術書典で購入してくださった方のほか、過去に技術書典またはBOOTHで既刊をお買い上げくださった方も対象です。その際はその旨をお伝えください（感想もあれば嬉しいです）。

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

2件の返信

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

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