数学研发论坛

 找回密码
 欢迎注册
查看: 3738|回复: 27

[求助] 2个64bit的无符号整数相乘,C++如何实现最快?

[复制链接]
发表于 2012-7-18 17:21:43 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
我想编写一个C++程序,

输入两个$64$bit的整数$a$和$b$,

然后计算$a$*$b$,结果为$128$bit的整数,

我希望用两个$64$bit的整数$h$和$l$表示这个$128$bit的整数,

其中$h$为前$64$个bit,$l$为后$64$个bit。

最后输出$h$和$l$。

例$1$:
===============
输入:
4294967297        4294967297
——————————
输出:
1        8589934593
===============

例$2$:
===============
输入:
18446744073709551615        18446744073709551615
——————————
输出:
18446744073709551614        1
===============

程序运行时间越短越好。

请问如何实现?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-7-19 08:38:12 | 显示全部楼层
如果在64位OS中,直接乘即可;
如果在32位OS中,就比较麻烦了,要经历多次乘法,带位加法。
而乘法应尽量设计成并行的,指令集需用到SSE2,寄存器用到MM或XMM.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-19 09:39:25 | 显示全部楼层
“如果在64位OS中,直接乘即可”

我知道直接乘可以得到低$64$位的$l$,高$64$位的$h$也可以直接乘得到吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-7-19 10:07:14 | 显示全部楼层
要用汇编,读取 RDX:RAX,其中 h <--RDX, l <-- RAX

评分

参与人数 1贡献 +2 鲜花 +2 收起 理由
KeyTo9_Fans + 2 + 2 原来如此。我去试试看~

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-19 21:13:28 | 显示全部楼层
在ubuntu系统,g++语言里面,

两个$64$bit的整数相乘,要得到一个$128$bit的整数,用什么指令?

网上只能找到两个$32$bit的整数相乘得到一个$64$bit的整数的指令。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-7-20 08:06:45 | 显示全部楼层
c++里面好像不支持内嵌的64位指令
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-7-20 09:11:21 | 显示全部楼层
这个是不是与编译器是否支持相关?
好像记得是ICC支持的。
可惜现在我还没用过64位系统,没得试。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-23 20:50:03 | 显示全部楼层
由于不知道$64$位直接乘如何实现,先暂时用多次$32$位乘法来实现。代码如下:
  1. void m64(unsigned __int64 a,unsigned __int64 b)
  2. {
  3.         unsigned __int64 ah,al,bh,bl,m;
  4.         ah=unsigned int(a>>32);
  5.         al=unsigned int(a);
  6.         bh=unsigned int(b>>32);
  7.         bl=unsigned int(b);
  8.         l=ah*bl;
  9.         m=al*bh;
  10.         h=ah*bh+(l>>32)+(m>>32);
  11.         l<<=32;
  12.         m=(m<<32)+l;
  13.         if(m<l)h++;
  14.         l=al*bl+m;
  15.         if(l<m)h++;
  16. }
复制代码
其中,$l$和$h$是全局的无符号$64$位整数,是最终的结果。

不知道这段代码还有没有优化的余地。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-7-24 09:44:24 | 显示全部楼层
依葫芦画瓢,不知是否算更简洁些?
  1. void m64(unsigned __int64 a,unsigned __int64 b)
  2. {
  3.         unsigned __int64 ah,al,bh,bl;
  4.         unsigned __int64 l,m,h;

  5.         ah=unsigned int(a>>32);
  6.         al=unsigned int(a);
  7.         bh=unsigned int(b>>32);
  8.         bl=unsigned int(b);

  9.         l=ah*bl;
  10.         m=al*bh+l;
  11.         h=((m<l)?(1ULL<<32):0)+ah*bh+(m>>32);
  12.         m<<=32;
  13.         l=al*bl+m;
  14.         if(l<m)++h;
  15. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-7-25 15:38:44 | 显示全部楼层
特别注意:当 al*bh+ah*bl 溢出时,向 h 需加 2^32,而不是 1.
我是突然间发现并修正这个bug的。
(——再看楼主发给我的短消息,也指明了这点;可怜我刚才改了几遍,居然都仅+1)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-5-25 01:28 , Processed in 0.054291 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表