V
Ganz ehrlich, hast du den Taschenrechner/Computer gezückt um mal schnell sicherheitshalber nachzuprüfen?
Klar. Der neue Casio Abiturrechner (Casio FX-991DE Plus) hat sogar GCD eingebaut. Und der liegt immer auf meinem Schreibtisch.
Solange die Zahlen so klein oder lieb sind, daß ich schnell Primfaktoren abspalten kann, mache ich das auch so. Bei größeren und unhandlichen Zahlen setze ich den euklidischen Algorithmus an.
Okay, aber wann sind für dich die Zahlen unhandlich?
Solange sie nur dreistellig sind, oder sind auch schon dreistellige Zahlen unhandlich wenn sie sich z.B. der 1000 annähern?
Hängt auch von den Zahlen ab. Schnelle Teilbarekeitsregeln habe ich bis 11. Also ist 221 schon kritisch (und böse). Aber es müßten ja Zähler UND Nenner so schrecklich böse sein.
Also (binary) gcd (angepaßt, auch mal zehnfache abziehen
Was meinst du mit gcd?
gcd = greates common divisor = größter gemeinsamer teiler = ggt
Und binary gcd = dieser Algo: http://en.wikipedia.org/wiki/Binary_GCD_algorithm
Wußte ja nicht, daß man den jetzt http://de.wikipedia.org/wiki/Steinscher_Algorithmus nennt.
Übrigens sind beide Behauptungen
Zu beachten ist, dass der steinsche Algorithmus nur dann richtig funktioniert, wenn vorzeichenbehaftete Integer verwendet werden. Der euklidische Algorithmus hingegen funktioniert auch mit vorzeichenlosen Integertypen.
Der steinsche Algorithmus ist auf heutigen Rechnern nur dann effizienter, wenn der Integertyp nicht in ein Register hineinpasst, beispielsweise bei 64-Bit Integerzahlen auf einem Rechner mit 32-Bit Registern. Umgekehrt ist der euklidische schneller, wenn der Integertyp vollständig in ein Register passt.
einfach falsch. Wikipedia eben.
267 123?
267-246=21!
246-210=36!
21 36 => 3
Wie kommst du auf die 210?
10*21 (weil 10* so flott geht, war das lecker)