Skip to content

Instantly share code, notes, and snippets.

@pmj
Created May 11, 2012 16:31
Show Gist options
  • Save pmj/2660790 to your computer and use it in GitHub Desktop.
Save pmj/2660790 to your computer and use it in GitHub Desktop.
64-bit * 64-bit -> 128-bit unsigned integer long multiplication
#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;
}
@ell1e
Copy link

ell1e commented Sep 22, 2023

Could you possibly state what the licensing and/or origin of this code is? I would be interested in using it in a project.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment