1

I need an algorithm that uses two 32-bit integers as parameters, and returns the multiplication of these parameters split into two other 32-bit integers: 32-highest-bits part and 32-lowest-bits part.

I would try:

uint32_t p1, p2; // globals to hold the result

void mult(uint32_t x, uint32_t y){
    uint64_t r = (x * y);

    p1 = r >> 32;
    p2 = r & 0xFFFFFFFF;

}

Although it works1, it's not guaranteed the existence of 64-bit integers in the machine, neither is the use of them by the compiler.

So, how is the best way to solve it?

Note1: Actually, it didn't work because my compiler does not support 64-bit integers.

Obs: Please, avoid using boost.

Rodrigo Siqueira
  • 375
  • 3
  • 15
  • You can treat each number and the product as a string and perform bruteforce school multiplication. Then divide the product into two parts accordingly. – Abhishek Bansal Nov 11 '13 at 07:03
  • It's valid, but I think there might be a faster and quite smarter way to do it. As I am simulating a processor, it needs to be as fast as possible. – Rodrigo Siqueira Nov 11 '13 at 07:06
  • Have you checked [this thread](http://stackoverflow.com/q/18425513/69809)? – vgru Nov 11 '13 at 09:07
  • Are platform-specific ways allowed? What compiler are you using and on what platform? – Matteo Italia Nov 11 '13 at 09:39
  • (I ask because on x86 the MUL instruction already does what you asked - it can take 32 bits operands and the 64-bit result is split in EDX:EAX, and I wouldn't be surprised if compilers provided intrinsics for this; the Win32 API even encapsulates this feature in a regular function) – Matteo Italia Nov 11 '13 at 09:45
  • @MatteoItalia Unhappily, I don't know in what platform the program will be executed. – Rodrigo Siqueira Nov 11 '13 at 13:32

4 Answers4

6

Just use 16 bits digits.

void multiply(uint32_t a, uint32_t b, uint32_t* h, uint32_t* l) {
    uint32_t const base = 0x10000;
    uint32_t al = a%base, ah = a/base, bl = b%base, bh = b/base;
    *l = al*bl;
    *h = ah*bh;
    uint32_t rlh = *l/base + al*bh;
    *h += rlh/base;
    rlh = rlh%base + ah*bl;
    *h += rlh/base;
    *l = (rlh%base)*base + *l%base;
}
AProgrammer
  • 51,233
  • 8
  • 91
  • 143
  • Perfect! No overflow found. – Rodrigo Siqueira Nov 11 '13 at 14:19
  • Probably I would add some conditional compilation directives to enable "real" 32->64 multiplication on platforms that support it. – Matteo Italia Nov 11 '13 at 15:03
  • @MatteoItalia I've heard that compilers MUST provide a way to execute 64-bit operations even though they are in 32-bit platform using `long long`. I'll try that and, if it doesn't work, I'll do what you've stated. – Rodrigo Siqueira Nov 12 '13 at 02:03
  • @RodrigoSiqueira, since C99, which also mandates int64_t. While long long had a longer existing practice beforehand, I somehow doubt that a compiler which provides a 64 bits long long and int32_t will not provide int64_t as that would just be a typedef in the same header than provide int32_t. – AProgrammer Nov 12 '13 at 06:31
  • 1
    You should REALLY be using &0xFFFF instead of %base and >>16 instead of /base. There's absolutely no reason for using % and / here instead, and I wouldn't expect or trust the compiler to do the change for you mostly when base isn't even declared as const. – Michel Rouzic Jul 27 '15 at 11:45
1

As I commented, you can treat each number as a binary string of length 32.

Just multiply these numbers using school arithmetic. You will get a 64 character long string.

Then just partition it.

If you want fast multiplication, then you can look into Karatsuba multiplication algorithm.

Abhishek Bansal
  • 12,589
  • 4
  • 31
  • 46
  • Actually, I have also manually tried this method before the question with 4-bit integers: `x = 0b1111` and `y = 0b1111`. I split it into four 2-bit integers: `x1 = x0 = y1 = y0 = 0b11`. Karatsuba has overflown in `((x1 + x0) * (y1 + y0))` as it would result `0b100100` and this cannot fit into a 4-bit integer. – Rodrigo Siqueira Nov 11 '13 at 13:50
  • @RodrigoSiqueira You will have to store the numbers as strings and then carry out the multiplication. – Abhishek Bansal Nov 11 '13 at 14:00
  • Ow yeah, I have forgotten of that detail. – Rodrigo Siqueira Nov 11 '13 at 14:02
1

This is the explanation and an implementation of the Karatsubas-Algorithm. I have downloaded the code and ran it several times. It seems that it's doing well. You can modify the code according to your need.

Deidrei
  • 2,125
  • 1
  • 14
  • 14
0

If the unsigned long type are supported, this should work:

void umult32(uint32 a, uint32 b, uint32* c, uint32* d)
{
  unsigned long long x = ((unsigned long long)a)* ((unsigned long long)b); //Thanks to @Толя
  *c = x&0xffffffff;
  *d = (x >> 32) & 0xffffffff;
}

Logic borrowed from here.

Roney Michael
  • 3,964
  • 5
  • 30
  • 45
  • unsigned long long x = (unsigned long long)(a*b); this is wrong, should be: unsigned long long x = ((unsigned long long)a)* ((unsigned long long)b); – Толя Nov 11 '13 at 08:10
  • 3
    Uhm, you relying on the availability of `unsigned long long`, while OP explicitly stated that it's not guaranteed. – Matteo Italia Nov 11 '13 at 09:38
  • @Толя Actually, this is exactly the first thing I have tried before the question. And, as @MatteoItalia and I said, 64-bit integers may not be available. My compiler's `unsigned long long` is 32-bit and `*d` will always be 0. – Rodrigo Siqueira Nov 11 '13 at 13:36
  • But what if the multiplication of a and b doesn't fit in x. This doesn't apply for numbers that would overflow. This only works for numbers that would already fit in ull. So, your answer is not efficient – mtk Sep 14 '15 at 08:39