大数运算(4)——大数乘法
发布日期:2021-06-29 13:10:41
浏览次数:3
分类:技术文章
本文共 1310 字,大约阅读时间需要 4 分钟。
摘自:http://blog.csdn.net/lisp1995/article/details/52316466。
首先说一下乘法计算的算法:同样是模拟人工计算时的方法。
从低位向高位乘,在竖式计算中,我们是将乘数第一位与被乘数的每一位相乘,记录结果之后,用第二位相乘,记录结果并且左移一位,以此类推,直到计算完最后一位,再将各项结果相加,得出最后结果。
计算的过程基本上和小学生列竖式做乘法相同。为编程方便,并不急于处理进位,而将进位问题留待最后统一处理。
我们以125*53为例来说明计算过程:
1、先算125*3,3*5得到15个1,3*2得到6个10,3*1得到3个100;
2、接下来算125*5,5*5得到25个10,2*5得到10个100,5*1得到5个1000;
3、乘法过程完毕。接下来从 a[0]开始向高位逐位处理进位问题。a[0]留下5,把1 加到a[1]上,a[1]变为32 后,应留下2,把3 加到a[2]上……最终使得a里的每个元素都是1 位数,结果就算出来了
结果就是6625。
总结一个规律:即一个数的第i 位和另一个数的第j 位相乘所得的数,一定是要累加到结果的第i+j 位上。这里i, j 都是从右往左,从0 开始数。
即:ans[i+j] = a[i]*b[j];另外进位时要处理,当前的值加上进位的值再看本位数字是否又有进位;前导清零。
下面是C语言代码实现:
- #include<stdio.h>
- #include<string.h>
- #define MAX 100
- char a[MAX],b[MAX];//用字符串进行数字的输入
- int x[MAX+10],y[MAX+10],z[MAX*2+10];//积的位数最多是因数位数的两倍
- int main()
- {
- int len1,len2,i,j;
- while(~scanf("%s %s",a,b))
- {
- len1=strlen(a);
- len2=strlen(b);
- for(j=0,i=len1-1;i>=0;i--)//将字符串中字符转化为数字,并倒序储存
- x[j++]=a[i]-'0';
- for(j=0,i=len2-1;i>=0;i--)
- y[j++]=b[i]-'0';
- for(i=0;i<len1;i++)//将因数各个位上的数字与另一个各个位上的数字相乘
- {
- for(j=0;j<len2;j++)
- z[i+j]=z[i+j]+x[i]*y[j];//先乘起来,后面统一进行进位
- }
- for(i=0;i<MAX*2;i++)//进行进位
- {
- if(z[i]>=10) //若>=10
- {
- z[i+1]=z[i+1]+z[i]/10; //将十位上数字进位
- z[i]=z[i]%10; //将个位上的数字留下
- }
- }
- for(i=MAX*2;i>0;i--) //删除0的前缀
- {
- if(z[i]==0)
- continue;
- else
- break;
- }
- for(;i>=0;i--) //倒序输出
- printf("%d",z[i]);
- printf("\n");
- }
- return 0;
- }
转载地址:https://chaiyu2002.blog.csdn.net/article/details/79756990 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月18日 23时34分17秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
OpenCV+python识别并打印HSV颜色
2019-04-29
2021-03-29
2019-04-29
网络攻击与防御--引言
2019-04-29
网络攻击与防御--网络协议漏洞
2019-04-29
sql注入: 判断注入点类型
2019-04-29
千人千面Elasticsearch实战学习笔记
2019-04-29
最大子数组问题(递归)(java)
2019-04-29
2021年第十二届蓝桥杯软件赛省赛第二场 C/C++ 大学 A 组
2019-04-29
2020年哨兵数据批量下载(USGS)
2019-04-29
简单3步快速生成千万级别mysql测试数据库,模拟电商数据
2019-04-29
EasyDSS平台接入设备量过多的情况下如何进行批量推流测试?
2019-04-29
mysql数据库操作基础
2019-04-29
Mariadb基础管理
2019-04-29
awk 的内置变量 NF、NR、FNR、FS、OFS、RS、ORS
2019-04-29
CentOS系统内核升级攻略
2019-04-29
linux系统时区修改(Debian的主机和docker)
2019-04-29