Das deutsche Python-Forum

Code: Alles auswählen

def ggT(x, y):
    "groesster gemeinsamer Teiler zweier Zahlen"
    try:
        x, y = (y, x % y) if x > y else (x, y % x)
        x, y = (y, x % y)
        x, y = (y, x % y)
        x, y = (y, x % y)
        x, y = (y, x % y)
        x, y = (y, x % y)
        x, y = (y, x % y)
        x, y = (y, x % y)
        x, y = (y, x % y)
        x, y = (y, x % y)
        x, y = (y, x % y)
        raise ValueError()
    except ZeroDivisionError:
        return x

Code: Alles auswählen

#include <cassert>
#include <cstddef>
#include <cstdint>

#include <algorithm>
#include <bit>
#include <iostream>
#include <limits>
#include <numeric>
#include <type_traits>

// https://github.com/emil-e/rapidcheck
#include <rapidcheck.h>

template<size_t N, typename T>
constexpr auto gcd_impl(T const a, T const b) -> T {
    if constexpr (N == 0) {
        assert(false);  // unreachable
    }
    else {
        if (a == 0) {
            return b;
        }
        else if (b == 0) {
            return a;
        }
        else if (a % 2 == 0 and b % 2 == 0) {
            return 2 * gcd_impl<N - 1>(a / 2, b / 2);
        }
        else if (a % 2 == 0) {
            return gcd_impl<N - 1>(a / 2, b);
        }
        else if (b % 2 == 0) {
            return gcd_impl<N - 1>(a, b / 2);
        }
        else {
            using std::min;
            return gcd_impl<N - 1>((a > b ? a - b : b - a) / 2, min(a, b));
        }
    }
}

// Calculate the GCD of `a` and `b` using Stein’s algorithm, for all unsigned
// numeric types and without using loops or recursion.
template<typename T>
constexpr auto gcd(T const a, T const b) -> T {
    return gcd_impl<std::numeric_limits<T>::digits * 2 + 1>(a, b);
}

auto main() -> int {
    rc::check(
        "gcd on uint64_t",
        [](std::uint64_t const a, std::uint64_t const b) {
            std::cout << a << ' ' << b << ' ' << std::gcd(a, b) << '\n';
            RC_ASSERT(gcd(a, b) == std::gcd(a, b));
            static_assert(std::is_same_v<decltype(gcd(a, b)), decltype(std::gcd(a, b))>);
        }
    );
}

Code: Alles auswählen

#!/usr/bin/env python3

import math
import sys

from hypothesis import given
from hypothesis import settings
from hypothesis.strategies import integers

__getattr__ = lambda name: (
    gcd_impl_for(int(name.rsplit("_")[-1]))
    if name.startswith("gcd_impl_")
    else name.raise_AttributeError
)

gcd_impl_for = lambda n: lambda a, b: (
    lambda next_impl=getattr(sys.modules[gcd_impl_for.__module__], f"gcd_impl_{n + 1}"): (
        b if a == 0
        else a if b == 0
        else 2 * next_impl(a // 2, b // 2) if a % 2 == 0 and b % 2 == 0
        else next_impl(a // 2, b) if a % 2 == 0
        else next_impl(a, b // 2) if b % 2 == 0
        else next_impl(abs(a - b), min(a, b))
    )
)()

gcd = getattr(sys.modules[__name__], "gcd_impl_0")


@given(a=integers(min_value=0), b=integers(min_value=0))
@settings(max_examples=1_000)
def test_gcd(a, b):
    assert gcd(a, b) == gcd(b, a)
    assert gcd(a, b) == math.gcd(a, b)


main = lambda: print(gcd(24, 16))


if __name__ == "__main__":
    main()