CODEWITHSUNDEEP
c++assemblymultiplicationbignummultiprecision
Hélder Gonçalves
Hélder Gonçalves

Reputation: 771

Multiplication with very large operands

I am implementing a multi-precision module, and at this moment I am stuck in the multiplication.

To do my algorithm I need to multiply two unsigned operands of 64 bits, using a Haswell microarchitecture, and store the result in a memory block. I'm doing an implementation using 'g++' and another more efficient using '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);
}

I don't know how to access to each half of the result to store them in the memory blocks that I want. Am I obligde to use assembly instructions to the multiplication and them to store the result, or exists an easy way?

Upvotes: 3

Views: 232

Answers (2)

ElderBug
ElderBug

Reputation: 6145

Just use __int128 as suggested, most compilers support it : 

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

This will translate to a single instruction multiplication on x64 architectures.

Upvotes: 4

user3703887
user3703887

Reputation:

It is the high qword that you will have trouble computing:

(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

The term in bold gives you the part of the product that you will be unable to represent in a 64-bit value and will be lost.

Upvotes: 0

Related Questions