ggT mit reduce und lambda

[student001]

Hallo
ich möchte die Funktion ggT
def ggT(x, y):
"groesster gemeinsamer Teiler zweier Zahlen"
while y!=0:
if x<y:
x,y=y,x
else:
x=x%y
return x
ohne Rekursion und ohne while bzw. for Schleife schreiben.
Möchte nur lambda Ausdrücke und reduce verwenden. Kann mir jemand helfen?

[Dookie]

Hi student001,

ohne Schleife oder Recursion wirds wohl, schon vom Prinzip her, nicht gehen.


Gruß

Dookie

[WeberLars]

Es geht schon, ich weis es ist ziemlich spaet mit diesem Antwort aber für Andere könnte es noch interessant sein.
ggt = lambda a, b: ggt(b, a%b) if a%b else b
Beispiel: ggt(300, 105) 15

[Zizibee]

17 Jahre später...
Allerdings beinhaltet der Code eine Recursion, die eigentlich ausgeschlossen wurde.

[WeberLars]

Recursion OK. Übersehen. Der letzte Satz war:
... "Möchte nur lambda Ausdrücke und reduce verwenden."

Python 3.x reduce() ist ausgelagert, muss importieren.

Und 17 Jahre -wie schnell geht die Zeit?-
Habe ich darauf hingewiesen, das es für ein Antwort schon zu Spaet ist!!!

Die Rest ist nur mit 'lambda'. Ich bitte um Entschuldigung das ich überhaupt noch lebe.

[__blackjack__]

Mein Ansatz wäre: ``from math import gcd as ggT``. Wobei ich mir die unkonventionelle Umbenennung noch sparen würde.

[Sirius3]

Ohne Rekursion und ohne Schleifen ist das ziemlich unmöglich.
Schon relativ kleine Zahlen benötigen viele Schritte:

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

Der Code funktioniert nicht für ggT(144, 233).

[narpfel]

Mit dem steinschen Algorithmus kann man das in C++ relativ einfach ohne Schleifen und Rekursion allgemeingültig für alle Zahlen schreiben:

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))>);
        }
    );
}

[Sirius3]

Was ist denn `gcd_impl<N - 1>` anderes als Rekursion?

[narpfel]

@Sirius3: `gcd_impl<N - 1>` ist eine andere Funktion als `gcd_impl<N>`. Und wenn ich eine andere Funktion aufrufe, kann das ja nicht Rekursion sein?

[__deets__]

Naja. Das ist schon haarspalterisch. Auch wenn die rekursion im Compiler und dessen Templateengine durchgeführt wird, bleibt es ein rekursiver Algorithmus. Auch in funktionalen Sprachen und deren pattern matching definierest du rekursive Algorithmen über ein generisches matching und spezialisierst den Rekursionsstart. Nur weil man das in imperativen Sprachen durch eine Fallunterscheidung in der gleichen Funktion tätigt, ist das keine andere Lösungstrategie.

[narpfel]

@__deets__: Das ist IMHO das gleiche wie zu sagen, dass die Implementierung von Integeraddition in Python/C++/... rekursiv ist, weil Integer in der Mathematik rekursiv definiert sind. Oder dass Sirius3s Implementierung eine Schleife benutzt, weil der euklidische Algorithmus eine Schleife benutzt und es egal ist, ob man die Schleife als Schleife hinschreibt oder ausrollt.

Wäre es für dich denn immer noch rekursiv, wenn ich alle `gcd_impl<N>` per Hand geschrieben hätte, anstatt sie vom Compiler schreiben zu lassen? Wenn ich eine Fold-Expression benutzt hätte?

[__deets__]

Da läuft sprichwörtlich ein Interpreter, der eine Funktion evaluiert. Rekursiv. Das der dann Code generiert, ist doch ein Detail.

Und die einfache Gegenfrage: wird eine rekursive Implementierung durch einen JIT entrollt wird, ist die dann nicht mehr rekursiv? Oder eine tail call optimization, die einen rekursiven Algorithmus essentiell zu einer for-Schleife (und ggf unrolling derselben) wandelt - auch kein rekursiver Algorithmus mehr?

Das ist als Lösungstrategie in meinen Augen etwas substantiell anderes. Du hast einen rekursiven Algorithmus programmiert. Der an bestimmte Randbedingungen hat, wie eben die festgezurrte Tiefe. Aber immer noch als Algorithmus rekursiv ist.

[narpfel]

@__deets__: Das sind gute Fragen. Wenn ich die Summe der ersten N natürlichen Zahlen mit der gaußschen Summenformel berechne, ist das dann eine Schleife? Wenn ich eine Schleife im Quelltext stehen habe und der Compiler optimiert daraus die gaußsche Summenformel, ist das dann eine Schleife? Und wenn ich das rekursiv schreibe?

Ich bin mir nicht sicher, ob es auf diese Fragen eine sinnvolle allgemeingültige Antwort gibt.

Ich bestreite nicht, dass ich einen rekursiven Algorithmus programmiert habe. Die Frage ist nur, ob das Programm Rekursion benutzt.

Wenn ich ein (rekursives) Python-Programm schreibe, das mir den C++-Code generiert: Ist der C++-Code dann rekursiv? Macht es einen Unterschied, ob der Code von einem Python-Programm generiert wird oder von einem C++-(Template-)Programm?

[__deets__]

Wie ja schon gesagt, wir sind hier im Haarspalterland. Aber ich würde “das Programm” hier schon vom Quelltext aus betrachten. Denn den legst du ja hier deiner Dozentin vor. Und nicht ein Kompilat. Und in dieser Beurteilung würde ich eben die Struktur betrachteten. Und keinen hoch ausgefeilten Optimierungsprozess. Der ist in einer anderen Vorlesung dran

[narpfel]

Hm. Ich bekomme dann wohl die andere Hälfte von dem Haar.

Um wenigstens der Anforderung „nur Lambdas“ gerecht zu werden:

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()

[WeberLars]

Mit Python3.9 ist das math Modul (import math) hat ein erweitertes gcd(var1, var2, var...) Funktion.
Wenn man Listen oder Tuplen als Argumente übergeben will, kommt eine Fehlermeldung raus.
Hier gibt es ein nützlicher Tip: List1 = [123, 456, 789]; math.gcd(*List1)

Mit lambda kann man es so schreiben mit Rücksicht auf if a or b == 0:
gcd = lambda a, b: gcd(b, a%b) if a%(b or 1) else b or a

(Wer Rechtschreibfehler findet darf es behalten!) schöne Grüsse