このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

ゼロを早く見つけると計算がどえらく楽

2,3日前に、Catyのスキーマ処理系がスタックを使い尽くす現象が起きました。僕はバグかと思っていたのですが、そうではなくてホントにスタックが足りないのでした。バグでないとは言え、計算資源を使い過ぎるという問題があるので、これはKuwataさんが修正(改善)しました。

修正の方針は無駄な計算をしない、ということですが、より具体的には「ゼロをなるべく早期に検出する」ことです。

これで思い出したのは、次男がゼロを習ったばかりの頃、次のようなことがありました。

次男:「おとうさん、暗算して」
父親:「いいよ」
次男:「7 たす9 かける3 かける11 ……」

いいかげんこちらが追いつけなくなってウガーッとなった頃に小さい声で

次男:「かける0 たす1 ではいくつだ?」

実は僕(父親)は「かける0」を聞き逃してなかったのですが、次男の策略を知らんことにして「わからーん」「答は1だよー」と。

掛け算の因子にゼロが含まれることが分かれば、その掛け算を律儀にする必要はなく、すぐさま答がわかります。足し算でもゼロは無視できるので計算が簡単になります。この当たり前な事実が、計算量を劇的に減らすこともあります。

バカみたいに当たり前の計算法則が、無駄な計算を排除するために役に立つことがあります。ゼロの法則は典型的ですが、別な例として an×m = (an)m という指数法則; a4 = a×a×a×a という4回3回の掛け算を b = a×a; result = b×b という2回の掛け算に減らしてくれます。掛け算のコストなんてたいしたことない? aが巨大な行列だったらどうですか、掛け算がとてもコストリーかも。