连续数相乘问题
求一串连续数相乘的高速算法，可以让实际运算中运算乘法的次数不会超过20次，而运算结果的值最大可以去到9.999999999 * 10^99 。
另外，最好是比较适合硬件运算的算法，因为我是用底层汇编做的；这一串数都是正整数；求这个算法的目的是求 初中数学中的 排列组合中的 P和C的值。
[解决办法]
“乘法的次数”概念比较含糊，两个大整数相乘算几次？
连续数相乘，比较好的是逐步分段相乘，尽量使相乘的两数位数相近，从而可充分利用一些高级算法。
[解决办法]
用float或者double
[解决办法]
如果不要求精确，用浮点数据类型即可。如果要求精确，就需要大整数相关算法了，
大整数乘法的高级算法基本上基于分段相乘，比如：Karatsuba、Toom3 及至 卷积算法，通过一些数学技巧努力降低乘法指令的次数（但可能同时会增加加减指令的次数），
至于采用哪种算法，完全视计算的规模而定。
[解决办法]
由于受底层空间限制，最终的精确结果不可能很大，这些大数运算算法并不适用。
具体问题具体分析，你只要将两个大整数用小学生的计算法则写出来，并充分优化即可。
关于排列和组合，可以先将结果进行质因数分解，这样可以充分利用平方快速计算，
当然，某些情形下这样反而会慢些。
[解决办法]
mark
[解决办法]
mark
[解决办法]
mark
[解决办法]
这是数学问题，不是编程问题。
什么叫连续数相乘？ 是不是等差数列相乘？
[解决办法]
给你表述一下：
f(x) = x*(x+1)*(x+2)*......*(x+n)
(其中，x大于2的64次方，n也大于2的64次方)
要怎么算？
恐怕是麻烦了。
首先，计算机内置的数值类型都不能表示上面的任何一个值。就算表示成字符串，几个屏幕都显示不下，哈哈。
[解决办法]
san_77227487() ( ) 信誉：100 Blog 加为好友 2007-6-21 22:16:01 得分: 0
看来大家都比较关心数据的存放问题。其实这个问题不需要考虑的，因为我是在单片机上用汇编做，再大的数也是用12个字节加一个指数字节表示，根本不需要什么数据类型。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
那你的结果是需要得到这样的形势：m*(2^n) ？
12个字节加一个指数字节并不能精确的表示结果，只能是近似表示。
[解决办法]
mark
[解决办法]
用double做乘法就可以啦,很快的.
[解决办法]
既然不是要精确值, 用公式计算就可以了吧, 象这样计算阶乘, 在 N 较大的时候精度非常高的, lg( N! / F(N) ) < 1 / (360*N^3) , 应该足够了 :
#include <math.h>
#include <float.h>
#include <stdio.h>
#define C2divLg2PI (0.3990899341790575247825) /* lg(2*PI)/2 */
#define CLgE (0.4342944819032518276511) /* lg(E) */
void fact( unsigned _N )
{
double _E , _M; /* result = _M * 10^_E */
double _LgR = C2divLg2PI + log10( (double)_N ) / 2 + _N * ( log10( (double)_N ) - CLgE ) + CLgE * ( 1./12/_N - 1./360/_N/_N/_N ) ;
_M = modf( _LgR , &_E );
_M = pow( 10. , _M );
printf( "%u! ~= %.10lf * 10 ^ %.0lf\n " , _N , _M , _E );
}
int main()
{
_control87( PC_64 , MCW_PC );
fact( 10000 );
return 0;
}
[解决办法]
以下算法给楼主参考
大数阶乘巧算法：
(Java)
public static void main(String[] args) {
static int[] data = new int[100];
int num = 0; // 占用的个数
data[0] = 1; // 0和1的阶乘是1
for (int i = 2; i < 257; i++) {
for (int j = 0; j < num + 1; j++) {
data[j] *= i; // 对每个int中的数都乘上 i
}
for (int j = 0; j < num + 1; j++) {
if (data[j] > 1000000) {
for (int k = j; k < num + 1; k++) {
if (data[num] > 1000000) num++;
data[k+1] += data[k]/1000000; // 进位
data[k] %= 1000000; // 进位后的余数
}
}
}
}
System.out.println( "占用的int数： " + (num+1) + "\n值： ");
System.out.print(data[num]);
for (int i = num-1; i > -1; i--) {
System.out.print(new java.text.DecimalFormat( "000000 ").format(data[i]));
}
}
}
===========================
(JavaScript)
function jc(N) {
var data = new Array(100);
var num = 0; // 占用的个数
data[0] = 1; // 0和1的阶乘是1
for(var i=1;i <data.length;i++){
data[i]=0;
}
for (var i = 2; i <= N; i++) {
for (var j = 0; j < num + 1; j++) {
data[j] *= i; // 对每个int中的数都乘上 i
}
for (var j = 0; j < num + 1; j++) {
if (data[j] > 1000000) {
for (var k = j; k < num + 1; k++) {
if (data[num] > 1000000) num++;
data[k+1] += Math.floor(data[k]/1000000); // 进位
data[k] %= 1000000; // 进位后的余数
}
}
}
}
T1.value=( "计算 " + N + "的阶乘\n ");
T1.value+=( "占用的int数： " + (num+1) + "\n值：\n ");
T1.value+=(data[num]);
for (var i = num-1; i > -1; i--) {
T1.value+=((1000000+data[i]).toString().substr(1));
}
}
===========================
(JavaScript)
function multiN(n) //连乘n!
{
var r = [1];
for(var i = 2; i <= n; i++)
{
for(var j = 0, c = 0; j < r.length || c != 0; j++)
{
var v = j < r.length ? r[j] * i + c : c;
r[j] = v % 10000000000;
c = (v - r[j]) / 10000000000;
}
}
for(var i = 0; i < r.length - 1; i++)
{
if(r[i] < 10) {r[i] = '000000000 ' + r[i]; continue;}
if(r[i] < 100) {r[i] = '00000000 ' + r[i]; continue;}
if(r[i] < 1000) {r[i] = '0000000 ' + r[i]; continue;}
if(r[i] < 10000) {r[i] = '000000 ' + r[i]; continue;}
if(r[i] < 100000) {r[i] = '00000 ' + r[i]; continue;}
if(r[i] < 1000000) {r[i] = '0000 ' + r[i]; continue;}
if(r[i] < 10000000) {r[i] = '000 ' + r[i]; continue;}
if(r[i] < 100000000) {r[i] = '00 ' + r[i]; continue;}
if(r[i] < 1000000000) {r[i] = '0 ' + r[i]; continue;}
}
//document.writeln(r.length+ ': ');
//document.writeln(r.join( ', '));
return r.reverse().join( " ");
}
[解决办法]
偶觉得这东西近似计算就可以了, 用 lg( N! ) ~= lg(2*PI)/2 + N * lg N - N * lg E + lg N / 2 + lg E * ( (12*N)^-1 - (360*N^3)^-1 ) 计算对 N 大于 100 的数可以有12位的精度, 如果你觉得精度还不够, 还可以找个更加精确的公式, 这个公式貌似有 Stirling 级数展开100项左右的精度 ... 对 N 小于100的用个平凡的算法就可以了 ...
这样子问题就简单了, 写个高精度(30来个10进制位)的浮点算法库就可以了 ...
[解决办法]
楼主的问题应如下分析：
1、要精确的，还是不精确的？
2、以二进制输出，还是以十进制输出？
3、计算规模有多大？
从回复看，对于问题1楼主似乎偏向于要精确的，问题2尚不得知。
由于最终乘积结果仅100位左右，所以用普通小学生多位数的乘法算法即可，
而这用汇编非常容易实现；如果是以二进制输出，甚至可避免耗时的除法指令。
由于全过程仅用整型汇编指令，速度非常快，甚至比不精确的浮点算法更快！
Stirling 公式在计算入参较大时很快，精度也比较好，
但对于较小的入数，精度会比较差，且由于需调用复杂函数速度反而会落后。
[解决办法]
晕, lz 明明表示数据是 12字节+指数, 怎么可能是求精确值 ...
看 lz 动辄开几十上百K 字节的 buffer , 看来内存也不是很紧张, 稍微有个1,2K的ROM空间, 查查表啥的, 用公式计算基本就是常数时间 ...
