Created
May 11, 2012 16:31
-
-
Save pmj/2660790 to your computer and use it in GitHub Desktop.
64-bit * 64-bit -> 128-bit unsigned integer long multiplication
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdint.h> | |
#include <assert.h> | |
#include <stdlib.h> | |
struct big64 | |
{ | |
uint32_t v[2]; /* num = v[0] + (v[1] << 32) - "little endian" */ | |
}; | |
typedef struct big64 big64_t; | |
struct big128 | |
{ | |
uint32_t v[4]; | |
}; | |
typedef struct big128 big128_t; | |
big128_t big128_mul(big64_t x, big64_t y) | |
{ | |
/* x * y = (z2 << 64) + (z1 << 32) + z0 | |
* where z2 = x1 * y1 | |
* z1 = x0 * y1 + x1 * y0 | |
* z0 = x0 * y0 | |
*/ | |
uint64_t x0 = x.v[0], x1 = x.v[1], y0 = y.v[0], y1 = y.v[1]; | |
uint64_t z0 = x0 * y0; | |
uint64_t z1a = x1 * y0; | |
uint64_t z1b = x0 * y1; | |
uint64_t z2 = x1 * y1; | |
uint32_t z0l = z0 & UINT32_MAX; | |
uint32_t z0h = z0 >> 32u; | |
uint64_t z1al = z1a & UINT32_MAX; | |
uint64_t z1bl = z1b & UINT32_MAX; | |
uint64_t z1l = z1al + z1bl + z0h; | |
uint64_t z1h = (z1a >> 32u) + (z1b >> 32u) + (z1l >> 32u); | |
z2 += z1h; | |
big128_t p = {{ z0l, z1l & UINT32_MAX, z2 & UINT32_MAX, z2 >> 32u }}; | |
return p; | |
} | |
int main() | |
{ | |
srand(0); | |
for (unsigned i = 0; i < 100000000; ++i) | |
{ | |
uint64_t a = (uint32_t)rand() | ((uint64_t)((uint32_t)rand()) << 32u); | |
uint64_t b = (uint32_t)rand() | ((uint64_t)((uint32_t)rand()) << 32u); | |
big64_t a_ = {{ a & UINT32_MAX, a >> 32u }}; | |
big64_t b_ = {{ b & UINT32_MAX, b >> 32u }}; | |
big128_t p_ = big128_mul(a_, b_); | |
__uint128_t p = (__uint128_t)a * (__uint128_t)b; | |
assert(p_.v[0] == (p & UINT32_MAX)); | |
assert(p_.v[1] == ((p >> 32u) & UINT32_MAX)); | |
assert(p_.v[2] == ((p >> 64u) & UINT32_MAX)); | |
assert(p_.v[3] == ((p >> 96u) & UINT32_MAX)); | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Could you possibly state what the licensing and/or origin of this code is? I would be interested in using it in a project.