(n*2-1)%p：当n和p为32位时避免使用64位

Question

考虑以下函数：

inline unsigned int f(unsigned int n, unsigned int p) 
{
    return (n*2-1)%p;
}

现在假设 n（和 p）大于 std::numeric_limits<int>::max()。

例如f(4294967295U, 4294967291U).

数学结果是7但是函数会return2，因为n*2会溢出。

那么解决方法很简单：我们只需要使用 64 位整数来代替。假设函数的声明必须保持不变：

inline unsigned int f(unsigned int n, unsigned int p) 
{
    return (static_cast<unsigned long long int>(n)*2-1)%p;
}

一切都很好。至少在原则上。问题是这个函数将在我的代码中被调用数百万次（我的意思是溢出版本），64 位模数比 32 位版本慢得多（例如参见 [=26=]）。

问题如下：是否有任何技巧（数学或算法）可以避免执行 64 位版本的模运算。使用这个技巧的 f 的新版本是什么？（保持相同的声明）。

注一：n > 0
注2：p > 2
注3：n可以低于p：n=4294967289U、p=4294967291U
注4：取模次数越少越好（3个32位取模太大了，2有意思，1肯定跑赢）
注意 5：当然，结果将取决于处理器。假设在最后一台 Xeon 可用的最后一台超级计算机上使用。

Answer 1

FWIW，这个版本似乎避免了任何溢出：

std::uint32_t f(std::uint32_t n, std::uint32_t p) 
{
    auto m = n%p;
    if (m <= p/2) {
        return (m==0)*p+2*m-1;
    }
    return p-2*(p-m)-1;
}

Demo。这个想法是，如果在 2*m-1 中发生溢出，我们可以使用 p-2*(p-m)-1，它通过将 2 与模加法逆相乘来避免这种情况。

Answer 2

我们知道p小于max，那么n % p小于max。它们都是无符号的，这意味着 n % p 是正数，并且小于 p。无符号溢出是明确定义的，所以如果 n % p * 2 超过 p，我们可以将其计算为 n % p - p + n % p，它不会溢出，所以合起来看起来像这样：

unsigned m = n % p;
unsigned r;
if (p - m < m) // m * 2 > p
    r = m - p + m;
else // m * 2 <= p
    r = m * 2;

// subtract 1, account for the fact that r can be 0
if (r == 0) r = p - 1;
else r = r - 1;
return r % p;

注意可以避免最后取模，因为我们知道r不会超过p * 2（最多是m * 2，而m不会'超过p), 所以最后一行可以改写为

return r >= p ? r - p : r

这使取模运算的次数为 1。

Answer 3

尽管我不喜欢处理 AT&T 语法和 GCC 的 "extended asm constraints"，但我认为这可行（它在我的有限测试中有效）

uint32_t f(uint32_t n, uint32_t p)
{
    uint32_t res;
    asm (
      "xorl %%edx, %%edx\n\t"
      "addl %%eax, %%eax\n\t"
      "adcl %%edx, %%edx\n\t"
      "subl , %%eax\n\t"
      "sbbl [=10=], %%edx\n\t"
      "divl %1"
      : "=d"(res)
      : "S"(p), "a"(n)
      : 
      );
  return res;
}

约束可能过严或错误，我不知道。好像有用。

这里的想法是做一个常规的32位除法，实际上是取一个64位被除数。它仅在商适合 32 位时才有效（否则会发出溢出信号），在这种情况下总是如此（p 至少 2，n 不为零）。除法之前的内容处理时间 2（溢出到 edx、"high half"），然后是 "subtract 1" 并可能借用。 "=d" 输出结果使它取余数。 "a"(n) 将 n 放入 eax（让它选择其他寄存器无济于事，该除法无论如何都会在 edx:eax 中进行输入）。 "S"(p) 可能是 "r"(p)（似乎有效）但我不确定是否可以信任它。

(n*2-1)%p：当n和p为32位时避免使用64位

(n*2-1)%p: avoiding the use of 64 bits when n and p are 32 bits

c++

algorithm

c++11

math

modulus