Binary GCD
(number/binary_gcd.hpp)

• View this file on GitHub
• Last update: 2021-08-21 15:46:09+09:00
• Include: #include "number/binary_gcd.hpp"

二つの整数の最大公約数を求める高速なアルゴリズムとして知られる Binary GCD の実装．Euclid の互除法によるアルゴリズムと異なり，2 以外の除算が登場しない．

使用例

long long a, b;
long long g = binary_gcd(a, b);

リンク

• Binary GCD algorithm - Wikipedia

Verified with

• number/test/binary_gcd.stress.test.cpp

Code

#pragma once

// CUT begin
template <typename Int> Int binary_gcd(Int x_, Int y_) {
    unsigned long long x = x_ < 0 ? -x_ : x_, y = y_ < 0 ? -y_ : y_;
    if (!x or !y) return x + y;
    int n = __builtin_ctzll(x), m = __builtin_ctzll(y);
    x >>= n, y >>= m;
    while (x != y) {
        if (x > y) {
            x = (x - y) >> __builtin_ctzll(x - y);
        } else {
            y = (y - x) >> __builtin_ctzll(y - x);
        }
    }
    return x << (n > m ? m : n);
}

#line 2 "number/binary_gcd.hpp"

// CUT begin
template <typename Int> Int binary_gcd(Int x_, Int y_) {
    unsigned long long x = x_ < 0 ? -x_ : x_, y = y_ < 0 ? -y_ : y_;
    if (!x or !y) return x + y;
    int n = __builtin_ctzll(x), m = __builtin_ctzll(y);
    x >>= n, y >>= m;
    while (x != y) {
        if (x > y) {
            x = (x - y) >> __builtin_ctzll(x - y);
        } else {
            y = (y - x) >> __builtin_ctzll(y - x);
        }
    }
    return x << (n > m ? m : n);
}

Back to top page