größten gemeinsamen Teiler ermitteln

[Gast]

Morgen,


kennt jemand eine Möglichkeit, den größten gemeinsamen Teiler von beliebig vielen Zahlen zu berechnen, so in der Art

int x = {1,2,5,7,13}  //Array variabler größe
calcggt(x) {...}

oder ist das vielleicht ein Verwendungszweck für die drei Punkte:


calcggt(int erstezahl ...) {...}

oder ist das in Java schon implementiert?



L-ectron-X hat diesen Beitrag am 27.07.2008 um 10:12 Uhr editiert.
Titel des Themas angepasst.

 

[DP]

beim der nächsten dämlichen überschrift ist der thread gelöscht.

 

[SlaterB]

zunächst mal gibts die iterative Variante:
erst ggt a von zwei Zahlen ausrechnen, dann den ggt von a zusammen mit der dritten Zahl ausrechnen usw.

wenn man das mit dem Euklidischen Algorithmus macht, dann ist der evtl. etwas unnötig langsam hinteinander,
Beispiel: ggt von 13, 17, 23

ggt von 13 und 17 ist 1,
bei der ggt-Berechnung von 1 und 23 muss man lange nur 1 abziehen:
22, 21, 20, .., 5, 4, 3, 2, 1

das Problem hat man generell bei diesem Algorithmus (ggt von 3 und 47498437498..)
aber bei obigen Beispiel ließe sich das etwas verbessern, wenn man den Euklidischen Algorithmus auf alle drei gleichzeitig anwendet,
ob und wie das genau geht, kann ich nicht sagen,

ich habs so gemacht: die kleinste Zahl nehmen und diese von den anderen beiden abziehen
->

13 17 23
13 4 10
9 4 6
5 4 2
3 2 2
1 2 0

ggt ist dann die kleinste Zahl != 0

mit paar anderen Beispielen hats bei mir auf dem Papier auch geklappt, aber ein Beweis ist das nicht


edit: ach, hab jetzt bei Wikipedia weitergelesen, gibt auch 'Modernen Euklidischen Algorithmus' mit Division statt nur Subtraktion
http://de.wikipedia.org/wiki/Euklidischer_Algorithmus
dann ist die normale ggt-Berechnung von immer nur zwei Zahlen vielleicht nicht langsamer als alle zusammen

 

[SebiB90]

also ich kenn den euklidischen algo so:

a = 12;
b = 6;
c = 0;
while(b!=0) {
c = a % b;
a = b;
b = c;
}

und nacher steht dann in a der ggt.

den hab ich jetzt mal bissel umgeändert und das sollte dann funktionieren:

public class GGT {

  public static int ggt(int[] zahlen) {
    int a = zahlen[0];
    int b = 0;
    for(int i = 1; i < zahlen.length; i++) {
      b = zahlen[i];
      while(b != 0) {
        b = a % (a=b);
      }
    }
    return a;
  }
  
  public static void main(String[] args) {
    System.out.println(ggt(new int[]{36,12,60}));
  }
}

 

[Gast]

@SebiB90

Habe deinen algorithmus mal gegen das hier laufen lassen und die Zeiten verglichen.

Bei kleinen arrays schneidet deine variante besser ab, bei großen
Arrays ab ca. 10 zahlen ist meine Variante etwa 1/3- 1/2 schneller.

public static int ggt2(int[] zahlen){ 
	 int a = zahlen[0];
	 int b = zahlen[1];
	 int ggt = ggt2(a,b);
	 for(int i =2 ; i<zahlen.length;i++){
		 ggt = ggt2(ggt,zahlen[i]);
	 }
	 return ggt;
  }
  public static int ggt2(int a,int b){
	  if(a==0){
		  return b;
	  }
	  if(b==0){
		  return a;
	  }
	  return ggt2(b%a,a);
  }

 

[blackMamba]

Arrays ab ca. 10 zahlen ist meine Variante etwa 1/3- 1/2 schneller.

Welcher Algo. schneller ist, kann man durch eine "einfache" Zeitmessung aber nicht genau sagen, da ja ständig unterschiedliche Threads im Hintergrund laufen, die auch Ressourcen des Computers verbrauchen.
Am besten vergleicht man Algorithmen, in denen man sich überlegt, wie viele Rechenschritte der Algorithmus benötigt.
Für den Worst- , Average -Case usw.

 

[Marco13]

Durch "einfache" zeitmessung nicht, aber durch "komplizierte" :wink:

Dass die Rekursive Variante so deutlich schneller ist, hätte ich aber auch nicht gedacht... ???:L Seltsam...

// Von [url]http://www.java-forum.org/de/viewtopic.php?t=72614&highlight=[/url]


public class GGT {

  public static void main(String[] args)
  {
      int input[] = new int[40];
      for (int i=0; i<input.length; i++)
      {
          input[i] = fib(i+5);
          System.out.println(input[i]);
      }
      for (int n=100000; n<=10000000; n*=10)
      {
          test(input, n);
          test2(input, n);
      }
  }


  private static int test(int input[], int n)
  {
      long before = System.currentTimeMillis();
      int sum = 0;
      for (int i=0; i<n; i++)
      {
          sum += ggt(input);
      }
      long after = System.currentTimeMillis();
      System.out.println("ggt  "+sum+" "+(after-before));
      return sum;
  }

  private static int test2(int input[], int n)
  {
      long before = System.currentTimeMillis();
      int sum = 0;
      for (int i=0; i<n; i++)
      {
          sum += ggt2(input);
      }
      long after = System.currentTimeMillis();
      System.out.println("ggt2 "+sum+" "+(after-before));
      return sum;
  }



  private static int fib(int n)
  {
    int i = 1;
    int c = 0;
    int d = 1;
    while (i <= n){
      int tmp = d;
      d = c + d;
      c = tmp;
      i = i + 1;
    }
    return c;
  }

  public static int ggt(int[] zahlen) {
    int a = zahlen[0];
    int b = 0;
    for(int i = 1; i < zahlen.length; i++) {
      b = zahlen[i];
      while(b != 0) {
        b = a % (a=b);
      }
    }
    return a;
  }


  public static int ggt2(int[] zahlen){
    int a = zahlen[0];
    int b = zahlen[1];
    int ggt = ggt2(a,b);
    for(int i =2 ; i<zahlen.length;i++){
       ggt = ggt2(ggt,zahlen[i]);
    }
    return ggt;
  }
  public static int ggt2(int a,int b){
     if(a==0){
        return b;
     }
     if(b==0){
        return a;
     }
     return ggt2(b%a,a);
  }
}

ggt  100000 141
ggt2 100000 78
ggt  1000000 1328
ggt2 1000000 703
ggt  10000000 13219
ggt2 10000000 6531

 

[SlaterB]

deine 40 Test-Zahlen sind aber auch wenig sinnvoll,
da sind am Anfang 5, 8, 13 dabei, also ist sofort ggt = 1 klar und dann ist 701408733 % 1 vielleicht sehr effizient zu 0 zu rechnen

hmm, mit 40.000, 40.100, 40.200 gehts aber auch ähnlich schnell, das macht doch wenig Unterschied,
aber die Reihenfolge ist interessant, absteigend:

    public static void main(String[] args)
    {
        int input[] = new int[20];
        int start = 16777216;
        for (int i = 0; i < input.length; i++)
        {
            input[i] = start;
            start /= 2;
            System.out.println(input[i]);
        }
        for (int n = 100000; n <= 10000000; n *= 10)
        {
            test(input, n);
            test2(input, n);
        }
    }
->
16777216
8388608
4194304
2097152
1048576
524288
262144
131072
65536
32768
16384
8192
4096
2048
1024
512
256
128
64
32
ggt  3200000 62
ggt2 3200000 110
ggt  32000000 515
ggt2 32000000 1047
ggt  320000000 5172
ggt2 320000000 10563

 

[SlaterB]

hmm, die gleichen Zahlen:

absteigend sortiert:
ggt  3200000 62
ggt2 3200000 110
ggt  32000000 515
ggt2 32000000 1047
ggt  320000000 5172
ggt2 320000000 10563

aufsteigend sortiert:
ggt  3200000 94
ggt2 3200000 63
ggt  32000000 1000
ggt2 32000000 594
ggt  320000000 9578
ggt2 320000000 5875

ggt sortiert sie sich absteigend, ggt2 aufsteigend:
ggt  3200000 46
ggt2 3200000 63
ggt  32000000 547
ggt2 32000000 562
ggt  320000000 5203
ggt2 320000000 5579

 

[Marco13]

Waha :autsch: natürlich Mit jeweils zwei aufeinanderfolgenden Fibonacci-Zahlen erhält man zwar den Worst-Case-Fall für den Euklid, aber wenn erstmal die 1 dabei ist, ist das alles ziemlich für die Socken :roll: (Nächstes Mal: ERST denken )

Wenn überhaupt, dann müßte man dafür sorgen, dass jeweils der ggt von n und n+1 die Fibonacci-Zahl ist, die der Vorgänger von n+2 ist :bahnhof:

Das möge dann blackMamba übernhemen - genauso wie den Beweis, dass (ob?) das dann ein "globaler" Worst Case ist :wink:


So. Jetzt unternehm' ich erstmal was gegen meinen Koffeinmangel :meld:

 

[Guest]

dankeschön für eure Posts, haben mir sehr geholfen,

 

[blackMamba]

Das möge dann blackMamba übernhemen

Ich überleg mir das gleich mal, jetzt aber erst mal Grillen und dann mache ich mir dazu nochmal gedanken