www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik ggT effizient ermitteln


Autor: Neubi (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Johannes Slotta (johanness)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Im Prinzip sollte der Euklidsche Algorithmus 
(http://de.wikipedia.org/wiki/Euklidischer_Algorith...) 
gehen.

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

Autor: Netbird (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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 ...

Autor: Philipp Burch (philipp_burch)
Datum:

Bewertung
0 lesenswert
nicht 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 ;)

Autor: Philipp Burch (philipp_burch)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
In C sieht das dann etwa so aus (Ok, ist C++, aber das spielt hier ja 
wohl keine Rolle...):
#include <iostream>

using namespace std;

int CalcGCD(int a, int b) {
    int x, y, diff;

    do {
        if (a > b) {
            x = a; y = b;
        } else {
            x = b; y = a;
        }
        diff = x - y;
        a = y;
        b = diff;
    } while (diff != 0);

    return a;
}

int main()
{
    int a, b;

    cout << "--- ggT-Berechnung ---\n";
    cout << "Zahl 1: ";
    cin >> a;
    cout << endl;
    cout << "Zahl 2: ";
    cin >> b;
    cout << endl << endl;

    cout << "Der ggT von " << a << " und " << b << " ist ";
    cout << CalcGCD(a, b);

  return 0;
}

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.