Optimierung einer kleinen Funktion



  • Moin,

    folgendes Problem:

    "Gesucht ist der größtmögliche Teiler (C) von einer Menge (A) mit dem Maximum (B) ohne Rest."

    Meine Lösung funktioniert, ist aber zu langsam:

    unsigned long int NennerMax(unsigned long int A, unsigned long int B){
    	unsigned long int C=B;
    	while(((A/C)*C)!=A){
    		--C;
    	}
    	return C;
    }
    

    Bitte um Optimierungsvorschläge.Danke!

    Mathe4+


  • Mod

    Wie kann eine Zahl eine Menge sein?



  • Mathe4+ schrieb:

    Moin,

    folgendes Problem:

    "Gesucht ist der größtmögliche Teiler (C) von einer Menge (A) mit dem Maximum (B) ohne Rest."

    Meine Lösung funktioniert, ist aber zu langsam:

    unsigned long int NennerMax(unsigned long int A, unsigned long int B){
    	unsigned long int C=B;
    	while(((A/C)*C)!=A){
    		--C;
    	}
    	return C;
    }
    

    Bitte um Optimierungsvorschläge.Danke!

    Mathe4+

    Benutze den Modulo-operator.





  • Dein Algorithmus oben berechnet aber nicht den ggT, sondern den größten Teiler von A, der kleinergleich B ist.

    Also wenn A=100 und B=53, dann ist der ggT davon 1 (53 ist prim).
    Du bekommst oben aber 50 raus.

    Da die Ursprungsfragestellung unklar ist (siehe Anmerkung von Arcoth), kann ich hier nix weiter sagen (ich meinem entfernten Post hatte ich auf den ggT verlinkt, bis mir aufgefallen ist, dass du ggf. was anderes möchtest).



  • Ok, A ist eine Zahl.

    Den Ggt suche ich nicht. Dachte das ist nur der Schlüssel zur Lösung!?



  • Arcoth schrieb:

    Wie kann eine Zahl eine Menge sein?

    Von Neumann lässt grüssen. 🙂



  • Macht es denn einen großen Unterschied bei der Lösung. A=100 könnte doch eine Menge von 100 Elementen bedeuten die ich aufteilen möchte.



  • Wozu

    unsigned long int C=B;
    

    ?
    Entweder habe ich call by value nicht verstanden oder du.



  • Eigentlich ist es nur ein Minimalbeispiel und ich dachte es passt gut zur Frage.

    Danke für den Hinweis!



  • Ok, aktueller Stand:

    unsigned long int C(unsigned long int A, unsigned long int B){
        while(((A/B)*B)!=A){ 
            --B; 
        } 
        return B; 
    }
    


  • Scheint als wäre das nicht so simpel. Werde mich mal mit Primfaktorzerlegung beschäftigen.

    Hat noch jemand Stichworte zu Themen die bei einer Lösung helfen könnten?

    Danke.
    Mathe4+



  • Mathe4+ schrieb:

    Ok, aktueller Stand:

    unsigned long int C(unsigned long int A, unsigned long int B){
        while(((A/B)*B)!=A){ 
            --B; 
        } 
        return B; 
    }
    
    unsigned long int C(unsigned long int A, unsigned long int B){
        while(A%B){ 
            --B; 
        } 
        return B; 
    }
    


  • Super, danke!

    Hatte deinen ersten Hinweis nicht richtig verstanden.



  • Mathe4+ schrieb:

    Super, danke!

    Hatte deinen ersten Hinweis nicht richtig verstanden.

    Jetzt gibt es noch einen Optimierungstrick:

    - Das Divisionsergebnis durch den größten Teiler ist der kleinste Teiler und umgekehrt.
    - Die Differenz zweier benachbarter Teiler wird größer, wenn die Teiler größer werden.

    Die Suche nach 'nem kleinen Teiler ist daher schneller wie die Suche nach 'nem großen Teiler.

    Jetzt viel Spaß beim Entwerfen des notwendigen Algoritmus.

    VG


Log in to reply