大整数相乘算法分治法_大整数乘法分治法算法资源-CSDN文库

5星 · 超过95%的资源需积分: 45 38 浏览量 2011-03-07 16:05:43 上传评论 7 收藏 78KB DOC 举报

资源推荐

资源详情

资源评论

大整数乘法的实现

姓名：张龙涛学号：E 30714041

专业：07 级网络 1 班成绩：

目的：在计算机语言中，整数最大可以设置为 unsigned long 类型的，但是表

示有限，当涉及到两个大整数相乘的时候，会出现不能表示的情况，鉴于此编

制此算法予以解决大整数相乘。

算法实现思想：本程序使用分治法实现，将 n 位二进制整数 X 和 Y 都分为 2 段，

每段的长为 n/2 位。对输入的数转化为 8 的倍数，使用分治法转化为 1 位，然

后递归调用计算。

算法源程序如下：

//张龙涛于 2010 年 5 月 8 日晚完成，此程序实现了大整数相加和相乘

//但由于时间原因并未完成大整数相减的功能，所以并未实现时间

//复杂度为 O(n^1.59).但程序后留有大整数相减的方法，留由以后

//有时间进行推展。

//该程序处理 10 进制数。

#include<iostream>

#include<math.h>

#include<string>

using namespace std;

string compute(string str1,string str2);//计算大整数相乘。

string move(string str1,int n);//对大整数进行移位

string bigplus(string str1,string str2);//完成大整数相加的功能。

void input(string a,string b)//对刚输入的大整数进行初始处理

{

string str1,str2,str3,str4,total;

int length1=a.length();

int length2=b.length();

while(length1 % 8!=0)//把 a,b 两个数都改成 8 的倍数，以方便后面对其切割。

{

a="0"+a;

length1=a.length();

}

while(length2 % 8!=0)

{

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余4页未读，立即下载

内容反馈

zhuanmenxiadongxi

2012-10-26

源代码，挺好用的，用动态数组达到了真正的大数
z853483687

2012-06-13

很早就下了，一直忘了评价，这个很不错，如果直接是程序文件就更好了
物理发财

2012-11-12

真的可以用，不错不错，十几位的都没有问题的说
clezo

2013-11-06

还行，都可以用
沐枫秋茗

2016-08-25

挺好的，能用！！！

前往

页

没事的咖啡店

粉丝: 1
资源: 9

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip