22:56 10/09/04 階乗を求める 去年聞いた中で、私が一番感動した式の話。 k!　=　limn→∞ nk / nCk kの階乗は、「nのk乗 ÷ n個のものからk個選ぶ組み合わせの数」という式で n を無限に大きくしていったときの収束先、である。 特に難しい証明が要るとかではなくて、nCk = n(n-1)(n-2)...(n-k+1) / k! であることを使うと、 limn→∞ nk / nCk = limn→∞ nk k! / n(n-1)(n-2)...(n-k+1) で、n が k に比べて十分大きければ n も n-k+1 もほとんど同じ値なので、 分子も分母もだいたい n を k 個かけているわけでして、 その部分が相殺して、k! が残るという寸法。 （厳密な表現ではないので、気になる人は厳密に証明してください。） 実装 と、この式自体はそんなに不思議ではないのです

10:01 10/07/20 それでも２倍だ 先日のvectorの伸長度合いの記事に関して 本当に1.5倍のほうがメモリ効率がよいのか という反応をいただきました。とても興味深い。みんな読みましょう。 自分の理解メモ： 「再利用ができるから嬉しい」等の議論をするなら、 今までに確保したメモリ (1 + r^1 + ... + r^k) のうち、 有効に使えてるメモリ r^{k-1} (バッファ拡大直後) や r^k (次のバッファ拡大直前) の割合で評価してみようじゃないかという。 まず簡単のために再利用をしない場合を考えると、この割合はそれぞれ (r-1)/r^2、 (r-1)/r になります（途中計算略）。 この利用率が最悪になる瞬間 (r-1)/r^2 を最善にしよう、 という一つの指標で考えてみると、式を微分なりなんなりしてみると r = 2 で最大(25%)となることがわかります

21:54 10/06/30 行列と項書換 "Termination of String Rewriting with Matrix Interpretations" という論文を読みました。 これは何かというとつまり、 ICFPコンテストの元ネタとして 紹介 されていた論文です。 れ い 年、 冗談９割で、主催者の専門分野にちなんだ問題が出るに違いない！と叫んでいるのですが、 本当に来るとは思わなかった…。 さて。項書き換え (term rewriting) と呼ばれる研究分野がありまして、 例えばこんな問題を調べています。 文字列に対して、「以下の操作のどれかを好きに選ぶ ＆ 実行する」を繰り返します。 abc という部分文字列を de に書き換える （abc ⇒ de と書きます） ef ⇒ g fgh ⇒ ij どんな文字列からスタートしても、最後には、どの規則も使えない状態 （つ

21:07 09/03/26 zipWithN twitterでいけがみさんが張ってらした論文が面白かったです。 map f [a1, a2, ..., an] ==> [f a1, ..., f an] zipWith f [a1, ..., an] [b1, ..., bn] ==> [f a1 b1, ..., f an bn] zipWith3 f [a1, ..., an] [b1, ..., bn] [c1, ..., cn] ==> [f a1 b1 c1, ..., f an bn cn] ... zipWith7 f [a1, ..., an] [b1, ..., bn] ... [g1, ..., gn] ==> [f a1 b1 … g1, ..., f an bn … gn] Haskell98 の標準ライブラリの関数ですけど、 １引数関数 f と１つのリスト as

13:33 08/06/29 RSS of kmonos/wlog moved! http://www.kmonos.net/wlog/index.rdf いや、移動したのは15ヶ月前なので、すでにご存じの方は華麗にスルーしてください。 「ここのRSSが文字化けしてるよー」という方だけ、↑に登録変更していただけると、 直るかと思います。お手数おかけしてスミマセン。定期的に「文字化けってる」という 指摘を見かけるので再度ブロードキャストです。こう、辛辣な評議会とかで怒られそうですけど、 諸般の事情により古い方からリダイレクトかけるの難しいらしいのだよね… それはそうと、昨日の記事に追記しました。 10:26 08/06/28 Logic ∩ CS 検索してたらたまたまヒットした "On the Unusual Effectiveness of Logic in Computer Scienc

00:18 05/11/26 経県値 母上からの指摘で秋田県が赤くなりました。修正。 山形と茨城もこれでよかったか微妙に自信なし。 （追記：茨城も赤いことが判明。） 木和 私の Tree Summing のコードが見たい人は、このページのソース内コメント 読んで下さい。「もっと読む」機能とか実装するの面倒なので手抜きばんざい。 あーでも、自分で解いてみて、できれば２日くらい悩んでみた人じゃないと 読んでも全然面白くないと思いますよん。 Ｃ言語の言語仕様の隅を突いてコードを短くする技能ってのは完璧に趣味の領域に 属すると思いますが、それとは別の「短く簡潔に書けるアルゴリズムを考える」能力の 方は、普段からわりと重要なのではないかという気もします。単純な話、コードの量が 少ないほど、バグの元も少ないわけで。例えば今回の問題を解くためだけに、自分 でTreeクラスを定義してそれを生成するpars