连续数相乘有关问题
连续数相乘问题
求一串连续数相乘的高速算法，可以让实际运算中运算乘法的次数不会超过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
}
求一串连续数相乘的高速算法，可以让实际运算中运算乘法的次数不会超过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
}