// Copyright (C) 2026 Kiyotsugu Arai
// SPDX-License-Identifier: LGPL-3.0-or-later

// IntGCD.hpp
// GCD (Greatest Common Divisor) and LCM (Least Common Multiple) operations for Int

#ifndef CALX_INT_GCD_HPP
#define CALX_INT_GCD_HPP

#include "IntBase.hpp"

namespace calx {

/**
 * @brief GCD and LCM operations for arbitrary-precision integers
 *
 * Provides efficient implementations of:
 * - Binary GCD (Stein's algorithm) - division-free, 30-50% faster for large integers
 * - Extended GCD - computes Bézout coefficients for modular arithmetic
 * - LCM - least common multiple using GCD
 */
class IntGCD {
public:
    /**
     * @brief Greatest Common Divisor (always returns positive result)
     *
     * Algorithm: Binary GCD (Stein's algorithm) - division-free
     * Performance: 30-50% faster than Euclidean GCD for multi-limb integers
     * Reference: Cohen "A Course In Computational Algebraic Number Theory" p.14
     *
     * Special cases:
     *   gcd(0, b) = |b|
     *   gcd(a, 0) = |a|
     *   gcd(0, 0) = 0
     *   gcd(NaN, x) = NaN
     *   gcd(∞, x) = NaN (undefined)
     *
     * @param a First integer
     * @param b Second integer
     * @return GCD as positive Int
     */
    static Int gcd(const Int& a, const Int& b);

    /**
     * @brief Least Common Multiple (always returns positive result)
     *
     * Formula: lcm(a, b) = |a * b| / gcd(a, b)
     * Optimization: Uses |a| * (|b| / gcd) to avoid intermediate overflow
     *
     * Special cases:
     *   lcm(0, x) = 0
     *   lcm(x, 0) = 0
     *   lcm(1, x) = |x|
     *   lcm(NaN, x) = NaN
     *   lcm(∞, x) = NaN (undefined)
     *
     * @param a First integer
     * @param b Second integer
     * @return LCM as positive Int
     */
    static Int lcm(const Int& a, const Int& b);

    /**
     * @brief Extended GCD: computes gcd(a, b) and Bézout coefficients
     *
     * Computes gcd(a, b) and coefficients x, y such that:
     *   a*x + b*y = gcd(a, b)
     *
     * Algorithm: Extended Euclidean algorithm
     * Reference: Serizawa "Elementary Number Theory in C" p.41
     *
     * Note: The Bézout coefficients (x, y) are not unique. This returns
     * one valid solution. Coefficients may have larger magnitude than inputs.
     *
     * Special cases:
     *   extgcd(a, 0) returns (|a|, sign(a), 0)
     *   extgcd(0, b) returns (|b|, 0, sign(b))
     *   extgcd(NaN, x) returns (NaN, NaN, NaN)
     *   extgcd(∞, x) returns (NaN, NaN, NaN)
     *
     * @param a First integer
     * @param b Second integer
     * @param x Output: Bézout coefficient for a
     * @param y Output: Bézout coefficient for b
     * @return GCD as positive Int
     */
    static Int extendedGcd(const Int& a, const Int& b, Int& x, Int& y);
};

} // namespace calx

#endif // CALX_INT_GCD_HPP