How to calculate modulus of 64-bit unsigned integer?

Question

Note: This question is different from Fastest way to calculate a 128-bit integer modulo a 64-bit integer.

---

Here's a C# fiddle:

https://dotnetfiddle.net/QbLowb

---

Given the pseudocode:

UInt64 a = 9228496132430806238;
UInt32 d = 585741;

How do i calculate

UInt32 r = a % d?

The catch, of course, is that i am not in a compiler that supports the UInt64 data type.¹ But i do have access to the Windows ULARGE_INTEGER union:

typedef struct ULARGE_INTEGER {
   DWORD LowPart;
   DWORD HighPart;
};

Which means really that i can turn my code above into:

//9228496132430806238 = 0x80123456789ABCDE
UInt32 a = 0x80123456; //high part
UInt32 b = 0x789ABCDE; //low part
UInt32 r = 585741;     

How to do it

But now comes how to do the actual calculation. I can start with the pencil-and-paper long division:

       ________________________  
585741 ) 0x80123456  0x789ABCDE

To make it simpler, we can work in variables:

Now we are working entirely with 32-bit unsigned types, which my compiler does support.

u1 = a / r; //integer truncation math

v1 = a % r; //modulus

But now i've brought myself to a standstill. Because now i have to calculate:

v1||b / r

In other words, I have to perform division of a 64-bit value, which is what i was unable to perform in the first place!

This must be a solved problem already. But the only questions i can find on Stackoverflow are people trying to calculate:

a^b mod n

or other cryptographically large multi-precision operations, or approximate floating point.

Bonus Reading

• Microsoft Research: Division and Modulus for Computer Scientists
• https://stackoverflow.com/questions/36684771/calculating-large-mods-by-hand
• Fastest way to calculate a 128-bit integer modulo a 64-bit integer (unrelated question; i hate you people)

¹But it does support Int64, but i don't think that helps me

Working with Int64 support

I was hoping for the generic solution to the performing modulus against a ULARGE_INTEGER (and even LARGE_INTEGER), in a compiler without native 64-bit support. That would be the correct, good, perfect, and ideal answer, which other people will be able to use when they need.

But there is also the reality of the problem i have. And it can lead to an answer that is generally not useful to anyone else:

• cheating by calling one of the Win32 large integer functions (although there is none for modulus)
• cheating by using 64-bit support for signed integers

I can check if a is positive. If it is, i know my compiler's built-in support for Int64 will handle:

UInt32 r = a % d; //for a >= 0

Then there's there's how to handle the other case: a is negative

UInt32 ModU64(ULARGE_INTEGER a, UInt32 d)
{
   //Hack: Our compiler does support Int64, just not UInt64.
   //Use that Int64 support if the high bit in a isn't set.
   Int64 sa = (Int64)a.QuadPart;
   if (sa >= 0) 
      return (sa % d);

   //sa is negative. What to do...what to do.

   //If we want to continue to work with 64-bit integers,
   //we could now treat our number as two 64-bit signed values:
   // a == (aHigh + aLow)
   //       aHigh = 0x8000000000000000
   //       aLow  = 0x0fffffffffffffff
   //
   // a mod d = (aHigh + aLow) % d
   //         = ((aHigh % d) + (aLow % d)) % d //<--Is this even true!?

   Int64 aLow  = sa && 0x0fffffffffffffff;
   Int64 aHigh =       0x8000000000000000;

   UInt32 rLow  = aLow  % d; //remainder from low portion
   UInt32 rHigh = aHigh % d; //this doesn't work, because it's "-1 mod d"

   Int64 r = (rHigh + rLow) % d;

   return d;
}

Answer

It took a while, but i finally got an answer. I would post it as an answer; but Z29kIGZ1Y2tpbmcgZGFtbiBzcGVybSBidXJwaW5nIGNvY2tzdWNraW5nIHR3YXR3YWZmbGVz people mistakenly decided that my unique question was an exact duplicate.

UInt32 ModU64(ULARGE_INTEGER a, UInt32 d)
{
   //I have no idea if this overflows some intermediate calculations
   UInt32 Al = a.LowPart; 
   UInt32 Ah = a.HighPart;

   UInt32 remainder = (((Ah mod d) * ((0xFFFFFFFF - d) mod d)) + (Al mod d)) mod d;

   return remainder;
}

Fiddle

Answer 1

I just updated my ALU32 class code in this related QA:

• Cant make value propagate through carry

As CPU assembly independent code for mul,div was requested. The divider is solving all your problems. However it is using Binary long division so its a bit slover than stacking up 32 bit mul/mod/div operations. Here the relevant part of code:

void ALU32::div(DWORD &c,DWORD &d,DWORD ah,DWORD al,DWORD b)
    {
    DWORD ch,cl,bh,bl,h,l,mh,ml;
    int e;
    // edge cases
    if (!b ){ c=0xFFFFFFFF; d=0xFFFFFFFF; cy=1; return; }
    if (!ah){ c=al/b;       d=al%b;       cy=0; return; }
    // align a,b for binary long division m is the shifted mask of b lsb
    for (bl=b,bh=0,mh=0,ml=1;bh<0x80000000;)
        {
        e=0; if (ah>bh) e=+1;   // e = cmp a,b {-1,0,+1}
        else if (ah<bh) e=-1;
        else if (al>bl) e=+1;
        else if (al<bl) e=-1;
        if (e<=0) break;        // a<=b ?
        shl(bl); rcl(bh);       // b<<=1
        shl(ml); rcl(mh);       // m<<=1
        }
    // binary long division
    for (ch=0,cl=0;;)
        {
        sub(l,al,bl);           // a-b
        sbc(h,ah,bh);
        if (cy)                 // a<b ?
            {
            if (ml==1) break;
            shr(mh); rcr(ml);   // m>>=1
            shr(bh); rcr(bl);   // b>>=1
            continue;
            }
        al=l; ah=h;             // a>=b ?
        add(cl,cl,ml);          // c+=m
        adc(ch,ch,mh);
        }
    cy=0; c=cl; d=al;
    if ((ch)||(ah)) cy=1;       // overflow
    }

Look the linked QA for description of the class and used subfunctions. The idea behind a/b is simple:

1. definition

   lets assume that we got 64/64 bit division (modulus will be a partial product) and want to use 32 bit arithmetics so:

   (ah,al) / (bh,bl) = (ch,cl)
   

   each 64bit QWORD will be defined as high and low 32bit DWORD.

2. align a,b

   exactly like computing division on paper we must align b so it divides a so find sh that:

   (bh,bl)<<sh <= (ah,al)
   (bh,bl)<<(sh+1) > (ah,al)
   

   and compute m so

   (mh,ml) = 1<<sh
   

   beware that in case bh>=0x80000000 stop the shifting or we would overflow ...

3. divide

   set result c = 0 and then simply substract b from a while b>=a. For each substraction add m to c. Once b>a shift both b,m right to align again. Stop if m==0 or a==0.

4. result

   c will hold 64bit result of division so use cl and similarly a holds the remainder so use al as your modulus result. You can check if ch,ah are zero if not overflow occurs (as result is bigger than 32 bit). The same goes for edge cases like division by zero...

Now as you want 64bit/32bit simply set bh=0 ... To do this I needed 64bit operations (+,-,<<,>>) which I did by stacking up 32bit operations with Carry (that is the reason why my ALU32 class was created in the first place) for more info see the link above.