ggt



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



  • 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



  • 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



  • 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]



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



  • 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 🙄



  • 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;
    }
    


  • 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 🙄 )


Anmelden zum Antworten