Board logo

标题: 一个高精度乘法的程序 [打印本页]
作者: x86    时间: 2005-9-28 23:51     标题: 一个高精度乘法的程序

#include #include #include #define SIZE 65535 void main(void) {char a[SIZE]; char b[SIZE]; int al, bl; int i, j, k=0; int af=0; int fench; int temp1, temp2, end1; int all, yu; //分别保存2数的乘积和mod10的结果 char filename[20]="in.txt"; FILE *fpin,*fpout; fpout=fopen("result.txt","wb"); char c=0; char input; memset(a,0,SIZE); memset(b,0,SIZE); if((fpin=fopen(filename,"rb"))==NULL) { printf("open file %s failed!\n",filename); exit(0); } i=0; j=0; while(input=fgetc(fpin),!feof(fpin))//从文件读取运算的数字 {scanf:if(input==32||input==10||input==13) {input=fgetc(fpin); af=1; goto scanf; } if(af==0) {a=input; i++; } else {b[j]=input; j++; } } al=strlen(a); bl=strlen(b); all=al+bl; printf("数据读入完成! 数a的长度: %d , 数b的长度: %d .\n",al,bl); char* result=(char*)malloc(all); memset(result,48,all); printf("result malloc ok!\n"); printf("\n计算中..."); fench=0; for(i=bl-1;i>=0;i--) { temp1=b-48; for(j=al-1;j>=0;j--) { temp2=a[j]-48; end1=temp1*temp2+k+(result[all-al+j-fench]-48);//计算2个数的乘积并加上进位,初始进位为0 k=end1/10; //计算进位值 yu=end1%10; //计算输出结果 c=yu+48; //将结果换成字符形式 result[all-al+j-fench]=c; if((j==0)&&(end1>=10)) result[all-al+j-1-fench]=k+48;//判断乘数已到最高位后有没有进位,有则进 } k=0; fench++; } printf("\n--------------------------------------------------------------------------------\n"); for(i=0;i);//输出结果 fputc(result,fpout);//把结果写入文件 } printf("\nok!\n"); free(result);//释放内存 result=NULL; }
作者: x86    时间: 2005-9-28 23:56     标题: 一个高精度乘法的程序

折腾了2天,终于最后写出了这段代码,写得时候真的体验到代码优化的重要性.
原先的代码算2个6700多位的整数要1个多小时,cpu一直是100%,后来改了一部分,时间快了很多,然后算10000多位的整数时,消耗的内存极高,达到了190m之多,又改,最后发现代码短了许多(当然,短的代码不一定性能高),现在时间就很快6000多位的只要1分钟不到就完成了,且内存消耗永远很低...
当然,算法一直是起先的,还有更好的算法...
作者: 皮蛋瘦肉    时间: 2005-9-30 11:45     标题: 一个高精度乘法的程序

hehe
厉害
我手下了
回去慢慢研究
作者: x86    时间: 2005-9-30 14:42     标题: 一个高精度乘法的程序

这个不需要慢慢看,关键这部分就是了,其实也没什么技巧,仔细看一下,很简单...
for(i=bl-1;i>=0;i--)
      {
temp1=b-48;
             for(j=al-1;j>=0;j--)
             {
               temp2=a[j]-48;
               end1=temp1*temp2+k+(result[all-al+j-fench]-48);//计算2个数的乘积并加上进位,初始进位为0
               k=end1/10;                  //计算进位值
               yu=end1%10;              //计算输出结果
               c=yu+48;                    //将结果换成字符形式
               result[all-al+j-fench]=c;
               if((j==0)&&(end1>=10))
               result[all-al+j-1-fench]=k+48;//判断乘数已到最高位后有没有进位,有则进
              }
              k=0;
              fench++;
}

为了提高速度,试着把这部分最关键的部分换成内联汇编,结果很不理想,速度反而慢了一点,也许是因为偶汇编代码写得太差劲的缘故(偶只学过一点汇编,这里只是做了简单的替换:(  )




欢迎光临 黑色海岸线论坛 (http://bbs.thysea.com/) Powered by Discuz! 7.2