Goldbach Vermutung

Columbo

@volkard: Lieste noch PMs?

Erhard Henkes

Die Datei ist schon im Bereich bis 1 Mrd. gefüllt (Größe: knapp 400 MB)
Mit uint64_t natürlich Verschwendung, aber das zählt heute nix mehr. Ab 4.294.967.296 macht sich das bezahlt.

999999900 Anzahl Primzahlenpaare: 4562607
999999900 time: 3764598 ms
999999902 Anzahl Primzahlenpaare: 1893418
999999904 Anzahl Primzahlenpaare: 1703735
999999906 Anzahl Primzahlenpaare: 3648927
999999908 Anzahl Primzahlenpaare: 1818341
999999910 Anzahl Primzahlenpaare: 2979831
999999912 Anzahl Primzahlenpaare: 3408624
999999914 Anzahl Primzahlenpaare: 1704021
999999916 Anzahl Primzahlenpaare: 1776165
999999918 Anzahl Primzahlenpaare: 3485738
999999920 Anzahl Primzahlenpaare: 2271013
999999920 time: 4038415 ms
999999922 Anzahl Primzahlenpaare: 1816246
999999924 Anzahl Primzahlenpaare: 4793529
999999926 Anzahl Primzahlenpaare: 1729134
999999928 Anzahl Primzahlenpaare: 1703407
999999930 Anzahl Primzahlenpaare: 4541309
999999932 Anzahl Primzahlenpaare: 1706109
999999934 Anzahl Primzahlenpaare: 1784800
999999936 Anzahl Primzahlenpaare: 3764962
999999938 Anzahl Primzahlenpaare: 2043764
999999940 Anzahl Primzahlenpaare: 2273405
999999940 time: 4314187 ms
999999942 Anzahl Primzahlenpaare: 3634878
999999944 Anzahl Primzahlenpaare: 1809485
999999946 Anzahl Primzahlenpaare: 1892186
999999948 Anzahl Primzahlenpaare: 3421789
999999950 Anzahl Primzahlenpaare: 2271899
999999952 Anzahl Primzahlenpaare: 2045480
999999954 Anzahl Primzahlenpaare: 3408253
999999956 Anzahl Primzahlenpaare: 1708123
999999958 Anzahl Primzahlenpaare: 1725433
999999960 Anzahl Primzahlenpaare: 4547143
999999960 time: 4588117 ms
999999962 Anzahl Primzahlenpaare: 1943855
999999964 Anzahl Primzahlenpaare: 1704392
999999966 Anzahl Primzahlenpaare: 4149473
999999968 Anzahl Primzahlenpaare: 1943234
999999970 Anzahl Primzahlenpaare: 2272712
999999972 Anzahl Primzahlenpaare: 3474263
999999974 Anzahl Primzahlenpaare: 1718735
999999976 Anzahl Primzahlenpaare: 1820043
999999978 Anzahl Primzahlenpaare: 3415578
999999980 Anzahl Primzahlenpaare: 2855600
999999980 time: 4863006 ms
999999982 Anzahl Primzahlenpaare: 1881761
999999984 Anzahl Primzahlenpaare: 3523571

(4038415 ms - 3764598 ms)/10 = ca. 27 sec pro gerader Zahl im Bereich bei 1 Mrd. Die 12 CPUs meines Rechners sind nur zu 8% ausgelastet. Da muss erstmal std::thread vom C++ 11 ran.

Zumindest muss man jede Primzahl nur einmal berechnen, nicht mehrfach. Zeit frisst natürlich das Berechnen aller Primzahlenpaare. RAM (für den STL-Container) ist kein Problem, habe 32 GB RAM, z.Z. liege ich bei 6,1 GB Auslastung.

Erhard Henkes

Die Anzahl der Primzahlen bis 10^9 habe ich nun auch:

Dateigröße: 406.780.264 Bytes (auf Anfrage verschicke ich diese gerne per e-mail)
ergibt Anzahl Primzahlen ab 3: 50.847.533

Zwischen 1 und 10^9 existieren also 50.847.534 Primzahlen. Diese Zahl habe ich auch im Netz gefunden:

http://www.michael-holzapfel.de/themen/primzahlen/pz-anzahl.htm

Zahl            p(x)
1.000.000.000 	50.847.534

Unser primitives isPrime stimmt also genau.

Das nächste Problem ist allerdings der RAM:
RAM: 32-5 GB = 27 GB => 3.623.878.656 <== soviele könnte ich im uint64_t Format im Speicher halten. Der STL-Container suckt aber auch.

100.000.000.000 <---> 4.118.054.813 Primzahlen <== das ist also nicht mehr so einfach machbar. da müsste man schon "swappen".

Habt ihr schonmal probiert, ob der Miller-Rabin-Test schneller ist?

Erhard Henkes

T.K. schrieb:

Habt ihr schonmal probiert, ob der Miller-Rabin-Test schneller ist?

Danke für den Hinweis, wurde inzwischen alternativ getestet.
http://www.sanfoundry.com/cpp-program-implement-miller-rabin-primality-test/

Gleiche Ausgangsbasis:
Daten bis 1 Mrd. in Datei
uint64_t ende = 1000100100;
uint64_t start = 1000100000;
... müssen also von 10^9 bis 1000100000 erstmal die Primzahlen berechnet werden.
Dann geht es in dem o.g. Bereich weiter mit genauer Berechnung aller Paare.

Test mit Miller-Rabin (5 Iterationen):
Resultate stimmen genau überein, also exakt.

Zeiten etwa vergleichbar: alte Methode: 27,5 sec pro Geradzahl, Miller-Rabin 29,2 sec, also kein Vorteil für unseren konkreten Fall (Unser Testfall ist ungeeignet).

Wir verbraten Zeit bei std::unordered_set::find und anderen Dingen. Wir erkennen, Primecheck ist nicht mehr so wichtig.

Focus schwenkt nun auf andere Abläufe im Programm. ==> Profiler

Miller-Rabin vs. die klassische Methode ist mathematisch sicher interessant, praktisch aber momentan nicht für mich.

Erhard Henkes

Wenn man einfach weiter "rechnen lässt", schlägt eine neue Begrenzung zu. Die App bittet um Ermordung:

Primzahlen werden aus der Datei geladen ...

maximum Prime: 1066715731
time: 112286 ms
Primzahlenpaare werden nun berechnet ...
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc

This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.

Process returned 3 (0x3) execution time : 117.791 s
Press any key to continue.

Hm, da gibt es wohl Probleme mit dem STL Container?! An welcher Schraube muss ich da drehen? Wie gesagt 32 GB RAM sind vorhanden.

volkard

Erhard Henkes schrieb:

T.K. schrieb:

Habt ihr schonmal probiert, ob der Miller-Rabin-Test schneller ist?

Danke für den Hinweis, wurde inzwischen alternativ getestet.
http://www.sanfoundry.com/cpp-program-implement-miller-rabin-primality-test/

Gleiche Ausgangsbasis:
Daten bis 1 Mrd. in Datei
uint64_t ende = 1000100100;
uint64_t start = 1000100000;
... müssen also von 10^9 bis 1000100000 erstmal die Primzahlen berechnet werden.
Dann geht es in dem o.g. Bereich weiter mit genauer Berechnung aller Paare.

Test mit Miller-Rabin (5 Iterationen):
Resultate stimmen genau überein, also exakt.

Du vestehst nicht.
Du sollst nicht 5 Iterationen MillerRabin machen, sondern NUR EINE (nennen wir es MilliMillerRabin)und nur mit der Basis 2.
Und das auch nur, wenn die zu prüfende Zahl nicht die Teiler 2,3,5,7,...,31 (hardcoded, für COmpileroptimierungen) drin hat.
Das flutscht dann ungemein. Aber ist noch leicht fehlerhaft.
Dann speicherst Du einfach alle Fehler ab, indem Du die MilliMillerRabin gegen Deine alte Schleifensuchvariante vergleichst.
Schwupps, die FehlerDatei bis 2^32 ist nur noch ein paar k groß.
Schwupps, die Primzahlen so zu erzeugen ist schneller als das Lesen von SSD.
Schwupps, einen Deiner 12 Kerne kannste durchlaufen lassen, um die Fehlerdatei zu vergrößern. Oder Du lädst die Fehlerdatei aus dem Netz, sie ist bis 2^64 verfügbar und wiegt dabei nur ein paarhundert M.
Und dann muss noch das schleifige mulmod(ll a,ll b,ll mod) gegen ein __asm "mul a[AX],b[DX]; div mod; return [DX]" ausgetauscht werden und Du hast nochmal Faktor 100 gewonnen.

Erhard Henkes schrieb:

Wir verbraten Zeit bei std::unordered_set::find und anderen Dingen. Wir erkennen, Primecheck ist nicht mehr so wichtig.

Ähm. Haste meinen Vorschlag mit den Fenstern gänzlich ignoriert?

Erhard Henkes schrieb:

Focus schwenkt nun auf andere Abläufe im Programm. ==> Profiler

Jo, viel Erfolg.

Erhard Henkes schrieb:

Miller-Rabin vs. die klassische Methode ist mathematisch sicher interessant, praktisch aber momentan nicht für mich.

Naja, Du hättest bis 2^64 keine Sorgen mehr, nicht die geringsten.

Übrigens benutze ich derzeit einen kleinen Eratosthenes, um mir die Datei zu sparen.

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

class Seldom{
	//Zweck: Console nicht vollspammen und durch zu viele Ausgaben
	//wertvolle Zeit verlieren, aber dennoch voll total ungebremst
	//bleiben, auch schneller als if(i%125000)…
//Erste Veröffentlichung hier? Dabei benutze ich Seldom schon seit 
//vielen Jahren. Die Klasse nimmt einem jeglichen Ausgabeabwägungsdruck 
//bei allen Numbercrunchern. 
    unsigned int count;
    unsigned int maxCount;
    clock_t lastTime;
    public:
    Seldom(){
        count=0;
        maxCount=0;
        lastTime=0;
    }
    bool operator()(){
        if(count==0){
            clock_t nowTime=clock();
            if((nowTime-lastTime)*8>CLOCKS_PER_SEC){
				//so ungefähr 8 Ausgaben pro Sekunde gönne ich mir, das
				//macht nichtmal einen 486-er lahm.
                maxCount=maxCount/2;
            }
            else{
                maxCount=maxCount*2+1;
            }
            lastTime=nowTime;
            count=maxCount;
            return true;
        }
        else{
			--count;
			return false;
		}
    }
    void reset(){
        maxCount=0;
        count=0;
    }
};

uint64_t const primeEnd=1000000000;

vector<uint32_t> makePrimeTable(){
	vector<uint32_t> result;
	Seldom seldom;
	cout<<"makePrimeTable\n"<<flush;
	vector<bool> noPrime(primeEnd+1);
	noPrime[0]=true;
	noPrime[1]=true;
	for(uint64_t f=2;f*f<=primeEnd;++f){
		if(!noPrime[f]){
			if(seldom()) cout<<'\r'<<f<<flush;
			for(uint64_t i=f*f;i<primeEnd;i+=f){
				if(!noPrime[i]){
					noPrime[i]=true;
				}
			}
		}
	}
	cout<<"\rcollect"<<flush;
	for(uint64_t i=0;i<primeEnd;++i)
		if(!noPrime[i])
			result.push_back(i);
	cout<<"\r         \r"<<flush;
	return result;
}

int main(){
	auto primeTable=makePrimeTable();
	cout<<primeTable.size()<<'\n';
}

Dateigröße: 406.780.264 Bytes (auf Anfrage verschicke ich diese gerne per e-mail)

Man verschickt keine Primzahlenlisten, sondern Programme.
Obiges braucht (auf meinem sicherlich viel lahmeren Rechner als Deinem) 15s dafür.

Das nächste Problem ist allerdings der RAM:
RAM: 32-5 GB = 27 GB => 3.623.878.656 <== soviele könnte ich im uint64_t Format im Speicher halten. Der STL-Container suckt aber auch.

100.000.000.000 <---> 4.118.054.813 Primzahlen <== das ist also nicht mehr so einfach machbar. da müsste man schon "swappen".

Jo. ALso mein Prog packts gerade noch. Aber hilft ja nix, sobald 100e9 gehen, willste 1000e9 und immer mehr…
Da muss einfach was her, was kaum RAM frisst und bei großen Zahlen nicht spürbar langsamer wird: Der MilliMillerRabin.

Ah, die Liste:
2-SPRP-2-to-64.zip (mirror 1)
auf https://miller-rabin.appspot.com/

Und benutz die Liste zum vorwärts- oder rückwärts-Generieren von Primzahlen, dabei kannste auch parallel vorwärts oder rückwärts durch die Liste wandern und brauchst kein binary-search oder ne hashtable.

volkard

Arcoth schrieb:

@volkard: Lieste noch PMs?

Selten, machmal monatelang nicht.

Erhard Henkes

@Volkard: Danke für die Hinweise und die Klasse Seldom.

Wirklich interessant, wie man so ab 10^9 in die Sackgasse fahren kann mit Vorgehensweisen, die im unteren Bereich unauffällig funktionieren.

Die Goldbach-Vermutung ist auf jeden Fall ein interessantes Spielfeld für die Programmierung. Als Nicht-Mathematiker sollte ich mich aber erst mit dem Thema Primzahlen und Zahlenverarbeitung ab 2^64 befassen.

@Volkard: was verwendest Du ab 2^64 ?

volkard

Erhard Henkes schrieb:

@Volkard: was verwendest Du ab 2^64 ?

Mal schauen, ich will was untersuchen für alle Zahlen zwischen 1 und 2^64. Mal utopischerweise angenommen, ich brauche pro Untersuchung nur eine Nanosekunde und habe 8 Threads…

Die jenseitige Programmierung ist vertagt, bis ich so weit bin, und das wird mit diesem Rechner frühestens in 2.305843009 Milliarden Jahren und 78 Tagen so weit sein.

Und dann schreibe ich einen schlichten struct uint128_t {uint64_t a,b;} und verschwende keinen Gedanken an 256 Bit oder gar beliebige Größen (naja vielleicht als Templateparameter sagt Onkel Karatsuba).

Deswegen auch in https://www.c-plusplus.net/forum/333745 als erstes die Frage nach der benötigten Größe. Habs erste Suchprogramm mit gmp eingeklimpert und rausgefunden, daß unter 40Mio kein Zyklus ist und dafür hat er die ganze Nacht gebraucht. Kanone zu groß.

Columbo

Protip: unsigned __int128 .

Leprechaun

Superpro-Tipp: arbitrary-length integers.

Bengo

Noch mal ein kleiner Nachtrag zu den Pseudoprimzahlen. Beim erreichen von a^p-1, solltest du folgendes beachten: a^(b+c)= a^b * a^c und insbesondere a^(b*c) = (a^b) ^c, auch wenn man zwischendurch mod p rechnent. Wenn du den algortihmus noch weiter optimieren willst, les dir am besten mal den Wikipediaartikel durch.

Erhard Henkes

Danke an alle für die Unterstützung!

Zunächst habe ich mich um das KO-Kriterium 'std::bad_alloc' gekümmert. Das kam bei der mit code::blocks kompilierten Variante, habe das Programm nach MS Visual Studio 2015 transferiert. Dort gibt es in diesem Stadium keine Speicher-Probleme, also kann das Gewurschtel weiter gehen.

Nun kann ich mich den math geek topics zuwenden.

Bengo

glaube codeblocks nutzt den g++, oder?
Aber auf jeden Fall ist es kein gutes Zeichen wenn ein Programm nur im Microsoft-Compiler läuft.

Erhard Henkes

Bengo schrieb:

glaube codeblocks nutzt den g++, oder?
Aber auf jeden Fall ist es kein gutes Zeichen wenn ein Programm nur im Microsoft-Compiler läuft.

Ja, ich verwendete Code:Blocks Version 13.12 mit dem GNU gcc Compiler. Setze ich gerne ein, weil man bei dieser IDE mit einzelnen Files arbeiten kann (nur ein Directory mit cpp, o, exe und ggf. Daten).
Aber was soll man machen? MS VS 2015 ist eine wirklich hervorragende IDE. Dort läuft es auf jeden Fall. Ich habe x64 als Ziel und bei Optimierung -Ox, -Oi und -Ot eingestellt. Auffällig ist, dass das Programm sich gleich deutlich mehr RAM grapscht. Bin nun in Win7 bei ca. 8,5 GB (von 32 GB). Zeitlich ist das Programm aber schlechter: Enttäuschende 43 sec pro Geradzahl (im Bereich 1,1*10^9) anstelle vorher (bei der Code::Blocks-Variante) ca. 27 sec.

Dafür läuft die Anwendung ohne Probleme. Die Datenbank mit Primzahlen z.Z. von 3 bis 1,1*10^9 im uint64_t Format umfasst 435 MB.

Erhard Henkes

Was haltet ihr von dieser Vorgehensweise? http://manzzup.blogspot.de/2013/12/ultra-fast-prime-number-generating.html
O(N^2) ==> O(N*sqrt(N)/6)

Columbo

O-Notationen ignorieren Konstanten. Du meintest O(N^1.5).

Columbo

Bengo schrieb:

glaube codeblocks nutzt den g++, oder?

Und einen Haufen anderer Compiler. Ich verwende damit GCC und Clang (und davon je zwei verschiedene Versionen), und spiele mit dem Gedanken mir ICC zuzulegen.

Leprechaun schrieb:

Superpro-Tipp: arbitrary-length integers.

Ja, sind nur vergleichsweise lahm. Also kein sonderlich guter Tipp.

Erhard Henkes

kann man dieses unsigned __int128 auf einem Intel Core i7 3930K (Sandy Bridge-E) verwenden?

Für Collatz hatte ich https://mattmccutchen.net/bigint/ eingesetzt. Wie schätzt ihr dies ein?