# Primzahlen Contest



## Roundy (6. Oktober 2015)

*Edit: 

Da meine Frage sich ja erübrigt hat wollte ich euch mal zu einem kleinen Contest auffordern.
Und zwar geht es darum alle Primzahlen (bzw deren Anzahl) von 0 bis 1 Milliarde zu berechnen.

Euer Programm muss enthalten:

Eingabeaufforderung (siehe meins auf seite 2)
Zeitmessung (nur für die Rechenarbeit, nicht für die Ausgabe)
Korrekte berechnete(!) Werte

Es muss die Primzahlen nicht ausgeben, sondern nur deren Anzahl.
Den Code dann anschließend im Thread posten, damit wir voneinander lernen können.

Haut rein Leute 

Gruß
*


Hey ho, ich hab ne bissl exotische Frage:

Wir haben als Informatik Hausaufgabe die Aufgabe erhalten das Sieb des Eratosthenes in Java zu programmieren.
So weit kein Problem.
Ich würde das ganze jetzt aber gerne nicht nur auf einem Prozessorkern sondern auf meinen 4 laufen lassen, und da komm ich an ein Problem.

Momentan noch nicht Multithreading fähige Herangehensweise:

Ich lege einen Array der Größe i an (i ist die Zahl bis zu der getestet wird)

anschließend streiche ich gemäß des Siebes alle Zahlen und so weiter bis nur die Primzahlen übrig bleiben.


Mein Gedanke  für mehrere Threads war den ursprünglichen Array_ in 4 Arrays jeweils der Größe u = i / 4 zu unterteilen.
Nun ist ist der Startwert für einen Array ja immer 0.

somit steht in meinem Fall der Array[0] für die Zahl 0.

Ich würde jetzt aber gerne nicht jeden Array mit 0 starten lassen sondern den ersten im Intervall Array[0] bis Array, den Zweiten im Intervall von  Array bis Array[2u], den dritten Array[2u] bis Array[3u] und den vierten von Array[3u] bis Array.

Ist dies überhaupt möglich?

Und wenn ja wie?

Gruß_


----------



## Malkolm (6. Oktober 2015)

*AW: Array Anfangswert mitgeben [Java]*

Das (klassische) Sieb profitiert in keinster Weise vom Multithreading.

Zur Frage: Arrays mit Werten initialisieren ist gleichbedeutend mit einer Initialisierung ohne Werte und nachfolgender Zuweisung. Eine for-schleife ist da dein Freund.


----------



## Roundy (6. Oktober 2015)

*AW: Array Anfangswert mitgeben [Java]*

Hab mitlerweile nen anderen weg gefunden, mal schauen ob ichs am ende mit multithreading doch schneller hinbekomm...
Gruß


----------



## DKK007 (7. Oktober 2015)

*AW: Array Anfangswert mitgeben [Java]*

Vielleicht würde eine andere Sprache da deutlich mehr bringen. Java ist einfach lahm. Bei kleineren Zahlen sollte das Programm aber auch so auf ner ordentlichen CPU in Sekundenbruchteilen fertig sein.


----------



## Roundy (7. Oktober 2015)

*AW: Array Anfangswert mitgeben [Java]*

Also bisher schaffe ich alle primzahlen von 0 bis 100 millionen in ca. 4, 6  Sekunden. 
Mit mehreren threads will ich aif unter eine sekunde bzw unter zwei sekunden kommen.
Gruß


----------



## Malkolm (7. Oktober 2015)

*AW: Array Anfangswert mitgeben [Java]*

Dann wünsche ich gutes gelingen beim Eintauchen in die Welt der Multithread-Programmierung!

Ein paar Anmerkungen aber trotzdem noch zum konkreten Problem:

- Du wirst feststellen, dass das klassische Sieb nicht so einfach auf mehrere Threads aufzuteilen ist, da diese zwar verschiedene Kandidatenräume beackern können, aber dies nicht unabhängig voneinander. Sobald in einem kleineren Zahlenraum eine Primzahl findest hat das Auswirkungen auf alle größeren Räume. Auf der anderen Seite kannst du bei allen Funden in größeren Räumen nicht sicher davon ausgehen, dass es wirklich eine Primzahl ist, solange nicht die kleineren Räume fertig beackert sind -> Absolut kein Geschwindigkeitsvorteil!

- Eine einfache Implementierung von Multithreads auf das Primzahlenproblem wäre sich eine Funktion zu definieren, die einen konkreten Kanditaten darauf prüft ob sie eine Primzahl ist, und das unabhängig von allen anderen Kandidaten. Somit kannst du beliebig viele unabhängige Threads starten, jeder für andere Kandidaten.

Weitere Stichworte, die dir in diesem Zusammenhang helfen können: Primzahltests nach Miller-Rabin, Fermat und Solovay-Strassen. Das Primzahl-Theorem (X ~ x/log x).


----------



## Roundy (7. Oktober 2015)

*AW: Array Anfangswert mitgeben [Java]*

Naja das sieb ist das schnellste verfahren, da jede nichtprim nur einmal in die hand genommen wird... sollte es gelingen bekommt ihrs mit 
Gruß


----------



## Roundy (7. Oktober 2015)

*AW: Array Anfangswert mitgeben [Java]*

So kleines Update.. ich habe es geschafft 

alle Primzahlen von 0 bis 100 000 000 in 0,7 sekunden und alle bis 1 000 000 000 in 8 Sekunden.
Danke an alle.

Gruß


----------



## DKK007 (7. Oktober 2015)

*AW: Array Anfangswert mitgeben [Java]*

Wie hast du es gemacht?


----------



## Roundy (7. Oktober 2015)

*AW: Array Anfangswert mitgeben [Java]*

Was genau?


----------



## Crysis nerd (8. Oktober 2015)

*AW: Array Anfangswert mitgeben [Java]*

Mich würde auch interessieren, wie du das Sieb des Eratosthenes mit 4 Thread mehr als vier mal so schnell gemacht hast 
Hast du zufällig mal deine neuen Ergebnisse mit den alten verglichen?

Im Übrigen würde ich auch sagen, dass es wohl am schnellsten ist, erst probabilistische Verfahren zu verwenden, um Primzahlen "vorzufiltern". Die false-positives filter man dann am Ende mit einem richtigen Test heraus. Dieser richtige Test kann natürlich das Sieb des E. sein, aber das ist wohl eher ungeeignet, da man dieses große Array braucht, wo die meisten Zahlen schon "gestrichen" sind.

Wobei ich mir gerade denke, dass es doch möglich seien sollte, das Array zu komprimieren *_* 
Hab gerade keine Zeit weiter drüber nachzudenken, aber kannst ja mal probieren 

EDIT: Mir fällt trotzdem gerade noch ein, dass das Sieb des E. wohl von Multithreading profitieren würde, allerdings nur, wenn man es etwas geschickter macht.


----------



## Roundy (8. Oktober 2015)

*AW: Array Anfangswert mitgeben [Java]*

also das mehr als vier mal so schnell kommt nicht nur vom mutlithreading.
momentan läufen vier threads durch:

Thread 1: 

```
int m = 2;	
            
    				for (int c = m * 2; c < i; c += m) 
    				{
                   
    					                       	
    						alleZahlen[c] = true;
                       	
    				}
```

Thread 2:


```
int m = 3;
			for (int m = 3; m <= wurzel; m += 6)
		{
		
			if (alleZahlen[m] == false)
			{
				for (int c = m * 2; c < i; c += m) 
				{
              
					
						alleZahlen[c] = true;
                    
				}
                                         
			}
     
		}
```

Thread 3:


```
for (int m = 5; m <= wurzel; m += 6)
		{
		
			if (alleZahlen[m] == false)
			{
				for (int c = m * 2; c < i; c += m) 
				{
               
					
						alleZahlen[c] = true;
                   	
				}
                                         
			}
		}
```

Thread 4:

```
for (int m = 7; m <= wurzel; m += 6)
		{
		
			if (alleZahlen[m] == false)
			{
				for (int c = m * 2; c < i; c += m) 
				{
              
					
						alleZahlen[c] = true;
                    
				}
                                         
			}
     
		}
```


Das ganze ist noch relativ inneffizient, ich muss mir noch ne methode ausdenken mit der ich verhinder, dass zweimal die gleiche zahl abgefragt wird.
Gruß


----------



## Crysis nerd (10. Oktober 2015)

*AW: Array Anfangswert mitgeben [Java]*

Hab ja jetzt Ehrgeiz, das selber schnell hinzukriegen 

Kannst du mal den ganzen Code posten? Und auf was für ner CPU lässt du das laufen?


----------



## Roundy (10. Oktober 2015)

*AW: Array Anfangswert mitgeben [Java]*

Sobald ich daheim bin.
Machen wir nen kleinen contest draus 
Hab den code noch weiter verbesser, bin mittlerweile bei 1 milliarde bei ca. 3, 7 sekunden.
i5 4670k @ 4 ghz.
Gruß


----------



## Crysis nerd (10. Oktober 2015)

*AW: Array Anfangswert mitgeben [Java]*

Ok, können wir gerne versuchen 

Also von https://www.cpubenchmark.net/cpu_list.php habe ich diesen Wert:
Intel Core i5-4670K @ 3.40GHz:  7639

Du hast den ja aber scheinbar übertaktet. Ich arbeite hiermit:
Intel Core i7-3612QM @ 2.10GHz:  6838

Sagen wir einfach mal sowas wie: Deine CPU ist 1,25 mal so schnell wie meine  Also kein großer Unterschied.


Ich hab das letztens mal ganz normal in Rust runtergeschrieben (also keine komischen Optimierunge) und da war es schon auf einem Thread ziemlich schnell (7s für 1Mrd). Multithreading habe ich gestern probiert, aber davon profitiere ich irgendwie nicht so. Muss ich mal untersuchen.

Damit die Ergebnisse auch korrekt sind, lass mal die Primzahlen zählen. Wolframalpha sagt zb:
Primzahlen < 1 Mrd:   50 847 534
Primzahlen < 100 Mio. 5 761 455


----------



## Roundy (10. Oktober 2015)

*AW: Array Anfangswert mitgeben [Java]*

die primzahlen stimmen ;D
hier der Code:

Thread 1 gesamt:

```
package primzahlen;
import javax.swing.JOptionPane;

public class PrimzahlenfindeClass 
{

	public static void main(String[] args) 
	{
		
		 	String eingabe = JOptionPane.showInputDialog("Geben sie die Variable i > 1 ein");  
		 	int i = Integer.parseInt(eingabe);
		 	boolean[] alleZahlen = new boolean[i];
		 	double zeit1 = System.currentTimeMillis();
		 	int wurzel = (int) Math.sqrt(i);
		 	int anzahl = 0;
		 	int m = 2;	

		 	Multithreading t1 = new Multithreading("erster Thread", i, alleZahlen, wurzel);
		 	Multithreading02 t2 = new Multithreading02("zweiter Thread", i, alleZahlen, wurzel);
		 	Multithreading03 t3 = new Multithreading03("dritter Thread", i, alleZahlen, wurzel);



		 	alleZahlen[0] = true;
		 	alleZahlen[1] = true;

		 	t1.start();
			t2.start();
			t3.start();


				for (int c = m * m; c < i; c += m) 
				{
					alleZahlen[c] = true;
   				}

				try 
				{
					t1.join();
					t2.join();
					t3.join();
				}	catch (InterruptedException e)
					{
						e.printStackTrace();
					}

				if (i == 2)
				{
					anzahl += 1;
				}

				double zeit2 = System.currentTimeMillis();
				double endzeit = (zeit2 - zeit1)/1000;

				for (int z = 0; z <  i; z++)
				{
					if (alleZahlen[z] == false)
					{
						//System.out.println(""+z); 
						anzahl++;
					}
				}

				System.out.println(""+ endzeit + " Sekunden");
				System.out.println("Es wurden " + anzahl + " Primzahlen berechnet");
	}
}
```

Thread 2 gesamt:

```
package primzahlen;

public class Multithreading extends Thread 
{
	String name;
	int i;
	boolean[] alleZahlen;
	int wurzel;
	int b = 5;
	int z = 7;
	int k = 3;

	
	Multithreading(String s, int i, boolean[] alleZahlen, int wurzel)
	{
		this.name = s;
		this.i = i;
		this.alleZahlen = alleZahlen;
		this.wurzel = wurzel;
	}
	
	public void run()
	{
		for (int c = k * k; c < i; c += 2*k) 
		{					
			alleZahlen[c] = true;
		}
	}
}
```

Thread 3 gesamt:

```
package primzahlen;

public class Multithreading02 extends Thread 
{
	String name;
	int i;
	boolean[] alleZahlen;
	int wurzel;
	
	Multithreading02(String s, int i, boolean[] alleZahlen, int wurzel)
	{
		this.name = s;
		this.i = i;
		this.alleZahlen = alleZahlen;
		this.wurzel = wurzel;
	}
	
	public void run()
	{
		for (int b = 5; b <= wurzel; b += 6)
		{
			if (alleZahlen[b] == false)
			{
				for (int c = b * b; c < i; c += 2*b) 
				{
					
					alleZahlen[c] = true;
				}
			}
		}  
	}
}
```

Thread 4 gesamt:

```
package primzahlen;

public class Multithreading03 extends Thread 
{
	String name;
	int i;
	boolean[] alleZahlen;
	int wurzel;
	
	Multithreading03(String s, int i, boolean[] alleZahlen, int wurzel)
	{
		this.name = s;
		this.i = i;
		this.alleZahlen = alleZahlen;
		this.wurzel = wurzel;
	}
	
	public void run()
	{
		for (int m = 7; m <= wurzel; m += 6)
		{
			if (alleZahlen[m] == false)
			{
				for (int c = m * m; c < i; c += 2*m) 
				{
					alleZahlen[c] = true;
				}
			}
		}
	}
}
```

Schreibst du in Java oder in einer anderen Sprache?
Stell deine Code dann auch mal rein 
Gruß


----------



## Crysis nerd (10. Oktober 2015)

Ja, wie gesagt: In Rust 

Hier erstmal der super einfache Code: https://play.rust-lang.org/?gist=5a4b4dfb20829d58a1e6&version=nightly
Man kanns online ausführen, aber es läuft auf einem kastrierten Server irgendwo, also Geschwindigkeit kann man da nicht messen 
Dazu muss man das dann lokal kompilieren. Compiler und so gibts auf https://rust-lang.org


----------



## Roundy (10. Oktober 2015)

Ja wie lange brauchst du wenn dus bei dir ausführst?
Gruß


----------



## Crysis nerd (10. Oktober 2015)

Ca 1.5 Sekunden for 100Mio. (also den Code, den ich gepostet habe). Falls du selber kompilierst: Achte darauf, mit Optimierungen zu compilieren.

Hab gerade eine neue Version hinbekommen, die für 1Mrd auch 3,7s braucht, aber in einem Thread (code später)


----------



## Roundy (10. Oktober 2015)

Also für 100 mille brauch ich 0,37 sec


----------



## Bunny_Joe (10. Oktober 2015)

Ich frage mich gerade, um wie viel schneller das in OpenCL ablaufen würde...oder obs überhaupt sinnvoll von der GPU verarbeitet werden könnte.

edit:

Eben das hier gefunden: primesieve - Fast prime number generator
Für 10^9 braucht er gerade mal 0.03 Sekunden bei mir. Also ein ziemlich guter Algorithmus. Allerdings nur CPU.


----------



## nay (11. Oktober 2015)

Wäre es vielleicht noch interessant den Speicherverbrauch zu messen?


----------



## Crysis nerd (12. Oktober 2015)

Hatte übers Wochenende zu tun, aber hier noch mal meine aktuellen Ergebnisse.

Mein Programm ist immer noch single thread, nutzt aber jetzt "richtige" factorization wheel Optimierung. Die Werte für Primzahlen unter 1Mrd:



*Version*
 | 
*Zeit*
 | 
*Speicher*

wheel-2 | 4.1s | 67 MB
wheel-2-3 | 3.6s | 47 MB
wheel-2-3-5 | 2.7s | 39MB
wheel-2-3-5-7 | 2.35s | 35 MB

Speicher habe ich mit "/usr/bin/time -v" gemessen, die Zeit im Programm direkt.

Diese hochoptimierte C++ Version habe ich auch gefunden. Klar kann man noch jede Menge machen. Mal sehen, wie weit ich komme ohne vom idiomatischen Rust abzuweichen. Den Code für die Benchmarks gibt es übrigens hier: https://gist.github.com/LukasKalbertodt/b0dedf364263d99858cf

EDIT: Die  hochoptimierte C++ Version braucht 0.7 sek bei mir. Also ca Faktor 35 besser als meine beste...


----------



## nay (12. Oktober 2015)

Ich hab diese Version gefunden: https://github.com/kimwalisch/primecount

Braucht bei meinem i5 760 mit 4 Threads 0.01 Sekunden für Primzahlen bis 1 000 000 000. Wenn man das unterbieten will muss man sich warm anziehen


----------

