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+

Columbo

Wie kann eine Zahl eine Menge sein?

mgaeckler

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.

Ach stimmt, da war was.
Danke!

http://141.19.87.190/doku/c++/buecher/Vcppk/html/der_euklidische_algorithmus.html

wob

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!?

Fytch

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.

EOP

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+

mgaeckler

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.

mgaeckler

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