Forum: Mikrocontroller und Digitale Elektronik ggT effizient ermitteln


von Neubi (Gast)


Lesenswert?

hey,

tüftle schon seit einiger zeit aber so richtig schlau werd ich nicht :(

-> wie kann ich am effizientesten den ggT von 4 ganzen zahlen mit einem 
mega32 ohne bibliotheken errechnen ???


.... am liebsten wär mir natürlich ein stückchen c-sourcecode :)


thx
Neubi

von Falk B. (falk)


Lesenswert?

@ Neubi

>-> wie kann ich am effizientesten den ggT von 4 ganzen zahlen mit einem
>mega32 ohne bibliotheken errechnen ???

Das läuft wohl auf eine Primfaktorzerlegung hinaus.

MFG
Falk

von Johannes S. (johanness)


Lesenswert?

Im Prinzip sollte der Euklidsche Algorithmus 
(http://de.wikipedia.org/wiki/Euklidischer_Algorithmus#Iterative_Variante) 
gehen.

Bei vier Zahlen führt man den Algo einfach dreimal durch: 
ggT(A,B,C,D)=>ggT(ggT(ggT(A,B),C),D).

von Netbird (Gast)


Lesenswert?

Eine gute Methode ist der Euklidische Algorithmus, der durch 
fortgesetzte Division arbeitet, Rekursion ist nicht erforderlich.

Beispiel: ggT(40,25) gesucht
Man dividiert ganzzahlig mit Rest nach folgendem Schema:

40: 25 = 1 R 15
25: 15 = 1 R 10
15: 10 = 1 R  5
10:  5 = 2 R  0  => Bei Rest 0 bricht der Algorithmus ab! Der letzte 
Divisor, also 5 ist der ggT!

Funktioniert auch, wenn die kleinere Zahl beim Start genommen wird.

Programmierung einfach zu machen mit einer WHILE - Schleife.
Division mit DIV - bzw. MOD Operator, je nach Programmiersprache ...

von Philipp B. (philipp_burch)


Lesenswert?

Falls du das auf einem kleinen Controller ohne Division in Hardware 
realisieren willst, gibt's da noch eine einfachere Alternative: Du 
nimmst den obigen Algo, verwendest allerdings anstatt der 
Modulo-Division nur Subtraktionen. Da nimmt die Schrittzahl natürlich 
zu, aber schneller als Divisionen in Software zu realisieren dürfte es 
allemal sein.

Beispiel mit obigen Zahlen:

40 - 25 = 15
25 - 15 = 10
15 - 10 = 5
10 - 05 = 5
05 - 05 = 0 -> ggT(40, 25) = 5

oder

54 - 29 = 25
29 - 25 = 4
25 - 04 = 21
21 - 04 = 17
17 - 04 = 13
13 - 04 = 9
09 - 04 = 5
05 - 04 = 1
04 - 01 = 3
03 - 01 = 2
02 - 01 = 1
01 - 01 = 0 -> ggT(54, 29) = 1

Zum Vergleich:

54 % 29 = 25
29 % 25 = 4
25 % 04 = 1
04 % 01 = 0 -> ggT(54, 29) = 1


Bei der Methode mit der Subtraktion ist halt zu beachten, dass IMMER die 
kleinere von der grösseren Zahl abgezogen wird.

EDIT: Hab' überlesen, dass du den mega32 verwenden willst. Meinen ersten 
Satz oben bis zum Doppelpunkt kannste somit streichen, der mega32 ist 
für mich so ein kleiner Controller ;)

von Philipp B. (philipp_burch)


Lesenswert?

In C sieht das dann etwa so aus (Ok, ist C++, aber das spielt hier ja 
wohl keine Rolle...):
1
#include <iostream>
2
3
using namespace std;
4
5
int CalcGCD(int a, int b) {
6
    int x, y, diff;
7
8
    do {
9
        if (a > b) {
10
            x = a; y = b;
11
        } else {
12
            x = b; y = a;
13
        }
14
        diff = x - y;
15
        a = y;
16
        b = diff;
17
    } while (diff != 0);
18
19
    return a;
20
}
21
22
int main()
23
{
24
    int a, b;
25
26
    cout << "--- ggT-Berechnung ---\n";
27
    cout << "Zahl 1: ";
28
    cin >> a;
29
    cout << endl;
30
    cout << "Zahl 2: ";
31
    cin >> b;
32
    cout << endl << endl;
33
34
    cout << "Der ggT von " << a << " und " << b << " ist ";
35
    cout << CalcGCD(a, b);
36
37
  return 0;
38
}

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.