clang 和 GCC 有一个 int __builtin_ctz(unsigned)
功能。这会计算整数中的尾随零。 Wikipedia article on this family of functions提到可以使用 __builtin_ctz
加速二进制 GCD 算法,但我不明白如何。
sample implementation二进制 GCD 看起来像这样:
unsigned int gcd(unsigned int u, unsigned int v)
{
// simple cases (termination)
if (u == v)
return u;
if (u == 0)
return v;
if (v == 0)
return u;
// look for factors of 2
if (~u & 1) // u is even
if (v & 1) // v is odd
return gcd(u >> 1, v);
else // both u and v are even
return gcd(u >> 1, v >> 1) << 1;
if (~v & 1) // u is odd, v is even
return gcd(u, v >> 1);
// reduce larger argument
if (u > v)
return gcd(u - v, v);
return gcd(v - u, u);
}
我怀疑我可以使用 __builtin_ctz
如下:constexpr unsigned int gcd(unsigned int u, unsigned int v)
{
// simplified first three ifs
if (u == v || u == 0 || v == 0)
return u | v;
unsigned ushift = __builtin_ctz(u);
u >>= ushift;
unsigned vshift = __builtin_ctz(v);
v >>= vshift;
// Note sure if max is the right approach here.
// In the if-else block you can see both arguments being rshifted
// and the result being leftshifted only once.
// I expected to recreate this behavior using max.
unsigned maxshift = std::max(ushift, vshift);
// The only case which was not handled in the if-else block before was
// the odd/odd case.
// We can detect this case using the maximum shift.
if (maxshift != 0) {
return gcd(u, v) << maxshift;
}
return (u > v) ? gcd(u - v, v) : gcd(v - u, u);
}
int main() {
constexpr unsigned result = gcd(5, 3);
return result;
}
不幸的是,这还不起作用。程序的结果是 4,什么时候应该是 1。那么我做错了什么?我如何使用 __builtin_ctz
在这里正确吗? See my code so far on GodBolt .
最佳答案
这是我来自 comments 的迭代实现:
虽然尾递归算法通常很优雅,但实际上迭代实现几乎总是更快。 (现代编译器实际上可以在非常简单的情况下执行这种转换。)
unsigned ugcd (unsigned u, unsigned v)
{
unsigned t = u | v;
if (u == 0 || v == 0)
return t; /* return (v) or (u), resp. */
int g = __builtin_ctz(t);
while (u != 0)
{
u >>= __builtin_ctz(u);
v >>= __builtin_ctz(v);
if (u >= v)
u = (u - v) / 2;
else
v = (v - u) / 2;
}
return (v << g); /* scale by common factor. */
}
如前所述,|u - v| / 2
step 通常被实现为非常有效的无条件右移,例如, shr r32
, 除以 (2)
- 作为两者 (u)
, (v)
是奇数,因此 |u - v|
必须是均匀的。这不是绝对必要的,因为“奇怪”步骤:
u >>= __builtin_clz(u);
将在下一次迭代中有效地执行此操作。假设
(u)
或 (v)
具有“随机”位分布,概率为 (n)
尾随零,通过 tzcnt
, 是 ~ (1/(2^n))
.该指令是对 的改进bsf
, 执行为 __builtin_clz
在 Haswell 之前,IIRC。
关于c++ - 如何使用 __builtin_ctz 加速二进制 GCD 算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/63604914/