Goldbach Vermutung
-
Bengo schrieb:
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); } } }abbruch ist eine "künstliche variable", die nur dazu da ist, das exit-pfeilchen aus dem struktogramnm wegzumachen. was hatte onkel volkard vorhin darüber geschrieben?
-
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.
Ein Trugschluss!
Sagen wir mal, man will eine Primzahlenliste bis 2^n speichern und hat als Alternativen
A einen vector<n-bittiger-int>(wo man nur die primzahlen speichert) oder
B einen vector<bool>(wo man 2^n bits drin hat und nur die primzahlen sind 1).Was ist teuerer? Und vor allem, wie verhält es sich, wenn n immer größer wird?
Primzahlensatz: Zwischen 0 und x gibt es ungefähr x/ln(x) Primzahlen.
B braucht 2^n Bits.
A braucht n*(2n)/ln(2n) = n*(2^n)/(ln(2)*n) = 2^n/ln(2) Bits.
B braucht 69% von A.Überraschung, der Verbrauch von B wird nie "erhebliches Stück geringer" sein.
-
Bengo schrieb:
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.
evtl haste Spaß daran: https://www.c-plusplus.net/forum/67513-full
Das führt aber zu weit für die Zielgruppe von Ehrhard fürchte ich.
-
du kannst in der Schleife von ZweiPrimzahlenGefunden, wenigstens mit a = a + 2 iterieren
bool ZweiPrimzahlenGefunden(uint64_t i) { uint64_t a=2; if(IsPrime(a) && IsPrime(i-a)) return true; for(a=3; a<i; a+=2) { if(IsPrime(a) && IsPrime(i-a)) return true; } return false; }Gemessene Zeitersparnis (6 bis 5.000.000): 1,93% DANKE!
Wie wichtig Reihenfolgen sind, sieht man daran, wenn man die Anordnung
IsPrime(i-a) && IsPrime(a)
ausprobiert. Dann braucht es etwa 65% mehr Zeit.
-
Den Test mit a=2 kann man auch sein lassen; 2 + irgendeine andere Primzahl ergibt eine ungerade Zahl, aber die Goldbachsche Vermutung betrifft nur gerade Zahlen. Für 4 ergäbe es zwar dann einen angeblichen Gegenbeweis, allerdings startet dein Test ja eh erst bei 6.
-
bool ZweiPrimzahlenGefunden(uint64_t i) { for(uint64_t a=3; a<i; a+=2) { if(IsPrime(a) && IsPrime(i-a)) return true; } return false; }Gute Idee. Das bringt 7% Zeitersparnis.
Interessant wird es aber erst bei hohen Zahlen (mit -O3):
Intel i5-2520M 2,5 GHz, 8 GB RAM, 64 bit1000000000000000000 time: 4836 ms
1000000000000000100 time: 249455 ms
1000000000000000200 time: 560991 msZur Sicherheit der aktuelle Code:
#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=3; a<i; a+=2) { if(IsPrime(a) && IsPrime(i-a)) return true; } return false; } int main() { clock_t zeit1 , zeit2; zeit1 = clock(); for(uint64_t i=1000000000000000000; i<=2000000000000000000; i+=2) { if(!ZweiPrimzahlenGefunden(i)) cout << "Gegenbeweis gefunden für folgende Zahl: " << i << endl; if (i%100 == 0) { zeit2 = clock(); cout << i << "\ttime: " << 1000 * (zeit2-zeit1) / CLOCKS_PER_SEC << " ms" << endl; } } wait(); }oder:
18400000000000000000 time: 27753 ms
18400000000000000010 time: 168974 ms
18400000000000000020 time: 308288 ms
18400000000000000030 time: 446579 ms
18400000000000000040 time: 587249 ms
18400000000000000050 time: 741313 msint main() { clock_t zeit1 , zeit2; zeit1 = clock(); for(uint64_t i=18400000000000000000; i<=18446744073709551615; i+=2) { if(!ZweiPrimzahlenGefunden(i)) cout << "Gegenbeweis gefunden für folgende Zahl: " << i << endl; if (i%10 == 0) { zeit2 = clock(); cout << i << "\ttime: " << 1000 * (zeit2-zeit1) / CLOCKS_PER_SEC << " ms" << endl; } } wait(); }Welche Bibliothek sollte man für Zahlen größer 2^64 - 1 einsetzen?
-
Ein erweitertes Thema: Zahl der Goldbach-Zerlegungen:
99999000 Anzahl Primzahlenpaare: 599905
99999000 time: 111418 ms
99999002 Anzahl Primzahlenpaare: 219708
99999004 Anzahl Primzahlenpaare: 261948
99999006 Anzahl Primzahlenpaare: 437521
99999008 Anzahl Primzahlenpaare: 222566
99999010 Anzahl Primzahlenpaare: 291523
99999010 time: 591165 msAb einer Milliarde wird es sehr zeitaufwändig (ca. 1h pro Zahl):
999999000 Anzahl Primzahlenpaare: 6797548
999999000 time: 3201129 mshttps://upload.wikimedia.org/wikipedia/commons/thumb/7/79/Goldbach200000.png/1024px-Goldbach200000.png <== Interessantes Muster.
Da wird es ab 100 Millionen am PC hakelig und Beschleunigung ist gefragt.Kann man die AKS- oder Bernstein-Methodik hier vernünftig einsetzen? http://yves.gallot.pagesperso-orange.fr/src/aks.html
-
Inzwischen wurde zum Erfassen bereits berechneter Primzahlen die STL-Klasse unordered_set verwendet.
Im Bereich 10^8 benötigt man nach dem Ersterfassen ca. 2 sec pro weitere Zahl, während das bei 10^9 auf ca. 20 sec und mehr anwächst. In richtig hohen Zahlenbereichen kann man damit nicht schnell arbeiten, aber im Bereich 10^8 bis 10^9 ist es noch erträglich.
Code wurde auf die Schnelle zusammen mit MrX entwickelt:
#include <iostream> #include <limits> #include <ctime> #include <cstdint> #include <cmath> #include <unordered_set> using namespace std; void wait() { cin.clear(); cin.ignore(numeric_limits<streamsize>::max(), '\n'); cin.get(); } unordered_set<uint64_t> primzahlen; bool IsPrime(uint64_t number) { static unordered_set<uint64_t> primzahlen; static uint64_t maxPrim = 1; if (number == 2) return true; if (number % 2 == 0) return false; if (number > maxPrim) { for (uint64_t j = maxPrim + 2; j <= number; j+=2) { bool prim = true; const uint64_t maxI = sqrt(j)+1; for (uint64_t i = 3; i < maxI; i += 2) { if (j%i == 0) { prim = false; break; } } if (prim) primzahlen.insert(j); } maxPrim = number; } return primzahlen.find(number) != primzahlen.cend(); } bool ZweiPrimzahlenGefunden(uint64_t i) { bool retVal = false; uint64_t counter = 0; uint64_t grenze = i/2; for(uint64_t a=3; a<=grenze; a+=2) { if(IsPrime(a) && IsPrime(i-a)) { retVal = true; counter++; } } cout << i << "\tAnzahl Primzahlenpaare: " << counter << endl; return retVal; } int main() { clock_t zeit1 , zeit2; zeit1 = clock(); uint64_t ende = pow(10,9); uint64_t start = ende - 1000; for(uint64_t i=start; i<ende; i+=2) { if(!ZweiPrimzahlenGefunden(i)) { cout << "Gegenbeweis gefunden fuer folgende Zahl: " << i << endl; wait(); } if (i%10 == 0) { zeit2 = clock(); cout << i << "\ttime: " << 1000 * (zeit2-zeit1) / CLOCKS_PER_SEC << " ms" << endl; } } wait(); }zeiten hier sind noch mit "set" ("unordered_set" ist bei unserer Anwendung schneller, wie wir herausfanden)
999999000 Anzahl Primzahlenpaare: 6797548
999999000 time: 4139032 ms
999999002 Anzahl Primzahlenpaare: 1702684
999999004 Anzahl Primzahlenpaare: 1704379
999999006 Anzahl Primzahlenpaare: 3446471
999999008 Anzahl Primzahlenpaare: 1706654
999999010 Anzahl Primzahlenpaare: 2287647
999999010 time: 4243619 ms
999999012 Anzahl Primzahlenpaare: 3413819
999999014 Anzahl Primzahlenpaare: 2152037
999999016 Anzahl Primzahlenpaare: 1735940
999999018 Anzahl Primzahlenpaare: 3475878
999999020 Anzahl Primzahlenpaare: 2333367
999999020 time: 4348399 ms
999999022 Anzahl Primzahlenpaare: 1892957
999999024 Anzahl Primzahlenpaare: 3699436
999999026 Anzahl Primzahlenpaare: 1857980
999999028 Anzahl Primzahlenpaare: 2046068
999999030 Anzahl Primzahlenpaare: 4546857
999999030 time: 4453061 ms
999999032 Anzahl Primzahlenpaare: 1811153
999999034 Anzahl Primzahlenpaare: 1704392
999999036 Anzahl Primzahlenpaare: 3408873
999999038 Anzahl Primzahlenpaare: 1710611
999999040 Anzahl Primzahlenpaare: 2272340
999999040 time: 4558470 ms
999999042 Anzahl Primzahlenpaare: 4090190
999999044 Anzahl Primzahlenpaare: 1892849
999999246 Anzahl Primzahlenpaare: 3410049
999999248 Anzahl Primzahlenpaare: 1703128
999999250 Anzahl Primzahlenpaare: 2275863
999999250 time: 6763243 ms
999999252 Anzahl Primzahlenpaare: 4113235
999999254 Anzahl Primzahlenpaare: 1741288
999999256 Anzahl Primzahlenpaare: 1704736
999999258 Anzahl Primzahlenpaare: 3407972
999999260 Anzahl Primzahlenpaare: 2766263
999999260 time: 6869398 ms
999999262 Anzahl Primzahlenpaare: 1819055
999999264 Anzahl Primzahlenpaare: 3787120
999999266 Anzahl Primzahlenpaare: 2100496
999999268 Anzahl Primzahlenpaare: 1704037
999999270 Anzahl Primzahlenpaare: 4579523
999999270 time: 6975479 ms
999999272 Anzahl Primzahlenpaare: 1724075
999999274 Anzahl Primzahlenpaare: 1707638
999999276 Anzahl Primzahlenpaare: 3410234
999999278 Anzahl Primzahlenpaare: 1711543
999999280 Anzahl Primzahlenpaare: 2727397
999999280 time: 7081272 ms
999999282 Anzahl Primzahlenpaare: 3405799
999999284 Anzahl Primzahlenpaare: 1703633
999999286 Anzahl Primzahlenpaare: 2140724
999999288 Anzahl Primzahlenpaare: 3406364
999999290 Anzahl Primzahlenpaare: 2379056
999999290 time: 7191097 ms
999999292 Anzahl Primzahlenpaare: 1706699
999999294 Anzahl Primzahlenpaare: 4090961
999999296 Anzahl Primzahlenpaare: 1869231
999999298 Anzahl Primzahlenpaare: 1815160
999999300 Anzahl Primzahlenpaare: 4544051
999999300 time: 7296351 ms
-
Man möchte die bereits berechneten Primzahlen nicht nur im STL-Container halten, sondern seine "Primes" in einem File mitwachsen lassen. Folgendes klappt bisher:
#include <iostream> #include <limits> #include <ctime> #include <cstdint> #include <cmath> #include <unordered_set> #include <fstream> using namespace std; void wait() { cout << "Press any key to continue." << endl; cin.clear(); cin.ignore(numeric_limits<streamsize>::max(), '\n'); cin.get(); } unordered_set<uint64_t> primzahlen; fstream myPrimesDatabase; bool IsPrime(uint64_t number, fstream &database, uint64_t &maxPrim) { if (number == 2) return true; if (number % 2 == 0) return false; if (number > maxPrim) { for (uint64_t j = maxPrim + 2; j <= number; j+=2) { bool prim = true; const uint64_t maxI = sqrt(j)+1; for (uint64_t i = 3; i < maxI; i += 2) { if (j%i == 0) { prim = false; break; } } if (prim) { primzahlen.insert(j); database.seekg(ios::end); database.write((char*)&j,sizeof(j)); } } maxPrim = number; } return primzahlen.find(number) != primzahlen.cend(); } bool ZweiPrimzahlenGefunden(uint64_t i, fstream &database, uint64_t &maxPrim) { bool retVal = false; uint64_t counter = 0; uint64_t grenze = i/2; for(uint64_t a=3; a<=grenze; a+=2) { if(IsPrime(a, database, maxPrim) && IsPrime(i-a, database, maxPrim)) { retVal = true; counter++; } } cout << i << "\tAnzahl Primzahlenpaare: " << counter << endl; return retVal; } int main() { clock_t zeit1 , zeit2; zeit1 = clock(); uint64_t j; fstream &refMyPrimesDatabase = myPrimesDatabase; uint64_t maxPrim = 2; myPrimesDatabase.open("myPrimesDatabase.dat", fstream::in | fstream::binary); cout << "Primzahlen werden aus der Datei geladen ..." << endl; while (!myPrimesDatabase.eof()) { myPrimesDatabase.read((char*)&j, sizeof(j)); //cout << j << " "; primzahlen.insert(j); } myPrimesDatabase.close(); maxPrim = j; cout << endl << endl << "maximum Prime: " << maxPrim << endl; //wait(); cout << "Primzahlenpaare werden nun berechnet ..." << endl; myPrimesDatabase.open("myPrimesDatabase.dat", fstream::out | fstream::app | fstream::binary | fstream::ate); uint64_t &refMaxPrim = maxPrim; uint64_t ende = 52000; uint64_t start = 6; for(uint64_t i=start; i<=ende; i+=2) { if(!ZweiPrimzahlenGefunden(i, refMyPrimesDatabase, refMaxPrim)) { cout << "Gegenbeweis gefunden fuer folgende Zahl: " << i << endl; wait(); } if (i%10 == 0) { zeit2 = clock(); cout << i << "\ttime: " << 1000 * (zeit2-zeit1) / CLOCKS_PER_SEC << " ms" << endl; } } myPrimesDatabase.close(); wait(); }Primzahlen von 3 bis 52000 gibt es hier in der zum Prg passenden dat (im binären uint64_t Format): http://henkessoft.de/Sonstiges/myPrimesDatabase.dat
-
Erhard Henkes schrieb:
Man möchte die bereits berechneten Primzahlen nicht nur im STL-Container halten, sondern seine "Primes" in einem File mitwachsen lassen.
Ja.
Weil man ja eh dauernd noch ein wenig am Algo rumfummelt und da hilft es mächtig, daß beim nächsten Programmstart die Primzahlen schon vorliegen, statt nochmal berechnet werden zu müssen.Und endgeil wird es, wenn man diesen Pseudoprimzahlentrick (mit Basis 2) von Bengo vorschaltet. Dann muss man nur die Lügner abspeichern und das sind sauwenige. Sausauwenige.
-
@volkard: Lieste noch PMs?
-
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.
-
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.533Zwischen 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.534Unser 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?
-
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.
-
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_allocThis 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.
-
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: 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 ?
-
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ß.
