<commit_before>import Foundation

public protocol EuclideanRing: Ring {
    var degree: Int {get}
    func euclideanDiv(rhs: Self) -> (q: Self, r: Self)
    static func /(lhs: Self, rhs: Self) -> Self
    static func %(lhs: Self, rhs: Self) -> Self
}

infix operator /% { associativity left precedence 150 }
public func /%<T: EuclideanRing>(lhs: T, rhs: T) -> (q: T, r: T) {
    return lhs.euclideanDiv(rhs)
}

public func gcd<T: EuclideanRing>(x: T, _ y: T) -> T {
    switch(x.degree, y.degree) {
    case (_, 0):
        return x
    case (0, _):
        return y
    case let (a, b) where a >= b:
        return gcd(x % y, y)
    default:
        return gcd(x, y % x)
    }
}
<commit_msg>improve gcd algorithm, add euclideanAlgorithm func.<commit_after>import Foundation

public protocol EuclideanRing: Ring {
    var degree: Int {get}
    func euclideanDiv(rhs: Self) -> (q: Self, r: Self)
    static func /(lhs: Self, rhs: Self) -> Self
    static func %(lhs: Self, rhs: Self) -> Self
}

infix operator /% { associativity left precedence 150 }
public func /%<T: EuclideanRing>(lhs: T, rhs: T) -> (q: T, r: T) {
    return lhs.euclideanDiv(rhs)
}

public func gcd<T: EuclideanRing>(x: T, _ y: T) -> T {
    switch x {
    case 0:
        return y
    default:
        return gcd(y % x, x)
    }
}

public func euclideanAlgorithm<T: EuclideanRing>(x: T, _ y: T) -> (q0: T, q1: T, r: T) {
    func gcd(x: T, _ y: T, _ q: [T]) -> (q: [T], r: T) {
        switch x {
        case 0:
            return (q, y)
        default:
            let res = y /% x
            return gcd(res.r, x, [res.q] + q)
        }
    }
    
    let result = gcd(x, y, [])
    
    typealias M = Matrix<T, TPInt_2, TPInt_2>
    let m = result.q.reduce(M.identity) { (m: M, q: T) -> M in
        m * M(-q, 1, 1, 0)
    }
    
    return (q0: m[1, 0], q1: m[1, 1], r: result.r)
}

{'fraction_non_alphanumeric': 0.157073695535234, 'fraction_numerical': 0.01237224314147391, 'mean_word_length': 2.206896551724138, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 23, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3745914', 'n_tokens_mistral': 770, 'n_tokens_neox': 713, 'n_words': 231}