关于大数阶乘 （相乘） 高手指点

来源：百度知道 编辑：UC知道 时间：2024/05/26 20:15:19
关于大数阶乘（相乘）的一点想法，希望高手能指点一下

我想这样来实现大数的相乘
算法简单讲就是乘法的笔算原则
因为m位的被乘数与n位的乘数相乘
他们的积不会超过（m+n）位（以证明的）
当然就可以用一个他们所占内存长度的内存来存储他们的积

算法过程就是移位相加的过程
数据在内存中以二进制表示每一位非零即一
所以当所在位为一时
就被乘数左移到它所在的位（与他对齐）
然后与以前所以位相乘的结果相加
就得到了乘积的结果

1111
× 1111
——————
1111
11110
111100
1111000
------------

算法过程就是将上述加法过程分解而已

算法的c代码我还没有实现
因为当用long型的时候会存在高低位交叉的问题
用int型的算法现在也没改好

想请高手来说说
算法的可行性和速度会怎么样？
菜鸟在此先谢过各位捧场的了！
下面的例子里由于由于格式有问题，大家自己理解一下。。。

我刚把程序调出来了,没通过计时我就发现了当数值比较大的时候,运算起来非常慢了.程序发出来,大家说的都很有道理的,我是个新手,太菜了点,至于采纳谁的为答案,我真得不知道怎么辨别好,这样吧,我就再请大家帮个忙,大家给我编程的缺点说一下,谁说的多又好,我给谁,好不好?下面198601020304就是我的程序.

基本不可行
怎么输出结果
直接用数组，数组的每个元素表示一位

这个问题我也考虑过。二进制的运算没什么问题，难点在于输入、输出。把一个十进制的大数转换为二进制的很麻烦（因为长度太大，用短除法的时候还要模拟竖式除法）；把二进制转换为十进制的话更麻烦，我至今没想到好的方法。

我劝你用数组，10000进制，模拟竖式。

//看看这个程序吧，我以前写的，主要方向就是用数组来模拟，一开始用数组每个元素来表示一位，但是可以优化成每个元素表示4位，这样更快更省空间，现在这个版本是double数组，每个元素表示11位，50000阶乘都没有问题，算大的只是时间长一点。每次乘的时候不是乘数组的每一位，而是定位一个实际有效的区间，这样更优化
#include<stdio.h>
#include<math.h>
#include<time.h>
#include<conio.h>
#define LEN 44000
#define DEP 11
double ans[LEN]={1};
void main()
{
int i,j,n,r,l;
long c1,c2;
double m,h=0,z=0,k=pow(10,DEP);
printf("\t阶乘运算 v1.1 by CityHunter\t2006-09\n");
printf("\n请输入n: ");
scanf("%d",&n);
printf("完成\t\t");
c1=clock();
for(i=2;i<=n;i++)
{
for(l=i;l>0&&l%5==0;l/=5)
z+=1.0/DEP;
h+=log10(i)/DEP;
if(z>1)
r=z-1;
els