Euclidean Algorithm GCD

Animierter euklidischer Algorithmus

Größter gemeinsamer Teiler.

Nützlich, um Brüche zu reduzieren

Sichtbarer euklidischer Algorithmus

GCD, auch bekannt als der größte gemeinsame Faktor (gcf), höchster gemeinsamer Faktor (hcf), größtes gemeinsames Maß (gcm) oder höchster gemeinsamer Teiler.

Dynamische und geometrische Darstellung des Algorithmus.

Rekursiver Algorithmus

Und Least Common Multiple, abgeleitet von GCD:

lcm (a, b) = a * b / gcd (a, b)

Nützlich, um den rekursiven Code des gcd (Euklidischer Algorithmus) zu verstehen: (Java)

int gcd (int m, int n) {

    if (0 == n) {

        Rückkehr m;

    }sonst{

        Rückkehr gcd (n, m% n);

    }

}

Geometrische Visualisierung hinzugefügt.

Algorithmus von Löwenzahn aus dem nahen Mathematischen Garten ausgeführt

Euklidische Algorithmusgeschichte:

("Der Pulverizer")

Der euklidische Algorithmus ist einer der ältesten allgemein gebräuchlichen Algorithmen.

Es erscheint in Euklids Elementen (ca. 300 v. Chr.), Speziell in Buch 7 (Propositionen 1-2) und Buch 10 (Propositionen 2-3).

Jahrhunderte später wurde der Euklid-Algorithmus sowohl in Indien als auch in China unabhängig voneinander entdeckt, hauptsächlich um diophantische Gleichungen zu lösen, die in der Astronomie auftraten und genaue Kalender lieferten.

Im späten 5. Jahrhundert beschrieb der indische Mathematiker und Astronom Aryabhata den Algorithmus als den "Pulverisierer", vielleicht wegen seiner Effektivität bei der Lösung von Diophantischen Gleichungen.

Danksagungen:

Joan Jareño (Creamat) (Zugabe von 1cm)