ggT, hohe Zahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:22 Mi 26.09.2012 | | Autor: | sissile |
| Aufgabe | | Berechne ggT(1187563,770809,537589) |
Hallo,
bei der Prüfung ist solch ein Bsp sehr wahrscheinlich. Da ich bei der Prüfung keinen Tachenrechner verwenden darf muss ich "rechnen am Papier" .
Wie löst man den ggT von großen Zahlen am schnellsten?
Ist es am besten ggT(1187563,770809,537589)= ggT(ggT(1187563,770809),537589) und dann jeweils den euklidischen Algorithmus anzuwenden.
oder ggT(1187563,770809,537589)=ggT(112385,233220,537589) =.. immer wieter zu vereinfachen mithilfe division mit rest durch den kleisnten Faktor?
Was geht in der Prüfung am schnellsten bzw. gibts von eurer Seite noch tipps dafür?
Liebe Grüße
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:36 Mi 26.09.2012 | | Autor: | leduart |
Hallo
schnell geht das nur, wenn du immer wieder Differenzen bildest, alos euklidscher Alg im Prinzip, aber gleich für beide
ggt(a,b,c)=ggt(a-rb,b-sc,a-tc) usw.
deine Reihenfolge geht natürlich auch.
Gruss leduart
|
|
|
| |
|
Hallo sissile,
ich bin genau der gegenteiligen Ansicht, die leduart vertritt:
berechne stur ggT(ggT(a,b),c) - das ist am sichersten und schnellsten, abgesehen von einigen quasi zufälligen Ausnahmen, die man angesichts der Aufgabenstellung aber sicher nicht entdeckt.
Probiers an Deinem Beispiel doch einmal aus. Wenn der Zeitunterschied nicht signifikant ist, dann ist es offenbar egal. Ansonsten dürftest Du Die einen Hinweis erarbeiten, was hier schneller zum Ziel führt.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:04 Mi 26.09.2012 | | Autor: | sissile |
Hallo.
Danke für eure Posts.
Ich muss nach einigen solchen beispielen auch sagen, dass "reverends Methode" mir auch schneller von der Hand geht.
Aber natürlich ist das Geschmacksache ;)
Liebe Grüße
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:04 Do 27.09.2012 | | Autor: | reverend |
Hallo sissile,
> Danke für eure Posts.
> Ich muss nach einigen solchen beispielen auch sagen, dass
> "reverends Methode" mir auch schneller von der Hand geht.
> Aber natürlich ist das Geschmacksache ;)
Geschmack einerseits, und andererseits hängt es eben auch davon ab, was man jeweils schneller kann. Das ist von Person zu Person ja auch verschieden. Deswegen kann die Entscheidung für eine Methode eben auch nur eine persönliche sein. Und im Einzelfall mag die Entscheidung dann sogar falsch sein, je nach Aufgabe. Das muss man halt riskieren.
Jedenfalls viel Erfolg damit!
Grüße
reverend
|
|
|
|
