Gcd.. Logisch?

08.01.2007, 07:35

Gcd.. Logisch?

Hallo,

Angenommen, ich möchte den größten gemeinsamen Teiler von 192.439.448.288.309.551 verschiedenen - nicht aufeinanderfolgenden Zahlen - bestimmen.

Ich bin mir im Moment nicht 100% sicher, ob ich $\begin{eqnarray*} a) \end{eqnarray*}$ richtige liege $\begin{eqnarray*} b) \end{eqnarray*}$ das die performanteste Angelegenheit ist. Deswegen mal mein Gedanke:

Ich fange an mit der kanonischen Primfaktorzerlegung der kleinsten Zahl $\begin{eqnarray*} a \end{eqnarray*}$ und erhalte $\begin{eqnarray*} a=\varphi_{\text{MERKER}}=p_1^c\ {p_2^d}\ p_3^e\ \text{...} \end{eqnarray*}$ Anschließend teile ich die nächstgrößere Zahl $\begin{eqnarray*} b \end{eqnarray*}$ durch jeden Primfaktor $\begin{eqnarray*} p_n^1 \end{eqnarray*}$ des "Merkers". Bleibt das Ergebnis der Division (1) durch $\begin{eqnarray*} p_n^1 \end{eqnarray*}$ ohne Rest, so ist $\begin{eqnarray*} b \end{eqnarray*}$ durch $\begin{eqnarray*} {p_n}^{x} \end{eqnarray*}$ teilbar. Ist der Exponent in $\begin{eqnarray*} {p_n}^{x} \end{eqnarray*}$ kleiner als der Exponent von $\begin{eqnarray*} p_n \end{eqnarray*}$ im "Merker", so wird der Exponent im Merker ausgetauscht. Ist er gleich oder größer, ignoriere ich das Ergebnis. Ist das Ergebnis der Division (siehe 1) nicht ohne Rest machbar, so hau ich $\begin{eqnarray*} p_n^{\text{bla}} \end{eqnarray*}$ aus dem Merker komplett raus. Der Vorgang wiederholt sich jetzt bis entweder alle Zahlen durchlaufen wurde oder es eben keinen ggT gibt ("Merker"=1).

Ist das i.O. oder falsch? Wenn i.O., gibt es eine bessere Lösung?

Danke schonmal.

Edit: Müll raus, siehe unten.

08.01.2007, 07:54

sqrt(2)

Auf diesen Beitrag antworten »

RE: Gcd.. Logisch?

Zitat:

Original von zt
Angenommen, ich möchte den größten gemeinsamen Teiler von 192.439.448.288.309.551 verschiedenen - nicht aufeinanderfolgenden Zahlen - bestimmen.

Kannst du mir was von deinem Arbeitsspeicher abgeben? Über 1,5 Exabyte scheinst du ja zu haben.

Zitat:

Original von zt
Ist das i.O. oder falsch? Wenn i.O., gibt es eine bessere Lösung?

Deine Notation ist verwirrend bis falsch, aber ich denke, du meinst das Richtige, dann funktioniert dein Algorithmus. (Es wäre vielleicht sinnvoller, wenn du Programmcode postest.) Das Laufzeitverhalten ist O(n), besser wird es nicht gehen. In der Praxis wäre es natürlich erwünscht, wenn du mit einer Zahl anfängst, die möglichst wenig unterschiedliche Primfaktoren hat. Eventuell lohnt es sich, vorher mal drüberzuschauen, ob du vielleicht eine Primzahl dabei hast.

08.01.2007, 08:10

Auf diesen Beitrag antworten »

Zitat:

Original von zt
so ist $\begin{eqnarray*} b \end{eqnarray*}$ durch $\begin{eqnarray*} {p_n}^{\frac{b}{{p_n^1}}} \end{eqnarray*}$ teilbar.

Das muss ein ganz neues Potenzgesetz sein, das hier zur Anwendung kommt. Erhelle bitte die Unerleuchteten!

08.01.2007, 09:09

Auf diesen Beitrag antworten »

RE: Gcd.. Logisch?

Zitat:

Original von sqrt(2)
Kannst du mir was von deinem Arbeitsspeicher abgeben? Über 1,5 Exabyte scheinst du ja zu haben.

Ich wollte damit nur sagen, dass es sehr, sehr viele Zahlen sind. Augenzwinkern

Zitat:

Original von zt
Deine Notation ist verwirrend bis falsch..

Das dachte ich mir. unglücklich

Zitat:

Original von sqrt(2)
Das Laufzeitverhalten ist O(n), besser wird es nicht gehen. In der Praxis wäre es natürlich erwünscht, wenn du mit einer Zahl anfängst, die möglichst wenig unterschiedliche Primfaktoren hat.

Kuhl.

(Was auch immer O(n) bedeutet.)

Zitat:

Original von Arthur Dent
Erhelle bitte die Unerleuchteten!

Da könnt ihr lange warten. smile

08.01.2007, 11:05

Auf diesen Beitrag antworten »

Na gut, dann werde ich deutlicher: Zumindest dieser Teil ist himmelschreiender Blödsinn - Beispiel:

Nur zwei Werte mit nur einem Primfaktor: $\begin{eqnarray*} a=3,b=9 \end{eqnarray*}$ .

Dann ist $\begin{eqnarray*} p_1=3 \end{eqnarray*}$ , und $\begin{eqnarray*} b \end{eqnarray*}$ ist offenbar durch $\begin{eqnarray*} p_1^1=p_1=3 \end{eqnarray*}$ teilbar. Nach deiner Aussage ist dann auch $\begin{eqnarray*} b \end{eqnarray*}$ durch $\begin{eqnarray*} p_1^{\frac{b}{p_1^1}}= 3^{\frac{9}{3}} = 3^3 = 27 \end{eqnarray*}$ teilbar, was ja wohl offensichtlich falsch ist.

08.01.2007, 11:09

Leopold

Auf diesen Beitrag antworten »

Mit gefühlter Wahrscheinlichkeit $\begin{eqnarray*} p=0{,}9999999368 \end{eqnarray*}$ ist der größte gemeinsame Teiler der Zahlen 1.

08.01.2007, 11:23

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Na gut, dann werde ich deutlicher: Zumindest dieser Teil ist himmelschreiender Blödsinn

Ich hab' doch zugegeben, dass es Blödsinn war und im Eingangspost habe ich es doch schon korrigiert.

Edit: Jetzt wo ich's nochmal lese.. mit Da könnt ihr lange warten. meinte ich, dass es in der Tat Unsinn ist und ich es nicht erklären kann. Sorry. *g*

08.01.2007, 11:35

Auf diesen Beitrag antworten »

Ok, zur Aufgabe: Du willst $\begin{eqnarray*} g = \operatorname{ggT}(a_1,\ldots,a_n) \end{eqnarray*}$ bestimmen.

Falls die Primfaktorzerlegung aller Zahlen $\begin{eqnarray*} a_1,\ldots,a_n \end{eqnarray*}$ bereits vorliegt (woher auch immer), dann ist dein Verfahren Ok.

Falls nicht, dann ist m.E. die naheliegende Variante bei weitem vorzuziehen:

Rekursion $\begin{eqnarray*} g_1 = a_1 \end{eqnarray*}$ und $\begin{eqnarray*} g_k = \operatorname{ggT}(g_{k-1},a_k) \end{eqnarray*}$ für $\begin{eqnarray*} k=2,\ldots,n \end{eqnarray*}$

Der ggT von diesen zwei Zahlen wird dabei wie üblich über den euklidischen Algorithmus (EA) bestimmt. Wie Leopold schon anmerkte, wird dann $\begin{eqnarray*} g_k \end{eqnarray*}$ wohl sehr rasch sehr, sehr klein werden, so dass der EA nur so durchrast.

Neue Frage »

Antworten »

Gcd.. Logisch?

Verwandte Themen