电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

Win32下无符号大整数相乘优化算法及其C++实现VIP免费

Win32下无符号大整数相乘优化算法及其C++实现_第1页
1/9
Win32下无符号大整数相乘优化算法及其C++实现_第2页
2/9
Win32下无符号大整数相乘优化算法及其C++实现_第3页
3/9
Win32 下无符号大整数相乘优化算法及其C++实现 转载请注明出处和作者,谢谢。 Lightning[0GiNr] 1、问题的引出: 两个无符号的大整数相乘是一道实践意味很浓的算法题目,这里的“无符号”(unsigned)指的是相乘的两个数都是正数,不需要考虑符号。由于32 位计算机没有指令支持128 及以上二进制位数的大整数的运算,所以必须自己设计算法来计算。传统的优化算法基本上都是理论层面上的优化,即尽可能地从理论上减少乘法次数,但是往往不能达到预想的优化效果。比方说二分法优化: 将待相乘的整数M 分成相等的左右两个部分M1 和 M2, 另一个相乘整数N 也同样地分成N1 和 N2, 然后按这样的方法递归分割,直到最后的元素大小小到可以利用CPU 指令直接计算为止。这时利用公式M*N = (M1 + M2) * (N1 + N2) = M1*N1 + M1*N2 + M2*N1 + M2*N2 结合移位运算再逐层返回得出最终结果。 显然这种算法理论性过强,一来只有当M 和 N 为 2 的 P 次方(P 为正整数)时的优化才会节省时间,而实际情况下应对随机数据时则会出现大量位移操作,速度不会得到提升;二来使用的递归算法由于调用栈和跳转指令的开销,浪费大量CPU 时间;三来这种方法实际上并没有真正地减少乘法次数,因为除了最后一层递归中的乘法可以直接用CPU 指令实现,其余各层的乘法由于数值较大仍得另想办法。 由此,我们须从实际出发,探索一些实用的优化方法。 本程序的测试环境为:Windows XP SP2 32bit + 512MB SDRAM + P4 1.80Ghz + VC 2、朴素的算法思路: 为了简易起见,我们先来设计一个朴素的算法。 使用一个DWORD 类型的数组m_buffer 作为缓冲区,大小为64,同时声明一个int 类型的变量m_nUsed,记录当前缓冲中DWORD 使用的个数(即后面所提到的“位数”)。 类的声明如下: 代码清单:BigNumber.cpp #include #include class CBigNumber { public: CBigNumber() { memset(this, 0, sizeof(*this)); m_nUsed = 1; } CBigNumber& operator = (DWORD dwData); CBigNumber& operator *= (const CBigNumber& right); int GetCount() const { return m_nUsed; } const DWORD* GetBuffer() const { return m_buffer; } protected: VOID OffsetAdd(DWORD dwData, int nOffset); int m_nUsed; DWORD m_buffer[64]; }; 首先是赋值函数,这个函...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

Win32下无符号大整数相乘优化算法及其C++实现

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部