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

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但该函数将返回 2 ，因为 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 位版本慢得多(例如参见 here)。

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

• 备注 1:n > 0
• 备注 2:p > 2
• 备注 3:n可以低于 p : n=4294967289U , p=4294967291U
• 注4:模运算次数越少越好(3个32位模太大了，2有意思，1肯定跑赢)
• 注意 5:当然，结果将取决于处理器。假设在最后一台可用的至强处理器上使用最后一台 super 计算机。

Answer 1

我们知道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。