我用字符串相加的办法,计算3000的阶乘。
先做加法,比如"111"和"222"相加,得到"333",先让个位相加,满10进1,然后算十位,百位...
再在加法的基础上做乘法,所谓乘法,即若干个数相加
最后在乘法的基础上做3000的阶乘.
我昨完CPU工作了4个小时,才算出这个结果。
请问有更好的办法吗?
最好在数秒钟之内
先做加法,比如"111"和"222"相加,得到"333",先让个位相加,满10进1,然后算十位,百位...
再在加法的基础上做乘法,所谓乘法,即若干个数相加
最后在乘法的基础上做3000的阶乘.
我昨完CPU工作了4个小时,才算出这个结果。
请问有更好的办法吗?
最好在数秒钟之内
尽可能将乘法转化为乘方;
尽可能地优先调用平方; 言归正转,下面以精确计算 1000! 为例,阐述该算法: 记 F1(n) = n*(n-1)*...*1;
F2(n) = n*(n-2)*...*(2 or 1);
Pow2(r) = 2^r;
有 F1(2k+1) = F2(2k+1) * F2(2k)
= Pow2(k) * F2(2k+1) * F1(k),
F1(2k) = Pow2(k) * F2(2k-1) * F1(k),
及 Pow2(u) * Pow2(v) = Pow2(u+v), ∴ 1000! = F1(1000)
= Pow2(500)*F2(999)*F1(500)
= Pow2(750)*F2(999)*F2(499)*F1(250)
= Pow2(875)*F2(999)*F2(499)*F2(249)*F1(125)
= Pow2(937)*F2(999)*F2(499)*F2(249)*F2(125)*F1(62)
= Pow2(968)*F2(999)*F2(499)*F2(249)*F2(125)*F2(61)*F1(31)
= Pow2(983)*F2(999)*F2(499)*F2(249)*F2(125)*F2(61)*F2(31)*F1(15)
= ... 如果你预存了某些小整数阶乘(比如这里的“F1(15)”),则可提前终止分解,否则直至右边最后一项为“F1(1)”为止;这样,我们将阶乘转化为2的整数次幂与一些连续奇数的积(或再乘以一个小整数的阶乘); 再定义:F2(e,f) = e*(e-2)*...*(f+2),这里仍用“F2”,就当是“函数重载”好了:),
则 F2(e) = F2(e,-1) = F2(e,f)*F2(f,-1) (e、f为奇数,0≤f≤e) ∴ F2(999) = F2(999,499)*F2(499,249)*F2(249,125)*F2(125,61)*F2(61,31)*F2(31),
F2(499) = ____________F2(499,249)*F2(249,125)*F2(125,61)*F2(61,31)*F2(31),
F2(249) = ________________________F2(249,125)*F2(125,61)*F2(61,31)*F2(31),
F2(125) = ____________________________________F2(125,61)*F2(61,31)*F2(31),
F2( 61) = _______________________________________________F2(61,31)*F2(31),
F2( 31) = _________________________________________________________F2(31),
∴ F1(1000) = Pow2(983) * F2(999,499) \
* [F2(499,249)^2] * [F2(249,125)^3] \
* [F2(61,31)^4] * [F2(31)^5]
这样,我们又将阶乘转化为了乘方运算。 上式实际上是个形如 a * b^2 * c^3 * d^4 * e^5 的式子;我们再将指数转化为二进制,可得到如下公式:
a * b^2 * c^3 * d^4 * e^5 = (a*c*e)*[(b*c)^2]*[(d*e)^4]
= (((e*d)^2)*(c*b))^2*(e*c*a),
即可转化成了可充分利用高效的平方算法。
最后,我再提供大家一个确保“小整数累乘不溢出”的技巧,这是我自创的,相信会对大家有借鉴作用:
应采用“倒序”,比方说,应按 999 * 997 * ... 的顺序;
可预先设定一个数组,记录如果当前起始数组的最大值不大于某个值,则连乘多少个数不会溢出;
可利用“几何平均值≤算术平均值”定理,可推导出“ k 个自然数连乘不大于某个定值,其充分条件是其和不大于某个临界值”,我们只需要事先计算出它们的对应关系并保存下来。 上述算法是 HugeCalc Ver1.2.0.1 的算法关键点,其效率已略高于liangbch(宝宝)的高级算法3.0版。 在最新的 HugeCalc Ver2.1.0.1 中,采用的是更彻底的分解成质因数的方法,技巧性倒反不如上面的强(但却需要有高效的素数筛法),但里面的很多思想仍在延续。
--------------------------------------------------------------------------------备注: Factorial.exe
Ver2.1.0.1 Celeron(tm) 466MHz
64MB RAM, Win98Sec Pentium(R) 4 1.70GHz
256MB RAM, WinXP Result
10,000! 0.069s 0.031s 2.8462... x 10^35,659
20,000! 0.236s 0.109s 1.8192... x 10^77,337
40,000! 0.795s 0.390s 2.0916... x 10^166,713
80,000! 2.661s 1.328s 3.0977... x 10^357,506
100,000! 4.177s 1.969s 2.8242... x 10^456,573
200,000! 13.663s 6.438s 1.4202... x 10^973,350
400,000! 43.818s 20.828s 2.5344... x 10^2,067,109
800,000! 139.337s 66.921s 5.6846... x 10^4,375,039