找回密码
 欢迎注册
楼主: KeyTo9_Fans

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

[复制链接]
发表于 2012-8-3 15:23:00 | 显示全部楼层
这个问题完全看不明白
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-7-2 22:13:46 | 显示全部楼层
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中。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-4-28 12:20:59 | 显示全部楼层
直接用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$位处理器。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-4-28 14:40:44 | 显示全部楼层
你的代码是编译成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位就没有这个限制了。

点评

根据你的提示,在vs里下拉解决方案平台,发现是win32,改成x64,编译就通过了,而且运行结果正确。  发表于 2019-4-28 15:34
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-4-28 15:26:52 | 显示全部楼层
本帖最后由 .·.·. 于 2019-4-28 15:32 编辑
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,否则显示会出问题
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-4-28 20:21:10 | 显示全部楼层
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进制数值

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-4-29 13:58:51 | 显示全部楼层
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
复制代码

点评

其实我的吐槽主要是针对msc的,因为gcc严格遵循各种C++标准(比如C++11甚至C++17)而MS总是给C++捣乱(哪怕--std=c++17都干不动这伙计……)  发表于 2019-4-30 00:25
sscanf sscanf_s 都是ms先用的, sscanf_s是 sscanf 的改进版本,ms专有,gcc显然不支持, _s 表示safe  发表于 2019-4-29 18:26
windows的library是gcc生成的? 先有windows还是linux? 先有msc还是gcc? c是最低级的高级语言,支持汇编语言,曾经被誉为系统编程语言.应用于开发新的系统.如今辉煌不再  发表于 2019-4-29 18:10
改成sscanf吧,sscanf_s是微软的。但那个UnsignedMultiply128,gcc是否支持就不清楚了。  发表于 2019-4-29 16:34
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-4-29 16:36:33 | 显示全部楼层
为啥这么多人用VS写密集计算的代码呢
大概是因为用windows的人多吧,而且VS编译出来的程序优化也不错。

点评

^_^  发表于 2019-4-30 13:20
强烈抵制VC  发表于 2019-4-30 13:19
要改成scanf,然后把%I64u改成%llu,然后后面的UnsignedMultiply128是否真的支持我也不清楚……所以我才来吐槽的……明明有c++的stl,微软就是不用……你也没办法  发表于 2019-4-30 00:27
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-4-30 21:08:26 | 显示全部楼层
gcc其实是支持128bit整数的:https://gcc.gnu.org/onlinedocs/gcc/_005f_005fint128.html
  1. #include <iostream>

  2. int main()
  3. {
  4. //    typedef unsigned int uint128_t __attribute__((mode(TI)));
  5.     typedef unsigned __int128 uint128_t;

  6.      uint64_t x = 0xABCDEABCDEABCDEF;
  7.      uint64_t y = 0xABABABABABABABAB;

  8.      uint128_t result = (uint128_t)x * y;
  9.      uint64_t low = result;
  10.      uint64_t high = result >> 64;

  11.      printf("%016llX * %016llX = %016llX%016llX\n", x, y,high,low);

  12.     return 0;
  13. }
复制代码


运行得到:
  1. ABCDEABCDEABCDEF * ABABABABABABABAB = 7335C18DB67335C3F633A7DBB2F633A5
复制代码

对于这个结果,肉眼凡胎看起来有些茫然,那就 用Mathematica验证一下:
  1. In[9]:= BaseForm[FromDigits["ABCDEABCDEABCDEF",16]*FromDigits["ABABABABABABABAB",16],16]
  2. Out[9]//BaseForm= Subscript[7335c18db67335c3f633a7dbb2f633a5, 16]
复制代码

哈哈哈,竟然是 一致的!

点评

测试了一下,好像GCC的支持比我写的汇编好一点,我以为gcc会自动重命名寄存器,其实不会……导致我的代码里面多了一句“把变量复制进%rdx”(以及,把结果复制出来)  发表于 2019-5-6 18:54
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-5-13 09:50:54 | 显示全部楼层
大整数相乘就是一个移位和进位的问题,处理好这两个问题很容易解决。同样可以扩展到任意大数的计算上。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-28 20:59 , Processed in 0.049066 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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