我有一个128位无符号整数A和一个64位无符号整数B.什么是最快的计算方法A % B- 即将A除以B的(64位)余数？
我希望用C或汇编语言来做这件事,但我需要针对32位x86平台.遗憾的是,我无法利用编译器对128位整数的支持,也无法利用x64架构在单条指令中执行所需操作的能力.
编辑:
谢谢你到目前为止的答案.但是,在我看来,建议的算法会非常慢 - 执行128位到64位除法的最快方法是利用处理器对64位乘32位除法的原生支持吗？有没有人知道是否有办法在一些较小的部门中执行更大的划分？
回复:B多久换一次？
主要是我对一般解决方案感兴趣 - 如果A和B每次都可能不同,你会进行什么计算？
然而,第二种可能的情况是B不会像A那样经常变化 - 每个B可能有多达200个As除以.在这种情况下,你的答案有何不同？
我还在研究C++中任意长整数的例程.到目前为止,我已经为64位Intel CPU实现了加/减和乘法.
一切正常,但我想知道我是否可以通过使用SSE来加快速度.我浏览了SSE文档和处理器指令列表,但我找不到任何我认为可以使用的内容,原因如下:
SSE有一些整数指令,但大多数指令处理浮点.看起来它不是设计用于整数(例如,是否有较小的整数比较？)
SSE的想法是SIMD(相同的指令,多个数据),因此它提供了2或4个独立操作的指令.另一方面,我希望有一个像128位整数加(128位输入和输出)的东西.这似乎不存在.(但是？在AVX2中可能？)
整数加法和减法既不处理输入也不处理输出.因此,手动操作非常麻烦(因而也很慢).
我的问题是:我的评估是正确的还是有什么我忽略的？长整数例程可以从SSE中受益吗？特别是,它们可以帮助我编写更快的添加,子或mul例程吗？
当使用SSE2指令,如PADDD(即_mm_add_epi32内在),有没有办法来检查任何操作是否溢出？
我想也许MXCSR控制寄存器上的标志可能在溢出后设置,但我没有看到这种情况发生.例如,_mm_getcsr()在以下两种情况下打印相同的值(8064):
#include <iostream>
#include <emmintrin.h>
using namespace std;
void main()
{
__m128i a = _mm_set_epi32(1, 0, 0, 0);
__m128i b = _mm_add_epi32(a, a);
cout << "MXCSR: " << _mm_getcsr() << endl;
cout << "Result: " << b.m128i_i32[3] << endl;
__m128i c = _mm_set_epi32((1<<31)-1, 3, 2, 1);
__m128i d = _mm_add_epi32(c, c);
cout << "MXCSR: " << _mm_getcsr() << endl;
cout << "Result: " << d.m128i_i32[3] << endl;
}
有没有其他方法来检查SSE2的溢出？
我们是否仍然需要在软件中模拟128位整数,或者现在平均桌面处理器中是否有硬件支持？
SSE/AVX寄存器可以被视为整数或浮点BigNums.也就是说,人们可以忽视存在通道.是否有一种简单的方法可以利用这种观点并将这些寄存器单独或组合用作BigNum？我问,因为我从BigNum库中看到的很少,它们几乎普遍存储并对数组进行算术运算,而不是SSE/AVX寄存器.可移植性？
例:
假设您将SSE寄存器的内容存储为a中的键std::set,您可以将这些内容作为BigNum进行比较.
对于我正在开发的业余爱好项目,我需要在x86 CPU上模拟某些64位整数运算,并且它需要很快.
目前,我正在通过MMX指令这样做,但这真的很难用,因为我必须一直刷新fp寄存器状态(因为大多数MMX指令处理有符号整数,我需要无符号行为).
所以我想知道如果SSE /优化大师在这里SO可以拿出使用SSE更好地执行.
我需要的操作如下(非常具体):
uint64_t X, Y;
X = 0;
X = 1;
X << 1;
X != Y;
X + 1;
X & 0x1 // get lsb
X | 0x1 // set lsb
X > Y;
具体来说,我不需要通用添加或移位,例如,只需添加一个和左移一个.真的,只是这里显示的确切操作.
当然,除了在x86上,uint64_t使用两个32位标量进行模拟,这很慢(在我的情况下,根本不起作用,因为我需要加载/存储是原子的,它们不会是当加载/存储两个单独的寄存器时).
因此,我需要一个SIMD解决方案.其中一些操作很简单,已经由SSE2支持.其他人(!=和<)需要更多的工作.
建议？SSE和SSE2都没问题.允许SSE3需要一些说服力,SSE4可能是不可能的(支持SSE4的CPU 无论如何都可能运行64位,所以我不需要这些解决方法)
我听说__int128_tGCC提供的128位整数数据类型 是模拟的,因此很慢.不过,据我所知,各种SSE指令集(SSE,SSE2,...,AVX)推出了128位寄存器至少一些指令.我不太了解SSE或汇编/机器代码,所以我想知道是否有人可以向我解释是否__int128_t使用现代版本的GCC模拟算术运算.
我问这个的原因是因为我想知道__int128_t在不同版本的GCC之间是否期望性能差异是有意义的,这取决于SSE指令的优势.
那么,__int128_tGCC会模拟哪些算术部分,以及哪些部分是用SSE指令实现的(如果有的话)？
我想用英特尔I64汇编程序做一些长整数数学运算(128位),需要创建一个2的补码.让我们说我的正面价值在于RDX:RAX.
2的补码是通过"翻转位并加1"来完成的.所以最天真的实现是(4条指令和14个字节的代码):
NOT RAX
NOT RDX
ADD RAX,1 ; Can't use INC, it doesn't set Carry
ADC RDX,0
当我在RAX而不是NOT上使用NEG指令时,它对我来说是"+1"但是Carry是错误的,当RAX为零时NEG RAX清除了Carry,但是我需要携带JUST IN THIS CASE.所以下一个最好的方法可能是(4条指令和11个字节的代码):
NOT RDX
NEG RAX
CMC
ADC RDX,0 ; fixed, thanks lurker
还有4条说明.但是不是加+1,我可以减去-1,因为SBB将Carry-Bit加到减数上,当Carry清零时我会加+1.所以我的下一个最好的尝试是这个,有3个指令和10个字节的代码:
NOT RDX
NEG RAX
SBB RDX,-1
从我冗长的文字中可以看出,这一点并不明显.是否有一种更好,更易理解的方法来在汇编程序中进行级联2的补码？
Windows上是否有任何c编译器本身可以使用128位整数？例如,您可以在linux上使用gcc,使用__uint128_t ...在Windows上有任何其他机会吗？(如果128位计算机也能在32位计算机上运行,那就太好了!:D)
马特奥
如何将两个64位整数乘以另外两个64位整数？我没有找到任何可以做到的指令.