问题分析:
在计算机上处理一些大数据相乘时,由于计算机硬件的限制,不能直接进行相乘得到想要的结果。可以将一个大的整数乘法分而治之,将大问题变成小问题,变成简单的小数乘法再进行合并,从而解决上述问题。
当分解到只有一位数时,乘法就很简单了。
算法设计:
分解:
首先将2个大整数a(n位)、b(m位)分解为两部分:ah和al、bh和bl
ah表示大整数a的高位,al表示大整数a的低位,,ah、al为n/2位。
bh表示大整数b的高位,bl表示大整数b的低位,,bh、bl为m/2位。
2个大整数a(n位)、b(m位)相乘转换成了4个乘法运算ah*bh、ah*bl、al*bh、al*bl,而乘数的位数变为了原来的一半。
求解子问题:
继续分解两个乘法运算,直到分解有一个乘数位1位数时停止分解,进行乘法运算并记录结果。
合并:
将计算出的结果相加并回溯,求出最终结果。
#include<stdlib.h>
#include<cstring>
#include <iostream>
using namespace std;
#define M 100
char sa[1000];
char sb[1000];
typedef struct _Node {
int s[M];
int l;
int c;
} Node, *pNode;
void cp(pNode src, pNode des, int st, int l) {
int i, j
今天的文章大整数乘法算法分析_整式的除法法则分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/77933.html