C++ Community

hi, kann mir mal jemand diesen Code genau erklären, ich hab nämlich für eine Schulaufgabe nen ggt Funktion geschrieben nur meine eigenen brauchte ca. 4 sekunden länger als diese aus dem Internet:

unsigned int ggt(unsigned int A, unsigned int
{
int Rest;
if (A &&
{
while (Rest = A %
{
A = B;
B = Rest;
}
return B;
}
else return !(A || + A + B;
}

Ich versteh nicht sogenau was der da macht;)

Peter Piksa

unsigned int ggt(unsigned int A, unsigned int B)
{
int Rest;
if (A && B) // Wird geschaut ob A und B existieren
{
while (Rest = A % B) // Rest ergibt sich aus dem was übrich bleibt wenn man A immer durch B teilt
{
A = B; // Apfel = Birne *lol*
B = Rest; // is auch klar
}
return B; // er gibt B zurück
}
else return !(A || B) + A + B; // hier weis ich nicht genau was die negation soll.  :confused: 
}

wow, danke das war echt schnell ich denk nun blicke ich ein wenig durch

Gary

Original erstellt von Peter Piksa:
**
if (A && B)
**

Da wird geschaut, ob A oder B gleich 0 ist.

Hier die Erklärung der Negation:

else return !(A || B) + A + B

Dieser Fall tritt nur ein, wenn A oder B gleich Null sind.

Unter die Prämisse gilt: Der ggT ist gleich A + B

Ausnahme A + B = 0, Null ist kein Teiler. Die Abfrage !(A || gibt eins zurück,
sobald A und B Null sind. Ansonsten ist die Rückgabe der Abfrage Null, somit
beeinflusst sie die Addition nicht!

MfG

Oliver

Krösus

Dieses wiederholte Teilen mit Rest wird als "Euklidischer Algorithmus" bezeichnet.
[url] ]http://www.google.de/search?q=Euklidischer+Algorithmus&ie=UTF-8&oe=UTF-8&hl=de&btnG=Google-Suche&meta=lr%3Dlang_de[/url]

Gary

es gibt aber auch schnellere ansätze,
zB a%b, dann
b%a
...

1ntrud0r

Original erstellt von Gary:
**[quote]Original erstellt von Peter Piksa:
[qb]
if (A && B)
**

Da wird geschaut, ob A oder B gleich 0 ist. :D[/QB][/QUOTE]

eher anderstrum
da wird geschaut ob A und B true sind d.h das A und B ungleich 0 sind ...
0 == false ; alles andere == true

volkard

Original erstellt von Gary:
es gibt aber auch schnellere ansätze,
zB a%b, dann
b%a
...

und natürlich den binary gcd.

unsigned ggt(unsigned a,unsigned b)
{
    unsigned shift=0;
    for(;;)
    {
        if(a%2==0)
        {
            a/=2;
            if(b%2==0)
            {
                b/=2;
                ++shift;
            }
            else
            {
                while(a%2==0)
                    a/=2;
                break;
            }
        }
        else
        {
            while(b%2==0)
                b/=2;
            break;
        }
    }
    for(;;)
    {
        if(a>b)
        {
            a-=b;
            while(a%2==0)
                a/=2;
        }
        else
        {
            b-=a;
            if(b==0)
                return a<<shift;
            while(b%2==0)
                b/=2;
        }
    }
}

und später hab ich zu ner anderen aufgabe noch ein paar tricks gefunden, die man oben noch einbauen sollte.

int wpc45(int offset,int max)
{//stellt nur fest, ob offset und max teilerfremd sind.
    static int lastbitpos[256]=
    {
        8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
        5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
        6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
        5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
        7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
        5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
        6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
        5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
    };
    int a=max,b=offset;
    //binary gcd with minor changes
    if(((a|b)&1)==0)//if both are even
        return 0;//no need to calc gcd, i wanted only to know if they are coprime
    //there is no need to ensure odd parameters. its enough to remove "some" final zeros
    a>>=lastbitpos[a&255];
    b>>=lastbitpos[b&255];
    while(a!=b)
    {//with high probability a and b are odd
        //now the bigger number shrinks (perhaps only a litte bit)
        if(a>b) 
            a-=b;
        else 
            b-=a;
        //but it became even because a and b were odd
        //and now it will be divided at least by 2
        a>>=lastbitpos[a&255];
        b>>=lastbitpos[b&255];
    }
    return a==1;
}

Gary

Original erstellt von 1ntrud0r:
eher anderstrum
da wird geschaut ob A und B true sind d.h das A und B ungleich 0 sind ...
0 == false ; alles andere == true

ich habs so gemeint, dass man sich dagegen absichert, dass a oder b gleich 0 sind. (aber blöd ausgedrückt )