我们是否仍然需要在软件中模拟128位整数,或者现在平均桌面处理器中是否有硬件支持？
我正处于一个项目的设计阶段，该项目需要执行大量简单的 256 位整数运算（仅加、子、多、分），并且需要针对这四个操作进行合理优化的东西。
我已经熟悉 GMP、NTL 和大多数其他重量级 bignum 实现。然而，这些实现的开销促使我做我自己的低级实现——我真的不想这样做；众所周知，这东西很难做对。
在我的研究中，我注意到 Clang 中新的扩展整数类型 - 我是 gcc 用户 - 我想知道是否有人对现实生活中的扩展整数有任何经验，愤怒的实现？它们是否针对“明显的”位大小（256、512 等）进行了优化？
我在 linux 下的 x-64 上使用 C 语言（目前是 Ubuntu，但如果需要，可以向其他发行版开放）。我主要使用 gcc 进行生产工作。
编辑添加：@phuclv 确定了以前的答案C++ 128/256-bit fixed size integer types。（感谢@phuclv。）这个q/a 侧重于c++ 支持；我希望确定是否有人对新的 Clang 类型有任何特定的经验。
我正在研究很长整数的乘法运算(大约100,000个十进制数字).作为我的图书馆的一部分,我要添加两个长数字.
分析表明我的代码在add()和sub()例程中运行的时间高达25%,因此尽可能快地运行它们非常重要.但我还没有看到太大的潜力.也许你可以给我一些帮助,建议,见解或想法.我会测试它们然后再回复你.
到目前为止,我的添加例程进行了一些设置,然后使用了8次展开的循环:
mov rax, QWORD PTR [rdx+r11*8-64]
mov r10, QWORD PTR [r8+r11*8-64]
adc rax, r10
mov QWORD PTR [rcx+r11*8-64], rax
然后是7个具有不同偏移的块然后循环.
我之前尝试从内存中加载值,但这没有帮助.我想那是因为好的预取.我使用Intel i7-3770 Ivy Bridge 4核CPU.但我想编写适用于任何现代CPU的代码.
编辑:我做了一些时间:它在大约2.25个周期/单词中增加1k个单词.如果我移除ADC,那么只剩下MOV,它仍然需要大约1.95个周期/字.所以主要的瓶颈似乎是内存访问.一个库memcpy()工作在大约0.65个周期/单词,但只有一个输入,而不是两个.我猜,因为它使用了SSE寄存器,所以速度要快得多.
一些问题:
ADD r11, 8改用.我非常感谢任何评论.
据我所知,BigInts通常在大多数编程语言中实现为包含数字的数组,例如:当添加其中两个时,每个数字都是一个接一个地添加,就像我们从学校知道的那样,例如:
246
816
* *
----
1062
其中*表示存在溢出.我在学校这样学习,所有BigInt添加函数我已经实现了类似于上面例子的工作.
所以我们都知道我们的处理器只能本地管理从0到2^32/的整数2^64.
这意味着大多数脚本语言为了高级并提供具有大整数的算术,必须实现/使用BigInt库,这些库使用整数作为上面的数组.但当然这意味着它们将比处理器慢得多.
所以我问自己的是:
它可以像任何其他BigInt库一样工作,只是(很多)更快,更低一级:处理器从缓存/ RAM中取一个数字,添加它,然后再将结果写回来.
对我来说似乎是一个好主意,为什么不是那样的？
我想更多地了解SSE2的功能,并想知道是否可以制作支持加法,减法,XOR和乘法的128位宽整数？
SSE/AVX寄存器可以被视为整数或浮点BigNums.也就是说,人们可以忽视存在通道.是否有一种简单的方法可以利用这种观点并将这些寄存器单独或组合用作BigNum？我问,因为我从BigNum库中看到的很少,它们几乎普遍存储并对数组进行算术运算,而不是SSE/AVX寄存器.可移植性？
例:
假设您将SSE寄存器的内容存储为a中的键std::set,您可以将这些内容作为BigNum进行比较.
我创建了一个使用SIMD进行64位*64位到128位的功能.目前我已经使用SSE2(acutally SSE4.1)实现了它.这意味着它可以同时运行两个64b*64b到128b的产品.同样的想法可以扩展到AVX2或AVX512,同时提供四个或八个64b*64到128b的产品.我的算法基于http://www.hackersdelight.org/hdcodetxt/muldws.c.txt
该算法进行一次无符号乘法,一次有符号乘法和两次有符号*无符号乘法.签名的*signed和unsigned*unsigned操作很容易使用_mm_mul_epi32和_mm_mul_epu32.但混合签名和未签名的产品给我带来了麻烦.例如,考虑一下.
int32_t x = 0x80000000;
uint32_t y = 0x7fffffff;
int64_t z = (int64_t)x*y;
双字产品应该是0xc000000080000000.但是如果你假设你的编译器知道如何处理混合类型,你怎么能得到这个呢？这就是我想出的:
int64_t sign = x<0; sign*=-1; //get the sign and make it all ones
uint32_t t = abs(x); //if x<0 take two's complement again
uint64_t prod = (uint64_t)t*y; //unsigned product
int64_t z = (prod ^ sign) - sign; //take two's complement based on the sign
使用SSE可以这样做
__m128i xh; //(xl2, xh2, xl1, xh1) high is signed, low unsigned
__m128i …我在 C 中有一个代码，它以与人类相同的方式进行加法，因此，例如，如果我有两个数组A[0..n-1]and B[0..n-1]，则该方法将执行C[0]=A[0]+B[0]，C[1]=A[1]+B[1]...
我需要帮助使这个函数更快，即使解决方案使用的是内在函数。
我的主要问题是我有一个非常大的依赖问题，因为迭代i+1取决于迭代的进位i，只要我使用基数 10。所以如果A[0]=6和B[0]=5，C[0]必须是1并且我有1下一个加法的进位。
我能做的更快的代码是这样的：
void LongNumAddition1(unsigned char *Vin1, unsigned char *Vin2,
unsigned char *Vout, unsigned N) {
for (int i = 0; i < N; i++) {
Vout[i] = Vin1[i] + Vin2[i];
}
unsigned char carry = 0;
for (int i = 0; i < N; i++) {
Vout[i] += carry;
carry = Vout[i] / …因为似乎没有ADC的固有内容而且我不能使用Visual C++的x64架构使用内联汇编程序,如果我想使用add with carry编写函数但是将它包含在C++命名空间中,我该怎么办？
(使用比较运算符进行仿真不是一种选择.这256兆位的添加对性能至关重要.)
为了好玩，我正在用 Rust 编写一个 bignum 库。我的目标（与大多数 bignum 库一样）是尽可能提高效率。我希望它即使在不寻常的架构上也能高效。
在我看来，CPU 将在具有架构的本机位数的整数上更快地执行算术运算（即，u64对于 64 位机器，u16对于 16 位机器等）因此，因为我想创建一个在所有架构上都有效的库，我需要考虑目标架构的本机整数大小。这样做的明显方法是使用cfg 属性 target_pointer_width。例如，定义最小的类型，它总是能够容纳超过最大原生 int 大小：
#[cfg(target_pointer_width = "16")]
type LargeInt = u32;
#[cfg(target_pointer_width = "32")]
type LargeInt = u64;
#[cfg(target_pointer_width = "64")]
type LargeInt = u128;
但是，在调查此问题时，我遇到了此评论。它给出了一个架构示例，其中原生 int 大小与指针宽度不同。因此，我的解决方案不适用于所有架构。另一个潜在的解决方案是编写一个构建脚本，它编码一个LargeInt基于 a 的大小定义的小模块usize（我们可以像这样获取：）std::mem::size_of::<usize>()但是，这与上面有相同的问题，因为usize它基于指针宽度以及。最后一个明显的解决方案是简单地为每个架构保留一个本地 int 大小的映射。但是，此解决方案不够优雅且无法很好地扩展，因此我想避免使用它。
所以，我的问题是：有没有办法找到目标的本机 int 大小，最好在编译之前，以减少运行时开销？这种努力是否值得？也就是说，使用本机 int 大小与指针宽度之间是否可能存在显着差异？
我在AVX2上工作,需要计算64位x64位 - > 128位加宽乘法,并以最快的方式获得64位高位.由于AVX2没有这样的指令,使用Karatsuba算法提高效率和提高速度是否合理？
这是另一种SSE is slower than normal code! Why?类型的问题。
我知道有很多类似的问题，但它们似乎与我的情况不符。
我正在尝试使用蒙哥马利模乘法实现Miller-Rabin 素性测试以进行快速模运算。
我尝试以标量和 SIMD 方式实现它，结果发现 SIMD 版本慢了大约 10%。
[esp+16] 或 [esp+12] 指向是否有人想知道的模倒数。N
我真的很困惑这样一个事实，即所谓的 1 Latency 1c Throughput 1uops 指令psrldq需要超过 3 Latency 0.5c Throughput 1uops pmuludq。
下面是在 Ryzen 5 3600 上运行的 Visual Studio 的代码和运行时分析。
关于如何改进 SIMD 代码和/或为什么它比标量代码慢的任何想法表示赞赏。
PS似乎由于某种原因，一条指令关闭了运行时分析
编辑1：对图像的评论是错误的，我在下面附上了一个固定版本：
;------------------------------------------
; Calculate base^d mod x
;
; eax = 1
; esi = x
; edi = bases[eax]
; ebp = d
; …操作系统：Linux（Debian 10）
CC：GCC 8.3
CPU：i7-5775C
在GCC中有一个unsigned __int128/ __int128，但是有什么办法在GCC中有一个uint256_t/ int256_t？
我读过一篇__m256i似乎来自英特尔的文章。我可以包含任何标头来获取它吗？
它像假设一样有用unsigned __int256吗？我的意思是，如果您可以为其分配/比较，比较，按位运算等。
它的等效符号是什么（如果有）？
编辑1：
我做到了：
#include <immintrin.h>
typedef __m256i uint256_t;
并编译。如果可以进行一些操作，请在此处进行更新。
编辑2：
发现问题：
uint256_t m;
ptrdiff_t l = 5;
m = ~((uint256_t)1 << l);
输出：
error: can’t convert a value of type ‘int’ to vector type ‘__vector(4) long long int’ which has different size
m = ~((uint256_t)1 << l);