重复排列:避免溢出
背景:
鉴于n
球,使得:
'a' balls are of colour GREEN 'b' balls are of colour BLUE 'c' balls are of colour RED ...
(当然a + b + c + ... = n
)
可以安排这些球的排列数量由下式给出:
perm = n! / (a! b! c! ..)
问题1:我如何“优雅地”计算perm
以尽可能避免整数溢出,并确保当我完成计算时,我要么具有正确的perm
值,要么我知道最终结果会溢出吗?
基本上,我想避免使用像GNU GMP这样的东西。
可选地,问题2:这是一个非常糟糕的主意,我应该继续使用GMP吗?
如果你有cpu时间的全局,你可以从所有阶乘中列出列表,然后找到列表中所有数字的素数因子化,然后取消顶部的所有数字与底部的数字,直到数字完全降低。
这些被称为多项式系数,我将用m(a,b,...)
。
并且您可以通过利用此身份(这应该相当简单地certificate)来有效地计算它们以避免溢出:
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
然后,使用递归来计算系数是一件简单的事情。 请注意,为避免指数运行时间,您需要缓存结果(以避免重新计算)或使用动态编程。
要检查溢出,只需确保总和不会溢出。
是的,使用任意精度库来完成这个简单的任务是一个非常糟糕的主意。
溢出最安全的方式是戴夫建议的方式。 你找到素数p
除以n!
的指数n!
通过总和
m = n; e = 0; do{ m /= p; e += m; }while(m > 0);
在a的因子中减去p
的指数a!
对所有素数<= n
,并且您具有多项式系数的因子分解。 当且仅当最终结果溢出时,该计算才会溢出。 但是多项式系数增长得相当快,因此对于相当小的n
,你已经有溢出。 对于大量计算,您将需要一个bignum库(如果您不需要精确的结果,则可以使用double
s获得更长的时间)。
即使您使用bignum库,也值得保持中间结果不会过大,因此不要计算因子并划分大数,最好按顺序计算零件,
n!/(a! * b! * c! * ...) = n! / (a! * (na)!) * (na)! / (b! * (nab)!) * ...
并计算这些因素中的每一个,让我们以第二个为例进行说明,
(na)! / (b! * (nab)!) = \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
乘法,保持中间结果适度小。
根据此链接 ,您可以将多项式系数计算为几个二项式系数的乘积,从而控制整数溢出。
这将原始问题减少到二项式系数的溢出控制计算。
符号: n! = prod(1,n)
n! = prod(1,n)
你可能猜到了什么。
这很容易,但首先你必须知道,对于任何2个正整数(i, n > 0)
,表达式是一个正整数:
prod(i,i+n-1)/prod(1,n)
因此,想法是切片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
这样每个分区都会产生一个整数。