3. Goldbach Vermutung

Goldbach Vermutung

  • V

    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.

    0
  • V

    Arcoth schrieb:

    @volkard: Lieste noch PMs?

    Selten, machmal monatelang nicht.

    0
  • E

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

    0
  • V

    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ß.

    0
  • Mod

    Protip: unsigned __int128 .

    0
  • L

    Superpro-Tipp: arbitrary-length integers. 😉

    0
  • B

    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.

    0
  • E

    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. 😉

    0
  • B

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

    0
  • E

    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.

    0
  • E

    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)

    0
  • Mod

    O-Notationen ignorieren Konstanten. Du meintest O(N1.5).

    0
  • Mod

    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.

    0
  • E

    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?

    0
  • Mod

    Erhard Henkes schrieb:

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

    😕 Probiers einfach aus?

    0
  • E

    32- und 64-bit: Das __int128-Schlüsselwort wird für diese Architektur nicht unterstützt.

    0
  • ?

    Erhard Henkes schrieb:

    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)

    hab jetzt nicht nicht geguckt ob die schlussfolgerungen alle richtig sind, aber O(N*sqrt(N)/6) quasi O(N) zu setzen (wie es der author macht) is auf jedefall falsch (deswegen mit vorsicht zu geniesen)...

    mit seiner begründung könnte ich auch sagen

    O(n^3) = O(n*n*n) = O(n^2*n) = O(n^2)

    weil n <<<< n^2 für große n. Dementsprechend wäre dann auch (wenn konsequent weiter gedacht):

    O(n^2) = O(n) = O(1)

    jeweils wieder mit der gleichen "begründung" wie oben. also einigermaßen falsch

    0
  • V

    Erhard Henkes schrieb:

    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)

    Gar nichts. Du bist schon wesentlich weiter als er.

    0
  • ?

    Erhard Henkes schrieb:

    32- und 64-bit: Das __int128-Schlüsselwort wird für diese Architektur nicht unterstützt.

    Sandy-Bridge unterstützt meines Wissens AVX, welches 16 256-Bit-Register anbietet. Wenn du dich mutig fühlst, kannst du mal schauen, ob dein Compiler Intrinsics anbietet - beim GCC hat es die auf alle Fälle.

    Wobei es aber wahrscheinlich intelligenter wäre, das auf SSE-Ebene (128-Bit-Register) zu implementieren. Ich habe damals für ein schnelles memset Tests zwischen 128- und 256-Bit-Implementierungen gemacht, keinen nennenswerten Unterschied festgestellt, und mich gewundert, bis ich auf Stackoverflow (Link finde ich allerdings nicht mehr, mein letztes Browser-Update hat meine komplette History vernichtet) gelesen habe, dass das Datenschieben zwischen CPU und Hauptspeicher bei 256 noch zu langsam ist der Synchronisierung wegen und man eigentlich bei 128 bleiben könnte.

    Wenn du allerdings zukunftssicher sein willst, kannst du mit AVX arbeiten. Oder sehnsüchtig auf AVX-512 schielen. 😉

    0
  • E

    Danke für die Antworten. Beim Austesten verschiedener Vorgehensweisen ist das bisherige Programm mit dem STL-Container unordered_set mit uint64_t einfach weiter gelaufen (verbraucht z.Z. nur 8% CPU-Kapazität).

    Über 5 * 10^9 umfasst die uint64_t (endlich lohnt es sich über 2^32) Primzahlen-Datei über 1,83 GB (mit heutigen Festplatten kein begrenzendes Thema).

    Limitierend wird nun das Thema RAM - wie von Volkard aufgegriffen. Da zeigt mein PC inzwischen 16,5 GB RAM (Beim Start: ca. 5 GB ==> 16,5 GB) an. Der STL-Container hat zwar ein schnelles "find", ist ansonsten aber nicht gerade "lean". Gestern konnte ich beobachten, wie auf die Schnelle von der STL mal 2,4 GB RAM neu okkupiert wurden. Das zwingt nun zu einem neuen Ansatz, aber bis in den Bereich von 5 Mrd. klappt alles gut.

    `

    5000099970 Anzahl Primzahlenpaare: 19462844

    5000099972 Anzahl Primzahlenpaare: 8880481

    5000099974 Anzahl Primzahlenpaare: 7279749

    5000099976 Anzahl Primzahlenpaare: 15647393`

    0
Anmelden zum Antworten