ggT effizient ermitteln

@ 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

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).

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 ;)

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

}