如何使用__builtin_ctz加速二进制GCD算法?

问题描述

clang和GCC具有int __builtin_ctz(unsigned)函数.这将以整数形式计算尾随零. 有关此功能族的Wikipedia文章提到可以使用以下命令加速二进制GCD算法__builtin_ctz，但我不知道如何.

clang and GCC have a int __builtin_ctz(unsigned) function. This counts the trailing zeros in an integer. The Wikipedia article on this family of functions mentions that the binary GCD algorithm can be sped up using __builtin_ctz, but I don't understand how.

二进制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:

My suspicion is that I could use __builtin_ctz as follows:

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? 在GodBolt上查看到目前为止的代码.

Unfortunately this does not work yet. The program results in 4, when it should be 1. So what am I doing wrong? How can I use __builtin_ctz correctly here? See my code so far on GodBolt.

推荐答案

这是来自注释:

尽管尾部递归算法通常很优雅，但是迭代实现在实践中几乎总是更快. (现代编译器实际上可以在非常简单的情况下执行此转换.)

While tail-recursive algorithms are often elegant, iterative implementations are almost always faster in practice. (Modern compilers can actually perform this transform in very simple cases.)

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步骤通常实现为非常有效的无条件右移，例如 shr r32 ，以除以(2)-同时为(u)，(v)是奇数，因此|u - v|必须是偶数.

As mentioned, the |u - v| / 2 step is typically implemented as a very efficient, unconditional right shift, e.g., shr r32, to divide by (2) - as both (u), (v) are odd, and therefore |u - v| must be even.

这不是严格的必要，因为整理"步骤:u >>= __builtin_clz(u);将在下一次迭代中有效地执行此操作.

It's not strictly necessary, as the 'oddifying' step: u >>= __builtin_clz(u); will effectively perform this operation in the next iteration.

假设(u)或(v)具有随机"位分布，则(n)通过 tzcnt 尾随零的概率为〜(1/(2^n)).该说明是对 bsf (IIRC的Haswell之前的__builtin_clz的实现)的改进.

Supposing that (u) or (v) have a 'random' bit distribution, the probability of (n) trailing zeroes, via tzcnt, is ~ (1/(2^n)). This instruction is an improvement over bsf, the implementation for __builtin_clz prior to Haswell, IIRC.

这篇关于如何使用__builtin_ctz加速二进制GCD算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！