与非常大的操作数相乘

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

就是你计算困难的高位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 位值表示并将丢失的部分。

Answer 2

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

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

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

与非常大的操作数相乘

Multiplication with very large operands

c++

assembly

multiplication

bignum

multiprecision