使用非常大的操作数乘法

Question

我正在实现一个多精度模块，目前我卡在乘法中。

为了完成我的算法，我需要使用 Haswell 微架构将两个 64 位的无符号操作数相乘，并将结果存储在内存块中。我正在使用"g ++"进行一个实现，并使用"icpc"进行另一个更有效的实现。

int main(){
    //Operands
    size_t a = 10000000000000000000 //Fit in 8 bytes
           b = 7;
    //To store the result;
    size_t dst[2];
    //Multiplication here... (Note that the multiplication result don't fit in 64bits. So, I need to save the result in two memory positions)
    dst[0] = //Store the less significative half..
    dst[1] = //Store the more significative half..

    //My function
    print_To_Screen(dst);
}

我不知道如何访问结果的每一部分以将它们存储在我想要的内存块中。我是否有义务使用汇编指令进行乘法并存储结果，还是存在一种简单的方法？

Answer 1

只需按照建议使用__int128，大多数编译器都支持它：

__uint128_t mul64x64( uint64_t a, uint64_t b ) {
    return ((__uint128_t)a) * ((__uint128_t)a);
}

这将转换为 x64 架构上的单个指令乘法。

Answer 2

这是

高 qword ，您将在计算时遇到麻烦：

（a*2^32 + b） * （c*2^32 + d）

= a*2^32（c*2^32 + d） +

b（c*2^32 + d）

= a*c*2^

64 + （ad + bc）*2^32 + bd

粗体字为您提供了产品中无法用 64 位值表示并丢失的部分。