实验一 实验报告.doc

实验一_实验报告深 圳 大 学 实 验 报 告
课程名称：算法设计与分析1500770002
实验项目名称：基于分治法的大整数乘法
学院： 计算机与软件学院
专业：
深 圳 大 学 实 验 报 告
课程名称：算法设计与分析1500770002
实验项目名称：基于分治法的大整数乘法
学院： 计算机与软件学院
专业： 软件工程
指导教师： 刘刚
报告人： 李玉苗学号： 2012150107班级：1班
报告人： 许佳丽 学号： 2012150140 班级： 1班
实验时间：2014-10-20
实验报告提交时间：2014-11-9
教务部制
实验目的：
掌握分治法。
学会测试和分析算法的时间性能
实验要求：
1. 编写普通大整数乘法
2. 编写基于分治的大整数乘法
3. 编写改进的基于分治的大整数乘法
4．编写一个随机产生数字的算法，分别产生两个10, 100, 1000, 10000, 100000位的数字a和b，该数字的每一位都是随机产生的
5. 用4所产生的数字来测试1、 2和3算法的时间，列出如下表格。
普通大整数乘法的时间
分
大整数乘法的时间
改进的分治大整数乘法的时间
10位
100位
1000位
10000位
10万位
100万位
1000万位
1亿位
10亿位
...
(1)一直增长数字的位数，直到计算机内存溢出，算法无法继续进行下去。
(2)当位数较小时，乘法所需要的时间较短，这时候可以多次循环该算法，用平均时间来代表该算法的运行时间。比如运行算法100次，，则该算法的执行时间是15毫秒。
6. 画出相应的散点图，其中x轴是矩阵的阶，y轴是所花费的时间，用不同的颜色表示不同的算法所花费的时间
7. 思考（选做）：
（1）在你的机器中，乘法是否比加法更费时？从哪里体现出来的？
（2）如果要做更大规模的乘法，比如10亿亿位的两个数的乘法，你有什么方法来解决这个问题？
方法、步骤：
1. 编写随机产生数字的算法，将其放入算法代码中用于测试
（1）普通大整数乘法：随机生成0—9十位整数，并放入一维整数数组中，用生成此类整数的个数控制大整数的位数。
（2）分治法大整数乘法：随机生成‘0’—‘9’十个字符，存在字符串中，同样用生成此类字符串的个数控制大整数位数；之后再将字符转换成整数。
2. 编写普通大整数乘法
按照乘法的法则，使第二个大整数从后往前逐个乘上第一个大整数从后往前的数，并存放于整数数组中；然后对以上得到的整数数组进行进位运算；最后输出。
3. 编写基于分治的大整数乘法
将大整数进行拆分，最终拆分成1位数的乘法，再合并结果
4. 编写改进的基于分治的大整数乘法
在分治法的基础上进行改进，分治的大整数乘法是每一位看成一个数，两数