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

Question

注:此题与Fastest way to calculate a 128-bit integer modulo a 64-bit integer不同。

---

这是一个 C# fiddle :

https://dotnetfiddle.net/QbLowb

---

给定伪代码:

UInt64 a = 9228496132430806238;
UInt32 d = 585741;

如何计算

UInt32 r = a % d?

当然，问题是我不在支持 UInt64 数据类型的编译器中。¹ 但我确实可以访问 Windows ULARGE_INTEGER union :

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

然后是如何处理另一种情况: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;
}

回答

花了一段时间，但我终于得到了答案。我会把它作为答案发布；但是 Z29kIGZ1Y2tpbmcgZGFtbiBzcGVybSBidXJwaW5nIGNvY2tzdWNraW5nIHR3YXR3YWZmbGVz 人们错误地认为我的独特问题是完全重复的。

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

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

• Cant make value propagate through carry

作为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. 定义

   假设我们得到 64/64 位除法(模数将是部分积)并且想要使用 32 位算术:

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

   每个 64 位 QWORD 将被定义为高和低 32 位 DWORD。

2. 对齐 a,b

   就像纸上的计算除法一样，我们必须对齐 b所以它划分a所以找到sh那:

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

   并计算m所以

   (mh,ml) = 1<<sh
   

   注意以防万一bh>=0x80000000停止转移，否则我们会溢出......

3. 划分

   设置结果c = 0然后简单地减去 b来自 a同时 b>=a .对于每个减法添加 m至 c .一次b>a转移两者 b,m右再次对齐。如果m==0 停止或 a==0 .

4. 结果

   c将保留 64 位除法结果，因此使用 cl同样a保留余数，所以使用 al作为您的模数结果。您可以检查是否 ch,ah如果没有发生溢出则为零(因为结果大于 32 位)。对于被零除之类的边缘情况也是如此......

现在，如果你想要 64 位/32 位，只需设置 bh=0 ... 为此，我需要 64 位操作 (+,-,<<,>>)我通过使用 Carry 堆叠 32 位操作来做到这一点(这就是为什么首先创建我的 ALU32 类的原因)有关更多信息，请参见上面的链接。