Container verschnellern....

minastaros

Arcoth schrieb:

Natürlich nur einmal, wieso um Himmels Willen sollte man ihn zweimal zählen

Weil ich zu sehr in meinem "Kopfprogramm" gedacht habe: Jeweils Teiler und Komplementär gleichzeitig abspeichern bzw. aufsummieren. Bei Quadratzahlen hätte man sowohl für Teiler als auch den quot die gleiche Zahl, was man beim on-the-fly-Aufsummieren dann abfangen müsste, um sie nur einmal zu zählen. Klar eigentlich, dass man sie bei einer Teilersumme nur einmal braucht. Nix für ungut.

volkard

Arcoth schrieb:

for(uint64_t teiler=2;teiler*teiler<=n;++teiler)
Wieso das Produkt in jedem Schleifendurchlauf berechnen? Wenn man schon diesen Weg einschlägt, kann man gleich die Regel anwenden, nach der Quadrate steigen, und wenigstens das Produkt durch eine Addition ersetzen. Am besten wäre allerdings isqrt .

Kein Problem. Bleibt aber bei O(n). Hab hier nur auf auf die Primfaktorenzerleging und das Aufspannen des Teilerverbands wert gelegt, das bringt erstmal am meisten bei wenig Mathe-Aufwand.

isqrt64 hätte ich erstmal anbieten müssen, ist ein eigenes thema. uint64_t ist größer als double. ::sqrt(double) reicht nicht. Eigenen Thread wert, wie ich sehe, haben wir hier noch keine gute Lösung.

die binomische formel wollte ich nicht noch reinmüllen, zumal bei modernen prozessoren, die nur 6 Takte pro multiplikation brauchen, der trick auch arg wenig dazu bringt.

camper

Arcoth schrieb:

Arcoth schrieb:

Man summiert dann auf, in dem man den Teiler plus das Gegenstück des Teilers (N/Teiler) addiert.

Die Frage ist: Wenn n eine Quadratzahl ist, wird dann der Wurzel-Teiler einmal oder zweimal gezählt?

Natürlich nur einmal, wieso um Himmels Willen sollte man ihn zweimal zählen
for(uint64_t teiler=2;teiler*teiler<=n;++teiler)
Wieso das Produkt in jedem Schleifendurchlauf berechnen? Wenn man schon diesen Weg einschlägt, kann man gleich die Regel anwenden, nach der Quadrate steigen, und wenigstens das Produkt durch eine Addition ersetzen. Am besten wäre allerdings isqrt .

Man kann auch das Divisionsergebnis des letzten Modulo heranziehen.

brak

Das Problem ist, Ich bat darum, nicht das Problem an sich zu lösen, das will ich machen, sondern mir nur an bestimmten Stellen Tips zu geben, die ich dann selber umsetzen kann. Mein Programm läuft jetzt auch, bestimmt nicht so schnell und elegant wie Euers und auch nicht zu so hohen Zahlen.....

Trotzdem vielen Dank

knivil

Von Dirk Louis C++ s. S. 251 "wegen des ständigen Speichervergrößernd im Hintergrund etwas ineffektiv"

'Staendig' ist falsch.

sondern mir nur an bestimmten Stellen Tips zu geben

1.) Mit dem Programm nicht alle Zahlen bis n testen sindern nur bis sqrt(n).
2.) Laufzeit vorher abschaetzen, d.h. wenn Zahlen bis 10000 Zeit x kosten, wieviel kosten dann Zahlen bis 1000000.
3.) Primzahlsieb mit prime-wheel benutzen (advanced).
4.) Geeignete Datenstruktur benutzen die effizienter als std::vector ist, beispielsweise ein Bitset.

Alle Faktoren finden ist aehnlich zu alle Primzahlen finden. Dort findest du weitere Anregungen.

volkard

brak schrieb:

Das Problem ist, Ich bat darum, nicht das Problem an sich zu lösen, das will ich machen, sondern mir nur an bestimmten Stellen Tips zu geben, die ich dann selber umsetzen kann. Mein Programm läuft jetzt auch, bestimmt nicht so schnell und elegant wie Euers und auch nicht zu so hohen Zahlen.....

Das fertige Programm musste sein, um Dir vorzumachen, wie unglaublich viel es bringt, sich über den Algo Gedanken zu machen und wie unglaublich wenig dagegen Mikro-Optimierungen bringen.
Oh, es hat noch viel Optimierungspotenzial, er schreit ein wenig nach Mikrooptimierung. Ist aber noch viel zu früh…

volkard

knivil schrieb:

4.) Geeignete Datenstruktur benutzen die effizienter als std::vector ist, beispielsweise ein Bitset.
Alle Faktoren finden ist aehnlich zu alle Primzahlen finden. Dort findest du weitere Anregungen.

stumpf ist Trumpf. Rot13, weil ich keinen Code mehr Zeigen darf.

#vapyhqr <vbfgernz>
#vapyhqr <irpgbe>

vag znva(){
	hvag32_g pbafg znk=10000000;
	fgq::irpgbe<hvag32_g> grvyre(znk);
	sbe(hvag32_g mnuy=1;mnuy<znk;++mnuy)
		sbe(hvag32_g ivry=mnuy;ivry<znk;ivry+=mnuy)
			grvyre[ivry]+=mnuy;
	sbe(hvag32_g mnuy=1;mnuy<znk;++mnuy)
		vs(grvyre[mnuy]==2*mnuy)
			fgq::pbhg<<"Qvr Mnuy "<<mnuy<<" vfg cresrxg.\a";
}

hustbaer

brak schrieb:

Das Problem ist, *snip*

Das Problem ist, dass du behauptet hast dass ein ganz bestimmter Befehl ( push_back ) das Bottleneck wäre, und dann nur nach Lösungen für dieses, nicht existente, " push_back -Problem" gefragt hast.
Das erzeugt bei einigen Leuten (z.B. mir ;)) ein wenig Unwillen/Mismut.

Du du aber anscheinend gar nicht so stur bist wie dich das hat erscheinen lassen, ein freundlich gemeinter Hinweis (und das ist ausnahmsweise mal kein Zynismus von mir, ich meine das echt nicht böse): wenn du dir wo nicht sicher bist, wie z.B. bei der push_back -Sache, dann lass dir das erstmal vom Forum bestätigen. Ala "ich will das optimieren und ich glaube die Problemstelle ist X - stimmt das soweit?".
Und wenn du nicht nur eine bestimmte Problemstelle entfernen willst, sondern allgemein nach Möglichkeiten suchst was zu verbessern/verschnellern, dann darfst du das auch gerne dazuschreiben

Zu breit/allgemein formulierte Fragen werden auch nicht gerne beantwortet. Dein Beispielcode war aber ausreichend klein und ausreichend spezifisch dass man da ohne weiteres "was kann man da noch verbessern" fragen kann. Ohne dass die Frage dadurch zu breit/unspezifisch wird.

----

So. Mathemässig kann ich dir nicht weiterhelfen, da haben andere hier viel viel viel mehr drauf als ich. Und da hast du ja auch schon einige gute Tips bekommen.

knivil

stumpf ist Trumpf. Rot13, weil ich keinen Code mehr Zeigen darf.

Bei Primzahlproblemen ist meine persoenliche Messlatte 10^10, erst dann wird es interessant. Deine Loesung kommt mit 10^9 nicht mehr klar, auch 10^8 kann bei Rechnern mit wenig Speicher problematisch sein. Wie nah aber vollkommene Zahlen jetzt dem Primzahlproblem sind, weiss ich nicht.

minastaros

brak schrieb:

Das Problem ist, ...

... dass hier Geeks unterwegs sind, die darin eine nette Denksportaufgabe für Zwischendurch sehen und dann gerne auch ein Stück schönen Code hinlegen. Dann kriegt ein TO auch mal etwas mehr als eine Antwort auf seine ursprüngliche Frage...
Sieh den Lerneffekt halt dieses Mal eher in den Nebenthemen, z.B. bei der Sache mit push_back vs. der Wahl des richtigen Algorithmus'/Designs. Ist langfristig wichtiger als zu wissen, wie man Teiler sucht.

Columbo

volkard schrieb:

Hab hier nur auf auf die Primfaktorenzerleging und das Aufspannen des Teilerverbands wert gelegt, das bringt erstmal am meisten bei wenig Mathe-Aufwand.

Ich würde liebend gern die größeren Zahlen mit einbeziehen.

Leider verstehe ich nicht, wieso Pollard-Rho hier viel hilft. Ich habe zwar keine Ahnung von seiner Effizienz, aber das ganze funktioniert ja auf probabilistischer Basis, und dazu muss der Teiler auch keine Primzahl sein - über den wieder einen Primzahltest zu ziehen kostet wieder.

Edit: Code ist Müll. Ich habe ja vergessen, dass std::sqrt mit Fließkommazahlen hier Blödsinn ist... :schäm:

Edit³: Du hast mich allerdings mit der ganzen Geschichte auf eine Idee gebracht, wie man das lösen kann.

volkard

Arcoth schrieb:

volkard schrieb:

Hab hier nur auf auf die Primfaktorenzerleging und das Aufspannen des Teilerverbands wert gelegt, das bringt erstmal am meisten bei wenig Mathe-Aufwand.

Ich würde liebend gern die größeren Zahlen mit einbeziehen, deren Primfaktoren so groß sind dass der Algorithmus beim stumpfen Durchlaufen nicht ankommt.

Leider verstehe ich nicht, wieso Pollard-Rho hier viel hilft. Ich habe zwar keine Ahnung von seiner Effizienz,

Könnte sein, daß er nix garantiert, ist aber im Durchschnitt bombastisch effizient.

Arcoth schrieb:

aber das ganze funktioniert ja auf probabilistischer Basis, und dazu muss der Teiler auch keine Primzahl sein -

Jo, kriegst irgend zwei Teiler. Natürlich zwei große Teiler, denn den Pollards's-Rho wirfst Du erst an, wenn Du die kleinen Primfaktoren schon alle abgespalten hast, und jetzt vor Dir ein Produkt großer Primfaktoren liegt.

Arcoth schrieb:

über den wieder einen Primzahltest zu ziehen kostet wieder.

Primzahltest ist immer sauschnell. Den haste übrigens eh vor Pollard-Rho machen müssen.

Steckst also die beiden Faktoren, soweit sie keine Primzahlen sind, rekursiv in den Spalter.

Arcoth schrieb:

Edit: Code ist Müll. Ich habe ja vergessen, dass std::sqrt mit Fließkommazahlen hier Blödsinn ist... :schäm:

Jo, sqrt(uint64_t) muss eigentlich eh mal her. Hier im Forum geistert dazu nur schlechter Code rum, fürchte ich. Nette Mini-Teilaufgabe.

Und bevor die schnelle Spaltung überhaupt geht, muss eine schnelle istPrimzahl(uint64_t) her. Wohl am schnellsten, man schaut bei großen Zahlen, ob sie eine starke Pseudoprimzahl zu einigen Basen ist, von denen man garantieren kann, daß sie den Bereich bis 2^64 abdecken. Dazu würde ich davon ausgehen, daß die GRH gilt. Nette Maxi-Teilaufgabe.

knivil

Jo, sqrt(uint64_t) muss eigentlich eh mal her. Hier im Forum geistert dazu nur schlechter Code rum, fürchte ich. Nette Mini-Teilaufgabe.

Meine beginnt so:

uint64_t isqrt(unit64_t n)
{
     if (n < 1<<51) return (uint64_t)std::sqrt((double)n));

Und fuer den Anfang ist 2*10^15 schon sehr gross, wahrscheinlich zu gross. Aber 5896847556 ist auch kein guter Testcase, da nur Primzahlen bis 80000 gebraucht werden, also etwa 8000 Stueck.

It0101

volkard schrieb:

und wechle mal nach uint64_t

Ist Teil des C-Standards, daher nicht in C++ zu verwenden. *pfeif*

knivil

It0101 schrieb:

Ist Teil des C-Standards, daher nicht in C++ zu verwenden. *pfeif*

Pfeife: http://en.cppreference.com/w/cpp/types/integer

It0101

Gut. Dann sind die inzwischen dabei. Ich nehme alles zurück und behaupte das Gegenteil

volkard

knivil schrieb:

Aber 5896847556 ist auch kein guter Testcase, da nur Primzahlen bis 80000 gebraucht werden, also etwa 8000 Stueck.

Vielleicht magste die eher:
2^61-1: vieele Teiler
2^61-7: mehrfacher Primfaktor und große Primfaktoren
2^61-87: drei große Primfaktoren

Columbo

Ich glaube, ich weiß, was du meinst: Du checkst die "Standard-Teiler" ab, sprich, alle unter ~100000 (ist das ein gutes Maß?). Solange die Zahl dadurch nicht komplett zerlegt wird, zerlegt man sie in zwei kleine Teiler, die man wiederum in ihre Primfaktoren zerlegt.

Meine beginnt so:

Ich hoffe, so steht es nicht wirklich in deinem Code. Da ist nämlich UB drin, solange int 32-Bit groß ist.

Für x86:

// Böse geklaut von http://stackoverflow.com/questions/994593/how-to-do-an-integer-log2-in-c
int64 log2(int64 x)
{
	int64 y;
	asm ( "\tbsr %1, %0\n"
		: "=r"(y)
		: "r" (x) );
	return y;
}

int64 isqrt( int64 const n )
{
	double x = n >> log2(n)/2; // x ist höchstens 2^32
	double old_x;
	for(;;)
	{
		old_x = x;
		x = (x + n/x)/2;

		if( std::abs(x - old_x) < 1 )
			break;
	}

	return x;
}

Die Approximation kann man natürlich schlechter machen.

Die Approximation kann auch dem GCC überlassen werden, der hat eine schöne Funktion, genannt** __builtin_clzll **.

volkard

Arcoth schrieb:

Ich glaube, ich weiß, was du meinst: Du checkst die "Standard-Teiler" ab, sprich, alle unter ~100000 (ist das ein gutes Maß?).

Würde mal damit rechnen, daß vielleicht auch 256 gut ist. Lassen wir es offen und messen es später aus.

Arcoth schrieb:

Solange die Zahl dadurch nicht komplett zerlegt wird, zerlegt man sie in zwei kleine Teiler, die man wiederum in ihre Primfaktoren zerlegt.

Jo.

volkard

Arcoth schrieb:

int64 isqrt( int64 const n )
{
	double x = n >> log2(n)/2; // x ist höchstens 2^32
	double old_x;
	for(;;)
	{
		old_x = x;
		x = (x + n/x)/2;

		if( std::abs(x - old_x) < 1 )
			break;
	}

	return x;
}

Hoffe, uint64 ist gemeint.
Und innendrin nur double??? Dann bleibste ja ungenau, oder?

Arcoth schrieb:

Die Approximation kann man natürlich schlechter machen.

Und alles andere. Da geht noch einiges. Von knivils Trick gehen wir eh aus, hoffe ich.

Arcoth schrieb:

Die Approximation kann auch dem GCC überlassen werden, der hat eine schöne Funktion, genannt** __builtin_clzll **.

Die rechnet Dir nur log2(n) blitzschnell aus.