Cで組み合わせの数を計算するときに定義通り計算するとすぐにオーバーフローしてしまう。
例えば以下のような実装だと、
程度でも結果がおかしくなってしまう。
#include <iostream> using namespace std; uint64_t fac(uint64_t n) { if (n > 1) return n * fac(n-1); else return 1; } uint64_t combinations(uint64_t n, uint64_t k) { return fac(n) / (fac(k) * fac(n-k)); } int main(int argc, char *argv[]) { cout << combinations(5, 3) << endl; // => 10 cout << combinations(10, 5) << endl; // => 252 cout << combinations(20, 10) << endl; // => 184756 cout << combinations(30, 15) << endl; // => 0 !? return 0; }
とりあえず素因数分解してやれば解決するのでいままでそうしてたのだけど、もっとかっこいい方法がないものかと思って探してみたらKnuth先生の本で以下のようなアルゴリズムが紹介されているらしい。1 これはかっこいい。
uint64_t combinations2(uint64_t n, uint64_t k) { uint64_t r = 1; for (uint64_t d = 1; d <= k; ++d) { r *= n--; r /= d; } return r; } int main(int argc, char *argv[]) { cout << combinations2(30, 15) << endl; // => 155117520 cout << combinations2(60, 30) << endl; // => 118264581564861424 cout << combinations2(64, 32) << endl; // これはオーバーフローする return 0; }
結果の値が範囲内ならオーバーフローしないのか、というとそういうわけではないけどナイーブな実装に比べるとずっと計算できる範囲が広いので、値のレンジがあらかじめわかっているのであればこれで十分ですね。
]]>
先週くらいに読んだWEB+DB PRESS Vol.42 に載っていたFront Coding という圧縮アルゴリズムを実装してみました。
http://d.hatena.ne.jp/naoya/20080914/1221382329 のパクりです。
ソースはhttps://github.com/taksatou/cl-frontcodingです。
学習目的でつくったので実用的なライブラリではないですが、CLOSやマクロを使いつつパッケージ作成〜テストまで一通りやりました。
CLOSもマクロも基本的な使い方をするだけなら意外と簡単でした。
CLOSとかマクロは本を読んでもいまいちよくわからない上に、深淵なイメージが膨らんで心理的ハードルがあがってしまうだけなので、よくわからないなりになにか作ってみると理解が進んでいいと思います。
]]>