2个64bit的无符号整数相乘，C++如何实现最快？

mathematica

这个问题完全看不明白

G-Spider

KeyTo9_Fans 发表于 2012-7-19 21:13
在ubuntu系统，g++语言里面，

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

x64 指令:
IMUL r/m64     
(表示 RDX:RAX= RAX*r/m64)
对应两个无符号64位乘，得到128位的结果，高64位进rdx(不够的填0),低64位进rax中。

KeyTo9_Fans

直接用UnsignedMultiply128函数似乎就可以了。

参考文献：
https://docs.microsoft.com/zh-cn ... unsignedmultiply128

但以下这段代码：

1. #include<Windows.h>
   
2. #include<winnt.h>
   
3. #include<cstdio>
   
4. unsigned __int64 a, b, c, d;
   
5. int main()
   
6. {
   
7.         scanf_s("%I64u%I64u", &a, &b);
   
8.         d = UnsignedMultiply128(a, b, &c);
   
9.         return 0;
   
10. }

复制代码

编译出现如下错误：

m128.cpp(8): error C3861: “UnsignedMultiply128”:  找不到标识符

初步猜测是我的电脑缺少相应的硬件，比如：$64$位处理器。

mathe

你的代码是编译成32位代码还是64位代码？
如果32位代码自然不支持，但是如果是64位代码，应该是支持的，64位乘法的支持不需要很新的硬件
比如VS中默认工程有可能是WIN32,就代表32位代码，要改成WIN64的才行。
当然操作系统也要求是64位的，但是我相信现在一般人都应该已经用64位操作系统了

https://stackoverflow.com/questi ... dentifier-not-found

另外AMD 在2003年就推出64位处理器Opteron了，而Intel紧跟者在2004年也推出了64位的Pentium 4。现在想找到不支持64位的PC机处理器还是很困难的。
另外，如果你使用32位代码模式，在Windows上，一个进程用户态内存是无法超过2G的，但是64位就没有这个限制了。

.·.·.

KeyTo9_Fans 发表于 2012-7-23 20:50
由于不知道$64$位直接乘如何实现，先暂时用多次$32$位乘法来实现。代码如下：其中，$l$和$h$是全局的无符号 ...

1. unsigned long long a,d;
   
2. ...
   
3.         asm ("mul %%rdx"
   
4.                 : "+a" (a) ,"+d"(d));
   
5. ...

复制代码

这个函数把a*d储存到a跟d中
a是低64位，d是高64位
gcc可以编译通过
记得输出的时候用%llu,否则显示会出问题

dlpg070

c++ proj的设置应为x64,不是x86
代码正确
------------
1个例子:
a=123456789012
b=123456789012
算得:
c=826             a*b的高64bit
d=45681482693943  a*b的低64bit

a*b=15241578753153483936144 10进制数值
c,d 只是a*b的高64bit ,低64bit,不能直接得到10进制数值

.·.·.

dlpg070 发表于 2019-4-28 20:21
c++ proj的设置应为x64,不是x86
代码正确
------------

话说……gcc完全跑不动这个栗子
话说，为啥这么多人用VS写密集计算的代码呢？
我看到的几乎所有library都是(在windows环境下)要用gcc/cygwin/msys2之类东西编译的

1. B:\>g++ B:\m64.cpp -o m64.exe
   
2. B:\m64.cpp: In function 'int main()':
   
3. B:\m64.cpp:7:13: error: 'scanf_s' was not declared in this scope
   
4.              scanf_s("%I64u%I64u", &a, &b);
   
5.              ^~~~~~~
   
6. B:\m64.cpp:7:13: note: suggested alternative: 'sscanf_s'
   
7.              scanf_s("%I64u%I64u", &a, &b);
   
8.              ^~~~~~~
   
9.              sscanf_s
   

复制代码

风云剑

为啥这么多人用VS写密集计算的代码呢
大概是因为用windows的人多吧，而且VS编译出来的程序优化也不错。

wayne

gcc其实是支持128bit整数的：https://gcc.gnu.org/onlinedocs/gcc/_005f_005fint128.html

1. #include <iostream>
   
2. 
   
3. int main()
   
4. {
   
5. //    typedef unsigned int uint128_t __attribute__((mode(TI)));
   
6.     typedef unsigned __int128 uint128_t;
   
7. 
   
8.      uint64_t x = 0xABCDEABCDEABCDEF;
   
9.      uint64_t y = 0xABABABABABABABAB;
   
10. 
    
11.      uint128_t result = (uint128_t)x * y;
    
12.      uint64_t low = result;
    
13.      uint64_t high = result >> 64;
    
14. 
    
15.      printf("%016llX * %016llX = %016llX%016llX\n", x, y,high,low);
    
16. 
    
17.     return 0;
    
18. }
    

复制代码

运行得到：

1. ABCDEABCDEABCDEF * ABABABABABABABAB = 7335C18DB67335C3F633A7DBB2F633A5

复制代码

对于这个结果，肉眼凡胎看起来有些茫然，那就 用Mathematica验证一下：

1. In[9]:= BaseForm[FromDigits["ABCDEABCDEABCDEF",16]*FromDigits["ABABABABABABABAB",16],16]
   
2. Out[9]//BaseForm= Subscript[7335c18db67335c3f633a7dbb2f633a5, 16]

复制代码

哈哈哈，竟然是 一致的！

灵树

大整数相乘就是一个移位和进位的问题，处理好这两个问题很容易解决。同样可以扩展到任意大数的计算上。