順列：回避オーバーフロー

Question

背景：これらのボールを配置することが可能な順列の数が与えられる（もちろんa + b + c + ... = nの）

'a' balls are of colour GREEN 
'b' balls are of colour BLUE 
'c' balls are of colour RED 
... 

：

このようなことnボールを考えますby：

perm = n!/(a! b! c! ..) 

質問1： は、どのように私は限りできるだけ整数オーバーフローを避けるため、と私は計算行っていたとき、私はどちらかがpermの正しい値を持っているか、私はそのを知ってことを確認するようにpermを計算「エレガント」することができます最終結果はオーバーフローしますか？

基本的に、私はGNU GMPのようなものを使用しないでください。

質問2： これはで、実際はという悪い考えです.GMPを使用するだけですか？

Answer 1

CPU時間のグロブがある場合は、すべての階乗からリストを作成し、リスト内のすべての数値の素因数分解を見つけて、上のすべての数値を最下部の数値と一緒にキャンセルします。数字は完全に減少します。

Answer 2

これらは、多項係数と呼ばれ、m(a,b,...)で表されます。

そして、あなたが効率的に（証明するかなり簡単であるべきである）、このアイデンティティを活用することによって、オーバーフローを避け、それらを計算することができます。

m(a,b,c,...) = m(a-1,b,c,...) + m(a,b-1,c,...) + m(a,b,c-1,...) + ... 
m(0,0,0,...) = 1 // base case 
m(anything negative) = 0 // base case 2 

そして、それは係数を計算する再帰を使用しての簡単な問題です。指数的な実行時間を避けるためには、（再計算を避けるために）結果をキャッシュするか、動的プログラミングを使用する必要があります。

オーバーフローをチェックするには、合計がオーバーフローしないようにしてください。

はい、この単純な作業を行うために任意の精度ライブラリを使用することは非常に悪い考えです。

Answer 3

オーバーフローで最も安全な方法は、Daveの提案です。あなたはプライムpがすべての素数<= n用などa!ことを行いますのfactorisationsにpの指数を引き合計

m = n; 
e = 0; 
do{ 
    m /= p; 
    e += m; 
}while(m > 0); 

でn!を分割すると指数を見つけ、そしてあなたは、多項係数の因数分解を持っています。この計算は、最終結果がオーバーフローした場合にのみオーバーフローします。しかし、多項式係数はかなり速くなります。したがって、かなり小さくてもオーバーフローすることになりますn。実質的な計算には、bignumライブラリが必要です（正確な結果が必要ない場合は、doubleを使用して少し長くすることができます）。

あなたがBIGNUMライブラリを使用する場合でも、大きくなりすぎから中間結果を維持するために価値があるので、代わりに階乗を計算し、膨大な数の分割、順序で部品を計算した方がよい、

n!/(a! * b! * c! * ...) = n!/(a! * (n-a)!) * (n-a)!/(b! * (n-a-b)!) * ... 

とのは、説明のために第二てみましょう、これらの要因の各々を計算する、

(n-a)!/(b! * (n-a-b)!) = \prod_{i = 1}^b (n-a+1-i)/i 

は

prod = 1 
for i = 1 to b 
    prod = prod * (n-a+1-i) 
    prod = prod/i 

で計算され

最後に、部品を掛けます。これには、nの除算とn + number_of_parts - 1の乗算が必要であり、中間結果を適度に小さく保ちます。

Answer 4

this linkによれば、途中で整数オーバーフローを制御する複数の2項係数の積として多項係数を計算できます。

これにより、元の問題が、2項係数のオーバーフロー制御された計算に還元されます。

Answer 5

表記：n! = prod(1,n)ここで、あなたは何を推測するかもしれません。

それは非常に簡単ですが、最初に使用すると、式は正の整数であることを任意の2つの正の整数(i, n > 0)のためにことを知っている必要があります。

prod(i,i+n-1)/prod(1,n) 

このような考え方は、小さな塊にして分割するn!の計算をスライスすることですできるだけ速くに。

aの場合はbなどとなります。

perm = (a!/a!) * (prod(a+1, a+b)/b!) * ... * (prod(a+b+c+...y+1,n)/z!) 

、その要因のどちらもが行いますpermがオーバーフローしませんので、もしこれらの要因のそれぞれは、整数です。

けれども、そのような要因の計算に分子や分母にオーバーフローすることができますが、それはその後、オルタナンスで割り算を分子内の乗算をやって回避です：

prod(a+1, a+b)/b! = (a+1)(a+2)/2*(a+3)/3*..*(a+b)/b 

そのようにして、すべての部門が得られます整数。