オーバーフローしにくい組み合わせの数の計算方法

October 17, 2013 at 09:13 PM | categories: algorithms, programming |

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;
}

結果の値が範囲内ならオーバーフローしないのか、というとそういうわけではないけどナイーブな実装に比べるとずっと計算できる範囲が広いので、値のレンジがあらかじめわかっているのであればこれで十分ですね。

[フレーム]
View the discussion thread. blog comments powered by Disqus

About Me

pic
mojavy

Recent posts



Categories

Badges


AltStyle によって変換されたページ (->オリジナル) /