在64位x 64位乘法中使用Karatsuba算法真的有效吗? [英] Is it really efficient to use Karatsuba algorithm in 64-bit x 64-bit multiplication?

问题描述

我在AVX2上工作，需要计算64位x64位-> 128位加宽乘法并以最快的方式获得64位的高位.由于AVX2没有这样的说明，所以我使用Karatsuba算法来提高效率和提高速度是否合理?

I work on AVX2 and need to calculate 64-bit x64-bit -> 128-bit widening multiplication and got 64-bit high part in the fastest manner. Since AVX2 has not such an instruction, is it reasonable for me to use Karatsuba algorithm for efficiency and gaining speed?

推荐答案

否.在现代体系结构上，唐津胜过教科书乘法的交叉点通常在8到24个机器字之间(例如x86_64上的512和1536位之间).对于固定大小，阈值位于该范围的较小范围内，新的ADCX/ADOX指令可能会将其带入标量代码，但64x64仍然太小而无法从Karatsuba中受益.

No. On modern architectures the crossover at which Karatsuba beats schoolbook multiplication is usually somewhere between 8 and 24 machine words (e.g. between 512 and 1536 bits on x86_64). For fixed sizes, the threshold is at the smaller end of that range, and the new ADCX/ADOX instructions likely bring it in somewhat further for scalar code, but 64x64 is still too small to benefit from Karatsuba.

这篇关于在64位x 64位乘法中使用Karatsuba算法真的有效吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！