Mathematische AlgorithmenBeginner

Euklidischer Algorithmus (GGT)

Antiker Algorithmus aus etwa 300 v. Chr., der effizient den grossten gemeinsamen Teiler zweier ganzer Zahlen berechnet. Basiert auf dem Prinzip, dass GGT(a, b) = GGT(b, a mod b). Einer der altesten kontinuierlich verwendeten Algorithmen, der die Grundlage der Zahlentheorie, Kryptographie und Bruchvereinfachung bildet.

#mathematical#number-theory#ancient-algorithm#gcd-lcm

Complexity Analysis

Time (Average)

O(log min(a, b))

Expected case performance

Space

O(1)

Memory requirements

Time (Best)

O(log min(a, b))

Best case performance

Time (Worst)

O(log min(a, b))

Worst case performance

Input Numbers (positive integers)

Number A

Number B

Quick Presets:

Step: 1 / 0

Animation Speed500ms

SlowFast

Keyboard Shortcuts

Space Play/Pause← → StepR Reset1-4 Speed

Real-time Statistics

Algorithm Performance Metrics

Progress0%

Comparisons

Swaps

Array Accesses

Steps

1/ 0

Algorithm Visualization

Step 1 of 0

Initialize array to begin

Default

Comparing

Swapped

Sorted

Code Execution

Currently executing

Previously executed

Implementation

Related Algorithms

View all in Mathematische Algorithmen

Sieb des Eratosthenes

Beginner

Findet alle Primzahlen bis n, indem iterativ Vielfache markiert werden. Benannt nach Eratosthenes von Kyrene (ca. 276-194 v. Chr.).

O(n log log n)

O(n)

mathematicalprime-numbers

Start Learning

Pascalsches Dreieck

Beginner

Dreieckiges Array von Binomialkoeffizienten, bei dem jede Zahl die Summe der beiden direkt daruber liegenden Zahlen ist. Benannt nach Blaise Pascal (1623-1662), obwohl Mathematikern Jahrhunderte fruher bekannt. Demonstriert wunderschone mathematische Muster einschliesslich Binomialentwicklung, Kombinatorik und Verbindungen zu Fibonacci-Zahlen.

O(n²)

mathematicalcombinatorics

Start Learning

Erweiterter Euklidischer Algorithmus

Intermediate

Erweitert den Euklidischen Algorithmus, um ganze Zahlen x und y zu finden, die Bezouts Identitat erfullen: ax + by = GGT(a, b). Berechnet nicht nur den GGT, sondern findet auch die Koeffizienten der Linearkombinationen. Fundamental fur modulare Arithmetik, RSA-Kryptographie und das Losen linearer diophantischer Gleichungen.

O(log min(a, b))

O(1)

mathematicalnumber-theory

Start Learning

Back to Mathematische Algorithmen