wie genau programmier i das GGT?

[negaH]

@evilseven,

den ggT = GCD = Greatest Common Divisor, kannst du so wie oben gezeigt auch auf größere Zahlen adaptieren. Der Algorithmus selber bleibt also gleich. Du benötigst also eine Bibliothek die es dir ermöglicht mit sehr großen Zahlen zu rechnen. Nun, da deine Frage davon ausging das du einen ggT() für sehr große Zahlen benötigst gehe ich mal davon aus das du schon eine solche "BigNum", "Large Integer" Library benutzt.

Der obige Algorithmus ist die einfachste Form des GCD, der euklidsche Algorithmus. Gute Large Integer Librarys nutzen einen anderen Algorithmus der nach Lehmer oder Sorensen arbeitet. Der euklidsche Algo. extrahtiert von rechts nach links, also vom LSB zum MSB der Zahlen. Die Methode nach Lehmer oder Sorenson arbeiten aber umgedreht, sie berechnen die Subprodukte von Oben nach Unten, sprich vom MSB zum LSB. Dadurch sind diese Verfahren weit effizienter. Sie bauen sozusagen eine Verhältnissgleichung der MSB's beider Zahlen zueinander auf und reduzieren dann beide Zahlen so lange bis der GCD gefunden wurde. Gerade mit sehr großen Zahlen führt dies zu einer drastischen Beschleunigung des GCD.

Gruß Hagen