Goldbach Vermutung

[Erhard Henkes]

Kann man dieses Programm deutlich beschleunigen?
http://henkessoft.de/C++/C++/cpp_konsole.htm#mozTocId167626

[Primzahlezauber]

Aber Hallo! isPrime() ist echt lahm. Google hilft!

[Erhard Henkes]

Ja, klar, ist als Tutorial-Aufgabe gedacht.

vorher: 500000 time: 247545 ms
number/2 ==> 122772 ms
sqrt(number) ==> 5375 ms

Solange kein Gegenbeweis auftaucht, wird zumindest ein Paar Primzahlen gefunden.

[siebert]

Dein Programm ist O(n²). Mit gescheitem Primzahltest (=2 Zeichen hinzufügen) kommt man auf O(n^1.5). Mit einem Sieb erhält man O(n log log n).

[scrontch]

Erhard Henkes schrieb:

Ja, klar, ist als Tutorial-Aufgabe gedacht.

vorher: 500000 time: 247545 ms
number/2 ==> 122772 ms
sqrt(number) ==> 5375 ms

Das würde ich nicht als Optimierung im programmiertechnischen Sinn sehen.
Das ist einfach eine mathematische Überlegung, dass es nichts bringt weiter als bis sqrt(number) zu testen.

[Mr X]

Ist aber eine gute Lektion, dass Verbesserung der Algorithmen i.d.R. mehr bringt als Mikrooptimierungen.

[volkard]

Original:
500000 time: 306070 ms

for (unsigned int i=2; i<number/2; i++)

500000 time: 276635 ms

for (unsigned int i=2; i<=sqrt(number); i++)

500000 time: 1624 ms

irgendwie fühlt sich sqrt komisch an.
i<=sqrt(number) |()²
würde ich als Hausfrau schreiben als
i²<=number
//eigentlich Basiswissen. Man *sollte* es ausprobieren.
//ok, ja, ich weiß, man ist Betriebsblind. Schulmathe UND Proggern geht nicht gleichzeitig.
//Das müssen die neuen Leute aber mal verinnerlichen, daß gerade die Schulmathe undglaublich
//hilfreich ist.

for (unsigned int i=2; i*i<=number; i++)

500000 time: 1422 ms

Warum auch gerade Teiler testen, macht man per Hand ja auch nicht.
//GAANZ WICHTIG: Immer schauen, wie man es per Hand macht, da hat man gute
//Intuition oder sowas.

if(number<2) return false;
if(number==2) return true;
if(number%2==0) return false;
for (unsigned int i=3; i*i<=number; i+=2)

500000 time: 347 ms

Nebenbei:
// if(i%25000 == 0)
// {
// zeit2 = clock();
// cout << i << "\ttime: " << 1000 * (zeit2-zeit1) / CLOCKS_PER_SEC << " ms" << endl;
// }
...
zeit2 = clock();
cout << 500000 << "\ttime: " << 1000 * (zeit2-zeit1) / CLOCKS_PER_SEC << " ms" << endl;
War nicht ok, die Zeitmessung so in den Algo zu vermengern.

No was Wichtiges:
gegenbeweis ist eine "künstliche Variable"!
So eine, die das Exit-Pfeilchen im Struktogramm vermeidet.
Die schickt man immer(!) nach Hause durch Auslagern ein eine Funktion.

Hab auch den Namespace weggemacht, weil man den bringen sollte, wenn er was bringt, hier ist er Ballast.
Und die {}, wenn nur ein Befwehl folgt, weil optimalerweise folgt so verdammt oft nur ein Befehl, daß man
kaum {} braucht.
Das führt dann dummerweise dazu, daß die Einrückung viel viel mehr Gewicht hat als die Klammern, dann
zieht man vielleicht die { nach oben. Habs als Exempel mal gemacht. Also ich denke dahingehend in Python
und NUR die Einrückung bestimmt die Verschachtelung. Die { sind halt aus Tradition gefordert.

#include <iostream>
#include <ctime>
using namespace std;

//Goldbachsche Vermutung:
//Jede gerade Zahl größer als 2 kann als Summe
//zweier Primzahlen geschrieben werden.

bool IsPrime(unsigned int number){
	if(number<2) return false;
	if(number==2) return true;
	if(number%2==0) return false;
	for(unsigned int i=3; i*i<=number; i+=2)
		if(number%i == 0)
			return false;
	return true;
}

bool IstGoldig(unsigned int i){
	for(unsigned int a=2; a<i; a++)
		if(IsPrime(a) && IsPrime(i-a))
			return true;
	return false;
}

int main(){
	clock_t zeit1 , zeit2;
	unsigned int a;
	zeit1 = clock();
	for(unsigned int i=6; i<=500000; i+=2)
		if(not IstGoldig(i))
			cout << "Gegenbeweis gefunden für folgende Zahl: " << i << endl;
	zeit2 = clock();
	cout << 500000 << "\ttime: " << 1000 * (zeit2-zeit1) / CLOCKS_PER_SEC << " ms" << endl;
}

Zur Erinnerung, das Klammensparen ist nicht wichtig, das Auslagern um die pascaloide Variable zu
sparen war der Trick. Und dieser Trick geht meiner Erfahung nach immer. Immer hat die ausgelagerte
Funktion eine sinnvolle Bedeutung uns sollte schon allein deshalb ausgelagert sein.

Ok, wir haben eine Basis, auf der man aufbauen kann.

Und Mathetricks sind erstmal ausgeschöpft.

Programmiertricks müssen her. Primzahltest ist teuer. Könnte man die nicht zwischenspeichern?
Nee, kann man nicht. Es sind ja immer andere gefragt und 500000 Zahlen will keiner speichern.
Oder naja, so viel RAM habe ich zwar, aber kaum geht es mit 500000 will ich ja 5Mio oder 5Bio testen.

Könnte man fensterweise vorgehen?
Also sagen wie mal die Fenstergröße ist 1Mio.
Ich will alle Kandidaten i zwischen 17Mio und 18Mio-1 auf einmal testen.
Dann baue ich ein Primzahlenfenster 0Mio bis 1Mio-1 und eins 17Mio bis 18Mio-1. Dazu brauche ich nur 2Mio Primzahlentests.
Und ich streiche alle blöden Kandidaten raus.
Dann baue ich ein Primzahlenfenster 1Mio bis 2Mio-1 und eins 16Mio bis 17Mio-1. Dazu brauche ich nur 2Mio Primzahlentests.
Und ich streiche alle blöden Kandidaten raus.
Und so weiter bis sich die Primzahlenfenster überschneiden, also 9 mal 2Mio Primzahlentests.
Und hab damit das Kandidatenfenster von 17Mio bis 18Mio geklärt.
Macht zusammen 1Mio untersuchte Kandidaten zu Kosten von 18Mio Primzahlentests. (18Mio)

Vorher waren es für diesen Bereich 1Mio Kandidaten mit ca 17.5Mio mal 2 Primzahlentests. (35MioMio)

[sebi707]

for(unsigned int a=2; a<i; a++)

Hier gibts noch nen Faktor 2 zu holen, weil es reicht bis einschließlich i/2 zu testen.

[sebi707]

volkard schrieb:

for (unsigned int i=2; i*i<=number; i++)

500000 time: 1422 ms

Obacht mit dem Wertebereich. 500000^2 passt schon nicht mehr in eine 32 Bit Variable!

[Mr X]

i*i<=number ist eine intelligente Idee, die Fließkommaoperation sqrt() loszuwerden, schöner Hinweis (wenn man die 32-bit-Grenze dabei nicht vergisst. Problem ist halt, dass die Zahlen explodieren...).

[sebi707]

Mr X schrieb:

i*i<=number ist eine intelligente Idee, die Fließkommaoperation sqrt() loszuwerden, schöner Hinweis

Vermutlich will man eher eine effiziente Version davon: https://en.wikipedia.org/wiki/Integer_square_root

[volkard]

sebi707 schrieb:

volkard schrieb:

for (unsigned int i=2; i*i<=number; i++)

500000 time: 1422 ms

Obacht mit dem Wertebereich. 500000^2 passt schon nicht mehr in eine 32 Bit Variable!

Richtig. Man muss aufpassen wie ein Luchs.

Aber kann i denn in die Gegend von number kommen? Nöö, gell? Hab den Luchs erschossen! *freu* *hüpf*

[Bengo]

Für Zahlen kleiner als 341550071728321 ist sicher, dass es reicht zu prüfen ob die starke Pseudoprimzahlen sind zur Basis 2,3,6,7,9,11,13,17. Ich denke das geht recht schnell und kann dein Programm enorm beschleunigen.

Nachtrag: Für kleiner als 25326001, reichen 2,3,5.

[sebi707]

volkard schrieb:

Aber kann i denn in die Gegend von number kommen? Nöö, gell? Hab den Luchs erschossen! *freu* *hüpf*

Ich merks gerade. Hätte mir auch eher auffallen können...

[Erhard Henkes]

#include <iostream>
#include <limits>
#include <ctime>
#include <cstdint>

using namespace std;

void wait()
{
    cin.clear();
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    cin.get();
}

bool IsPrime(uint64_t number)
{
    if(number<2)    return false;
    if(number==2)   return true;
    if(number%2==0) return false;

    for(uint64_t i=3; i*i<=number; i+=2)
    {
        if(number%i == 0) return false;
    }
    return true;
}

bool ZweiPrimzahlenGefunden(uint64_t i)
{
    for(uint64_t a=2; a<i; a++)
    {
        if(IsPrime(a) && IsPrime(i-a))
            return true;
    }
    return false;
}

int main()
{
    clock_t zeit1 , zeit2;
    zeit1 = clock();

    for(uint64_t i=6; i<=5000000; i+=2)
    {
        if(!ZweiPrimzahlenGefunden(i))
            cout << "Gegenbeweis gefunden für folgende Zahl: " << i << endl;

        if (i%100000 == 0)
        {
                zeit2 = clock();
                cout << i << "\ttime: " << 1000 * (zeit2-zeit1) / CLOCKS_PER_SEC << " ms" << endl;
        }
    }

    wait();
 }

mit -O3 und 64 bit: 5000000 time: 18652 ms

[Bengo]

Ich denke du kannst noch richtig Speed raushohlen, wenn du dir die Primzahlen vorher erstellst.

Das hier könnte ein Construtor für eine Klasse Primes werden, die einen public std::vector mit den Primzahlen hält, über den kannst du dann immer iterieren.

Primes::Primes(int up_to) {
    this->primes.push_back(2);
    bool abbruch = false;
    for(int i = 3; i <= up_to; ++i) {
        for ( auto &p : this->primes ) {
            if (i%p == 0) {
                abbruch = true;
                break;
            }
        }
        if (abbruch == true) {
            abbruch = false;
        } else {
            this->primes.push_back(i);
        }
    }
}

[Erhard Henkes]

ja, das müsste man aber dann schon bis 18.446.744.073.709.551.616 machen für uint64_t. Gewaltiges Array.

[Mr X]

Erhard Henkes schrieb:

ja, das müsste man aber dann schon bis 18.446.744.073.709.551.616 machen für uint64_t. Gewaltiges Array.

Naja, zum Glück sind nur eine Minderheit der Zahlen bis dahin Primzahlen, sodass der Speicherbedarf doch ein erhebliches Stück geringer ist.

[Bengo]

Mr X schrieb:

Erhard Henkes schrieb:

ja, das müsste man aber dann schon bis 18.446.744.073.709.551.616 machen für uint64_t. Gewaltiges Array.

Naja, zum Glück sind nur eine Minderheit der Zahlen bis dahin Primzahlen, sodass der Speicherbedarf doch ein erhebliches Stück geringer ist.

mmh, ich würde sagen immernoch mehr als mein Computer verkraftet.
Es sind etwa 18.446.744.073.709.551.616/log(18.446.744.073.709.551.616)
(Ich meine den natürlichen log)
Und das sind immernoch verdammt viele.

Ok also bei so großen Zahlen würd ich trotzdem den Test mit den Pseudoprimzahlen machen, der ist einfach und schnell. Wird glaube auch bei vielen RSA implementierungen verwendet.

Und du kannst in der Schleife von ZweiPrimzahlenGefunden, wenigstens mit a = a + 2 interieren

[Bengo]

Die Idee hinter den Pseudoprimzahlen ist folgende:

Es gilt a^{p-1} \equiv 1 \mod p (kleiner Fermat) ggT(a,p)=1;(Beweis: betrachte die Gruppe der Restklassen modulo p ohne 0 mit der Multiplikation als verknüpfung, diese Gruppe hat die Ordung p-1, daher gilt für jedes a: a^(p-1)=1)

Umgekehrt kann man aber auch schließen, wenn für diese Kongruenz für eine Zahl n erfüllt ist, ist sie auch prim. Das stimmt leider nicht ganz, aber wenn es für die Zahlen a=2,3,5,7,11,13,17 gilt dann ist sie sehr wahrscheinnlich prim, und wenn kleiner als die Grenze die ich schon mal angegeben habe auch zu 100%. Kann man beweisen wenn man einfach mal überprüft, welche Zahlen bei 2 Pseudoprimzahlen sind, dann bei 3 und so weiter. Die kleinste gemeinsame Zahl ist dann schon verdammt groß.
Da sich $a^{p-1}$ eher nicht ausrechnen lässt, muss man das iterativ machen und immer mal wieder mod p rechnen.