如何计算64位无符号整数的模数？

Question

注意：此问题与计算128位整数模64位整数的最快方法不同。

---

这是一个 C# 的代码片段：

https://dotnetfiddle.net/QbLowb

---

给定伪代码：

UInt64 a = 9228496132430806238;
UInt32 d = 585741;

我该如何计算

UInt32 r = a % d?

当然，问题在于我所用的编译器不支持UInt64数据类型。¹但是我可以访问Windows ULARGE_INTEGER结构体。

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

这意味着我可以将上面的代码转换为：

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

如何实现

现在是如何进行实际计算的。我可以从纸笔长除法开始：

       ________________________  
585741 ) 0x80123456  0x789ABCDE

为了让它更简单，我们可以使用变量：

现在我们完全使用32位无符号类型，这是我的编译器支持的。

u1 = a / r; //整数截断数学

v1 = a % r; //取模运算

但现在我已经陷入了僵局。因为现在我必须计算：

v₁||b / r 换句话说，我必须执行64位值的除法运算，这正是我一开始无法执行的操作！

这肯定是一个已经解决的问题。但我在Stackoverflow上能找到的唯一问题都是人们试图计算：

a^b mod n

或其他密码学大型多精度运算，或近似浮点数。

额外阅读材料

Microsoft Research: 计算机科学家的除法和模数 https://stackoverflow.com/questions/36684771/calculating-large-mods-by-hand Fastest way to calculate a 128-bit integer modulo a 64-bit integer (不相关的问题；我恨你们这些人)

¹但是它支持Int64，但我认为这对我没有帮助

使用Int64支持

我希望有一种通用的解决方案来执行对ULARGE_INTEGER（甚至LARGE_INTEGER）进行模运算，而不需要本地64位支持的编译器。那将是正确、好、完美和理想的答案，其他人需要时也可以使用。

但是还有问题i的现实。这可能会导致一个通常对其他人无用的答案：

• 通过调用Win32大整数函数之一作弊（尽管没有模数函数）
• 通过使用有符号整数的64位支持来作弊

我可以检查a是否为正。如果是，我知道我的编译器内置的Int64支持将处理：

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

接下来是如何处理另一种情况：a为负数

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;
}

回答

花了一些时间，但我终于得到了答案。我会将其发布为答案；但是，由于某些人错误地认为我的独特问题是精确重复的，所以他们阻止了我。

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;
}

小提琴

- Ian Boyd

---

问题中的 d 是否总是32位？ - John Coleman

你能不能将 a 分成两半：上下两部分，一部分大于 Int64_MAX，另一部分小于等于 Int64_MAX，然后将它们转换为 Int64 类型，分别进行除法运算并存储余数，最后将两个余数相加并计算出最终的余数？ - fejese

@JohnColeman 是的，就这个问题而言，您可以假设 d 是32位的。这意味着模数（即余数）也将是32位的。 - Ian Boyd

请注意，如果您的大整数具有高位hi和低位lo，则a = 2^32 * hi + lo，其余数为(pow(2,16)%d* pow(2,16)%d * hi %d + lo%d)%d。如果您能找到一种不会溢出的模乘法方法，那么这应该可以解决问题。我不太明白您编辑的逻辑。如果UInt32 r = a％d; //对于a> = 0总是有效的吗？如果2 ^ 63 <a <2 ^ 64，似乎您会遇到麻烦 - John Coleman

@JohnColeman 这是因为我将 UInt64 强制转换为 Int64 - 有符号整数。如果它没有触发符号位（即如果 UInt64 中的高位清除），那么我可以在编译器中使用有符号支持。 - Ian Boyd

@IanBoyd 我同意这不是一个完全的重复，但我认为通过说明使用的语言或可接受的答案语言，可以改进问题。或者，如果想要从特定的语言抽象出来，可以使用哪些操作（例如，是否有 mulhi 功能，或返回完整双宽乘积的乘法操作；是否支持 任何 64位操作或严格为 Uint32 操作；是否有“计数前导零”操作可用）？例如，这将有助于通过牛顿拉弗森实现。 - njuffa

Answer 1

我刚刚在这个相关的QA中更新了我的ALU32类代码：

• 无法使值通过进位传播

由于需要为 CPU 汇编程序编写独立的mul,div代码，因此除法器可以解决所有问题。不过它使用二进制长除法，所以比堆叠32位的mul/mod/div操作要慢一些。以下是相关代码部分:

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
    }

请查看链接的QA以了解该类及其使用的子函数的描述。 a/b 的背后思想很简单：

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...

现在，如果您想要64位/32位，只需设置bh=0... 为此，我需要64位运算（+、-、<<、>>），我通过使用带有Carry的32位操作堆叠来实现这些运算（这就是为什么我的ALU32类首次被创建的原因），有关更多信息，请参见上面的链接。

- Spektre