Is it really efficient to use Karatsuba algorithm in 64-bit x 64-bit multiplication?
avx2, c++, parallel-processing, performance, simd
Solution
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.
Problem
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?
Related problems
- How to efficiently perform double/int64 conversions with SSE/AVX?
- SIMD signed with unsigned multiplication for 64-bit * 64-bit to 128-bit
- Can I use the AVX FMA units to do bit-exact 52 bit integer multiplications?
- Can long integer routines benefit from SSE?
- Is there any scenario where function fma in libc can be used?
- GCC couldn't vectorize 64-bit multiplication. Can 64-bit x 64-bit -> 128-bit widening multiplication be vectorized on AVX2?