Tuesday, December 18, 2012

64-bit multiply with carry (MWC) for Intel x86-64


We don't have a uint128_t yet, but we can access rdx:rax. 

static uint64_t Q[R] = {}, c=1;

uint64_t mwc64() {
    uint64_t a = A;
    static int i = ~0;

    i = (i + 1) % R;
    asm(
        "mulq %%rdx\n\taddq %%rcx,%%rax\n\tadcq $0,%%rdx"
         : /*out*/ "=a" (Q[i]), "=d" (c)
         : /*in*/ "a" (Q[i]), "c" (c), "d" (a) );
    
    return Q[i]; 
}

and some values for A and R:

ARperiod (approx)
1844674407370955087412127
1844674407370954755922191
1844674407370953015042319
1844674407370952553082575
184467440737093986691621087
184467440737092195003222111
184467440737071951156424159
1844674407370921468812828255
18446744073688074570256216447

No comments: