算法思想之分治法-大整数乘法问题.docx
49 浏览量
2023-10-28
20:32:06
上传
评论
收藏 19KB DOCX 举报
2-算法思想之分治法-大整数乘法问题
2020-11-25 12:30:34 | 算法思想
算法–分治法之大整数乘法
问题描述
在计算机上处理一些大数据相乘时，由于计算机硬件的限制，不能直接进行相乘
得到想要的结果。可以将一个大的整数乘法分而治之，将大问题变成小问题，变
成简单的小数乘法再进行合并，从而解决上述问题。
问题分析
分析：大数据可以分解称高位和地位，比如 1534268973 可以表示为
15342*10^5+68973，那么两个大数据都进行拆解后，可以通过十字相乘获得 4 个
相对较小的乘法，将 4 个乘法的结果相加即可得到大数据相乘的结果。4 个相对
较小的乘法各自可以继续分解称 4 个更小的乘法，再进行合并。
举个例子： 3278×41926
=(32×10^2+78)×(419×10^2+26)
=32×419×10^4 + 32 × 26 × 10^2 + 78×419×10^2 + 78×26
继续拆分：
32×419×10^4
=(3×10+2)×(41×10+9)×10^4
=3×41×10^6 + 3×9×10^5 + 2×41×10^5 + 2×9×10^4
=123×10^6 + 27×10^5 + 82×10^5 + 18×10^4
=13408×10^4
算法实现
剩余11页未读，继续阅读
资源评论
