Primzahlen Contest

Roundy

Roundy

BIOS-Overclocker(in)
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 :D

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ß
 
Zuletzt bearbeitet:
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.
 
AW: Array Anfangswert mitgeben [Java]

Hab mitlerweile nen anderen weg gefunden, mal schauen ob ichs am ende mit multithreading doch schneller hinbekomm...
Gruß
 
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.
 
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ß
 
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).
 
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ß
 
AW: Array Anfangswert mitgeben [Java]

So kleines Update.. ich habe es geschafft :D

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ß
 
Zuletzt bearbeitet:
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.
 
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:
Code: 
 int m = 2;	
            
    				for (int c = m * 2; c < i; c += m) 
    				{
                   
    					                       	
    						alleZahlen[c] = true;
                       	
    				}

Thread 2:

Code: 
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:

Code: 
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:
Code: 
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ß
 
Zuletzt bearbeitet:
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?
 
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ß
 
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 :P 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
 
AW: Array Anfangswert mitgeben [Java]

die primzahlen stimmen ;D
hier der Code:

Thread 1 gesamt:
Code: 
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:
Code: 
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:
Code: 
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:
Code: 
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ß
 
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)
 
Du musst dich einloggen oder registrieren, um hier zu antworten.

Ähnliche Themen

A
Wird eine neue Grafikkarte mich glücklich machen?
Antworten
13
Aufrufe
1K
EM_EN
EM_EN
I
Neuer Gamer oder Office plus sinnvolle Nutzung ältere Komponenten???
Antworten
3
Aufrufe
1K
Gast1738105801
G
ivory2k17
Tagebuch [Worklog] Neubau eines alten Bekannten Projekt "Battlefield"
Antworten
4
Aufrufe
1K
ivory2k17
ivory2k17
W
Gamingrechner - Warten hat Lehrgeld gekostet - nun gehts los.
2
Antworten
34
Aufrufe
3K
Hellhammer
Hellhammer
Karnstein
Frage zum PPT beim 7800X3D, Thermal Throttling und Cinebench R23 Last
Antworten
8
Aufrufe
663
cryon1c
cryon1c
Oben Unten
Zurück