分治策略实现大整数二进制乘法

"二进制的大整数乘法实验报告" 在本次实验中，目标是设计一个基于分治思想的二进制大整数乘法算法。实验要求使用递归方法处理位数为2的整数幂的大整数乘法，并通过数组来存储和操作这些大整数。下面将详细介绍实验的算法描述、调试过程以及运行结果。 **算法描述** 1. 主函数(Main)： - 首先，读入两个大整数u和v，它们的位数n是2的整数幂。 - 计算u和v的位数n。 - 调用Mul函数进行乘法运算，将结果存储在一个数组Mult中。 - 清理Mult数组中的前导零和尾随零，然后输出最终结果。 2. Mul函数（递归实现）： - 当n等于1时，这是基本情况，直接计算u[0]和v[0]的乘积，返回结果。 - 如果n不等于1，将n除以2得到mid。 - 将u和v分别分为两部分：w、x、y、z，每部分的位数为mid。 - 分别计算w*y、w*z、x*y和x*z，并存储结果。 - 对w*y和w*z进行倒置操作，以便后续的位运算。 - 对w*y右移n位，然后计算s11 = wz + xy，再将s11右移n/2位。 - 计算s22 = wy/2^n + (wz+xy)/2^(n/2)，这涉及到位运算和取模操作。 - 使用递归调用，将结果组合成更大的乘积，最后返回结果数组。 **调试过程与问题解决** 在调试过程中，遇到的主要问题是数据类型的问题。原本将待相乘的数定义为整型（int），递归函数的返回类型也是int，这导致了当乘积超过整型范围时，结果不正确。为了解决这个问题，将待相乘的数和递归函数的返回类型更改为长整型（long），确保在计算机允许的数据范围内正确处理大整数。 **运行结果** 经过调整后，该算法能够正确处理任意位数为2的整数幂的大整数乘法，给出正确的乘积。实验结果表明，分治法在处理大整数乘法时效率较高，且代码结构清晰，易于理解和实现。 这个实验旨在通过实现二进制大整数乘法，让学习者掌握分治法的基本思想和算法设计步骤。通过对数据类型的调整和递归算法的优化，成功地实现了满足要求的算法，能够在实际中处理大整数的乘法运算。