OCamlで車輪を再発明する - fetburner.core最近研究でCoqぐらいしか書いてないので、リハビリがてらAtCoderで 開かれるコンテストにOCamlで参加して遊んでます。 僕は個人的な趣味もあってOCamlを使う際は専ら言語処理系を書いていましたが、 競技プログラミングでは全く関係ない題材を扱う必要があるので新鮮な感じですね。 それに伴って有名なアルゴリズムもいくつか実装したので、 ここではそういうアルゴリズムをMLではどう書いたのか紹介したいなと思います。 高速なべき乗のアルゴリズム 正式名称はよく分からないのですが、ありますよね？O(log n)でべき乗を計算するアルゴリズム。 x ^ nを計算する時、nが偶数の時は(x * x) ^ (n / 2)とみなすやつです。 OCamlで素朴に実装するとこんな感じ。 let rec power m = function | 0 -> 1. | n when n mod 2 = 0 ->
