3. Goldbach Vermutung

Goldbach Vermutung

  • 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
  • E

    So, nun reicht es mit dem unordered_set im leider endlichen RAM und auch die Datei lädt immer langsamer, also erstmal alles nach vector<bool> mit uint64_t für x64. Dies greift Volkards Vorschlag auf (er hat es nur mit uint32_t gebaut)

    #include <iostream>
#include <iomanip>
#include <cstdint>
#include <cmath> 
#include <ctime>
#include <vector>

using namespace std;

void wait()
{
	cout << "Press any key to continue." << endl;
	cin.clear();
	cin.ignore(numeric_limits<streamsize>::max(), '\n');
	cin.get();
}

bool IsPrime(vector<bool>& primes, uint64_t number)
{
	return primes[number];
}

bool ZweiPrimzahlenGefundenInPrimeTable(vector<bool>& primes, 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(primes, a) && IsPrime(primes, i-a))			
		{
			retVal = true;
			counter++;
		}
	}
	cout << i << "\tprime pairs: " << setw(12) << counter;
	return retVal;
}

int main()
{
	uint64_t startNumber, endNumber;
	cout << "start number to be executed: ";
	cin >> startNumber;
	cout << "last number to be executed:  ";
	cin >> endNumber;

	vector<bool> primes(endNumber+1);	// processed numbers;
	time_t startTime, endTime;		// measuring execution time
	uint64_t global_count = 0;		// total number of primes

	time(&startTime);

	// initialize the number array
	primes[0] = false;
	primes[1] = false;
	for (uint64_t i=2; i<endNumber+1; ++i)
	{
		primes[i] = true;
	}

	// sieving loop
	uint64_t iMax = (uint64_t)sqrt((double)endNumber)+1;
	for (uint64_t i=2; i<iMax; ++i)
	{
		if (primes[i])
		{
			for (uint64_t j=2*i; j<endNumber+1; j+=i)
			{
				primes[j] = false;
			}
		}
	}

	time(&endTime);

	// count the number of primes
	for (uint64_t i=0; i<endNumber+1; ++i)
	{
		if (primes[i])
			global_count++;
	}

	cout << "We found " << global_count << " prime numbers." << endl
		<< "Execution time: " << difftime(endTime, startTime) << " seconds" << endl;

	wait();

	cout << "Now Goldbach prime number pairs are detected and counted" << endl << "from " << startNumber << " to " << endNumber << endl;
	clock_t zeit1, zeit2, zeit2_old;
	zeit2 = zeit1 = clock();

	for (uint64_t i = startNumber; i <= endNumber; i += 2)
	{
		if (!ZweiPrimzahlenGefundenInPrimeTable(primes, i))
		{
			cout << "Counterevidence found for this number: " << i << endl;
			wait();
		}

		zeit2_old = zeit2;
		zeit2 = clock();
		cout << "\tcalc. time: " << 1000 * (zeit2 - zeit2_old) / CLOCKS_PER_SEC << " ms" << endl;
	}
}

    `start number to be executed: 5000099970

    last number to be executed: 5000099976

    We found 234958692 prime numbers.

    Execution time: 56 seconds

    Press any key to continue.

    Now Goldbach prime number pairs are detected and counted

    from 5000099970 to 5000099976

    5000099970 prime pairs: 19462844 calc. time: 2765 ms

    5000099972 prime pairs: 8880481 calc. time: 2697 ms

    5000099974 prime pairs: 7279749 calc. time: 2681 ms

    5000099976 prime pairs: 15647393 calc. time: 2732 ms`

    Der RAM-Auslastung kommt das sehr entgegen.

    Bisher wird nur ein Kern verwendet. Die Frage ist, ist ein multi-threaded Berechnen der Primes schneller als das Laden der vorberechneten Bittabelle von Datei.

    Mein RAM von 32 GB reicht aus für Berechnungen bis in den Bereich 10^11 (ca. 5 ==> 16,3 GB), dann muss irgendein swap her von Platte. 😃

    0
  • B

    Denke die Datei hat irgentwo ihre Grenzen und genau die erreichtst du gerade. Für größere Zahlen gibt es alle möglichen Primzahltests, die auch sehr schnell und effektiv funktionieren. Und bei den meisten kann man auch sehr einfach und effektiv multithreading implementieren.

    0
  • E

    Ja, bei mir ist jetzt im Bereich 10^11 langsam schluss.

    RAM: 5 ==> 16,5 GB

    Zeitverhalten:

    Last number to be executed: 100000000000
    We found 4118054813 prime numbers (2 to last number).
    Execution time: 1480 seconds

    und ...

    `99999999982 prime pairs: 113717018 calc. time: 50675 ms

    99999999984 prime pairs: 227201878 calc. time: 51075 ms

    99999999986 prime pairs: 121706008 calc. time: 50826 ms

    99999999988 prime pairs: 134920837 calc. time: 50846 ms

    ...

    100000000000 prime pairs: 149091160 calc. time: 50648 ms

    `

    @bengo, volkard: Ist jetzt der Milli-Miller-Rabin mit den Fehlertabellen (hässlich!) der richtige Weg ab 10^11 aufwärts?

    0
  • B

    Ich wüsste nicht, dass es effiziente Verfahren gäbe, die ohne Fehlertabellen auskämen. Gibt den exacten AKS-Test, der hat zwar polynomielle Laufzeit, braucht aber troztdem länger als die meisten nicht deterministischen Algorithmen.
    Die openssl implementierung nutzt für das RSA Verfahren auch Primzahlen aus diesem Test und nimmst hin, dass es eventuell mal doch keine Primzahl sein kann.

    Wenn du ein Gegenbeispiel zu Goldbach finden solltest, musst du halt noch mal genau nachrechnen 😃

    0
Anmelden zum Antworten