Wie findet ihr ohne Computer/Taschenrechner am schnellsten den größten gemeinsammen Teiler (GGT) eines Bruches?
-
Mal angenommen ihr habt nen Bruch wie:
267/123 und nun soll ohne Hilfsmittel gekürzt werden, ihr habt nur nen Stift und Papier zur Verfügung.
Zum kürzen braucht ihr natürlich den GGT. Wie findet ihr den nun am schnellsten ohne Hilfsmittel?
-
Euklidischer Algorithmus?
-
eueueu schrieb:
Euklidischer Algorithmus?
Den gehst du im Kopf durch oder wie?
-> ohne Computer/Taschenrechner
-
Effizienz b. Kopfrechnen schrieb:
Mal angenommen ihr habt nen Bruch wie:
267/123 und nun soll ohne Hilfsmittel gekürzt werden, ihr habt nur nen Stift und Papier zur Verfügung.
Zum kürzen braucht ihr natürlich den GGT. Wie findet ihr den nun am schnellsten ohne Hilfsmittel?
Hängt von den konkreten Zahlen ab.
Hier:
Die 123 "leuchtet" und ruft 3!
123/3=61
Die 61 riecht prim.
267 ist durch 3 teilbar (hatte ich vorhin übersehen).
=>3.
(Weil 3*irgendwas/3*primzahl gekürzt ergibt irgendwas/primzahl und irgendwas hier kaum ein Vielfaches von 61 sein wird.)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.
Also 3813/4743...
Nö, das geht ja gar nicht. Und ich bin nicht vom wilden Watz gebissen und teste alle denkbaren Primteiler hier bis sqrt(3813). Mhhm, sqrt(1000)≈=32. Also sqrt(4000)≈62. Ach nöö, Dividieren ist ätzend.
Also (binary) gcd (angepaßt, auch mal zehnfache abziehen oder wie hier vierfache, solange es leicht geht, denn Multiplizieren ist seliger als Dividieren: Der Algo verzeiht es, wenn man bei Dividieren auch mal falsch liegt *einself*).
3813 4743?
4743-3813=930!3813 930?
(4*930=3720)
3813-3720=93!930 93?
93.Daran hätte ich mich totdividiert, bis ich die 31 gefunden hätte.
Ich lege mich mal absichtlich falsch beim Dividieren (Raten).
3813 4743?
Erste Ratung: 1, da kann man nix falsch machen.
4743-3813=930!(Ab jetzt führe ich alle bisherigen Zahlen mit, denn manchmal ist die eine größere zur neuen Zahl passender(, darf ich das überhaupt?)).
4743 3813 930?
Ratung 5.
(5*930=4650)
4650-3818=Ach nöö, zu schwierig
4743-4650=93.4743 3813 930 93
930 teilt 93 und klappe zu.Und nochmal das Eingangsbeispiel. Und Aufschreibung geändert. Da ich eh jede Zahl nehmen darf, brauche ich sie auch nicht zu sammeln, sie stehen ja da. Normalerweise nehme ich die beiden kleinsten, aber ich lunse kurz rauf ob es was saugut passendes gibt. Und ich darf eigentlich nicht alle Zahlen anschauen. Oder doch, muss aber dann sichergehen, den kleinsten zu finden, was bei handlichen Zahlen wohl noch geht. Bei noch größeren Zahlen muß man wohl sich auf zwei Zahlen beschränken.
267 123?267-246=21!
246-210=36!
21 36 => 3
Beispiel, wo man nicht mehr als 2 Zahlen führen darf:
1024 101?
1024-101=923!
1024 923 101?
923-101=802!1024-802=222...=>2
Da muß man dann noch die 2 gegen die beiden Eingangszahlen testen. Was ist besser? Sich auf 2 Zahlen beschränken oder am Ende nochmal testen?
-
volkard schrieb:
267 ist durch 3 teilbar (hatte ich vorhin übersehen).
Ich hab's gesehen und wollte schon was dazu schreiben, aber beim zitieren war es dann schon korrigiert.
Ganz ehrlich, hast du den Taschenrechner/Computer gezückt um mal schnell sicherheitshalber nachzuprüfen?
Kannste schon zugeben, geht hier ja um die Machbarkeit, ob man im Kopf so etwas schnell, effizient, einfach und fehlerfrei als Laie hinbekommt ohne jetzt der absolute Kopfrechner sein zu müssen.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?Also (binary) gcd (angepaßt, auch mal zehnfache abziehen
Was meinst du mit gcd?
267 123?
267-246=21!
246-210=36!
21 36 => 3
Wie kommst du auf die 210?
Beispiel, wo man nicht mehr als 2 Zahlen führen darf:
1024 101?
1024-101=923!
1024 923 101?
923-101=802!1024-802=222...=>2
Da muß man dann noch die 2 gegen die beiden Eingangszahlen testen. Was ist besser? Sich auf 2 Zahlen beschränken oder am Ende nochmal testen?[/quote]
-
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 BehauptungenZu 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)