作者AJE (小杰)
看板C_and_CPP
标题Re: [问题] 长整数的乘法问题.......
时间Wed Oct 28 19:24:32 2009
※ 引述《liu2007 (薯)》之铭言：
: 我的问题是「长整数的运算」
: 用C++ 6.0 写的
: 加法跟减法都有做出来
: 但是两个长整数的乘法
: 每个位数之间的处理状况是在是太多了
: 所以我想不出快速的解法
: 只好用土法炼钢的方式
: R = A * B
: 设一个count 存乘数 count = B
: 然後设一个Result 存结果 R = 0
: 然後设一个回圈
: while ( cout != 0 )
: {
: R = R+A;
: count--;
: }
: 简单的说就是电脑的原理: 连加
: 以上是我的想法，不是程式码
: 想请问版上高手是否有更快速的方法??
: 就是直接对每个bit做处理
: 总共做 bit 大次就好了
: 谢谢回答~
刚刚想的内容 可能有瑕疵
1st.先完成 32bit * 32bit 存成64bit的结果
2nd.从第一步类推到第二步 完成64bit * 64bit
1st.的作法:
有两个32bit的整数A与B
A = AH*2^16 + AL , B = BH*2^16 + BL; AH,AL与BH,BL都是16bit的整数
A*B = AH*BH*2^32 + (AH*BL + AL*BH)*2^16 + AL*BL;
AH*BH , AH*BL , AL*BH 与AL*BL都是32bit的整数
把以上四各转化成相对应的64bit整数後 加起来就是结果
2nd.的作法:
类似1st. 把64bit的整数拆成两个32bit的整数 各别相乘之後再相加即可
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 60.250.190.7
1F：推 VictorTom:原po没有限定在64 bit或128 bit啊@_@" 10/28 19:58
2F：→ liu2007:对不起我题目没定义好，因为我不知道长整数有别的实作 10/28 21:18
3F：→ liu2007:楼下才是我要的，原PO抱歉 Orz... 10/28 21:18
4F：→ AJE:没注意到 没关系啦 不用道歉 太客气了 10/28 22:02