Prime

Übersicht

Sonstiges

Projekte

	Badudel Betreff: Prime	Do, Jun 10, 2010 20:51 Antworten mit Zitat
Hallo, hier möchte ich die Gelegenheit nutzen, um mein derzeitiges Programm vorzustellen: Prime Hinter diesem äußerst kreativen Namen verbirgt sich ein Programm, welches zum Berechnen von Primzahlen benutzt wird. Dabei wird das Prinzip des "Verteilten Rechnen", auch Distributed Computing genannt, verwendet. Das heißt, es arbeitet im Hintergrund und nutzt Ressourcen, welche nicht benötig werden. Was ist daran so besonders? Solche Programme gibt es viele. Doch der Witz an Prime ist nicht, irgendeine höchste Primzahl zu errechnen, sondern eine Liste, die bei 3 anfängt und nach oben hin offen ist. Per Netzwerk verständigen sich die einzelnen Programme miteinander, um zusammen so weit wie möglich zu kommen. Ein paar Stichwörter, damit es sich einfacher liest - Programmiert in BMax - Fortschritt 85% - Per Netzwerk gesteuert - Stringoperationen - Komprimierte Speicherung - Spezielle Arbeitsweise mit Packs (Siehe unten) - Einstellbarer Timer - Als Hintergrundprozess ausführbar Technik Prime zerstückelt und arbeitet mit Packages. Diese sind verschieden groß, deswegen kann ich hier keine genauere Angabe geben Folgendes Prinzip: Es gibt Self-Berechnungen, sowie Vergleichs-Berechnungen. Selfberechnung Die Selfberechnung eines Pakets fängt bei einer bekannten Zahl an, von der wir erst einmal ausgehen, dass es eine Primzahl ist. Dann wird so lange jede größere Zahl getestet, ob sie durch eine kleineren Zahl aus dieser Selfreihe teilbar ist. Wenn nicht, ist es eine potenzielle Primzahl und wird notiert. Dies wird so lange gemacht, bis wir (derzeit!) 10.000 Zahlen haben. Selbstverständlich sind das noch keine Primzahlen, die meisten der Zahlen fliegen noch raus - bei den Vergleichs-Berechnungen. Aber zuerst wird das Paket zurück auf den Server übertragen. Das erste Pack, das bei 3 beginnt, ist bereits nach der Selfberechnung fertig. Nun kann das zweite Pack selfberechnet werden. Ist auch dies fertig, ist das Paket selbst allerdings noch nicht fertig! Bei den Selfberechnungen werden nur ungerade Zahlen benutzt. Dadurch fliegen schon einmal alle Zahlen, die durch 2 teilbar sind, raus. Wenn man sich das genau ansieht, reicht es jetzt, jede Zahl mit allen vorherigen Primzahlen zu checken (da alle anderen Zahlen ja bereits durch eine vorhandene Zahl irgendwo anders drinstecken, 2 ist bereits ausgeschlossen). Dies nenne ich dann eine Vergleichs-Berechnung Die Vergleichsberechnung prüft ein Paket und schmeißt alle Zahlen, die durch eine andere Zahl (aus einem Vergleichspaket) teilbar sind, raus. Schlussendlich kriegen wir dann entweder ein fertiges Pack oder ein Pack heraus, dass weitere Berechnungen braucht. Beispiel: Paket 2 braucht nur noch eine VB (Vergleichsberechnung) mit Paket 1 Ist die VB fertig, so haben wir auch das Paket fertig gemacht. Wenn eine Selfberechnung von Pack 5 fertig ist, so sind die VB mit Pack 4,3,2 und 1 nötig. Dann ist auch dieses Paket fertig. Selbstverständlich berechnet nicht ein PC ein Paket, sondern macht immer nur entweder eine Selfberechnung oder eine VB. Dann wird wieder synchronisiert. Fortschritt Folgenden Arbeitsstand habe ich erreicht: - Self- und Vergleichsberechnungen funktionieren (näheres dazu später, auf jeden Fall kommen dabei Zwischen- oder Endergebnisse mit Primzahlen heraus) - Gesamte Kommunikation samt Aufgabenverteilung und Passwortabfrage - Optimierte Verwaltung, damit so wenig Traffic wie möglich verursacht wird Folgende Ziele habe ich mir noch gesetzt: - Datumsfunktion: Wird eine Aufgabe über einen längeren Zeitraum nicht abgeliefert, wird sie jemand Anderem zugewiesen - Zwischenspeicherung der Ergebnisse, damit bei längeren Aufträgen das Programm zwischenzeitlich geschlossen werden kann - Systemunabhängigkeit (line end characters) Folgende Probleme habe ich noch: - Derzeit arbeite ich mit einem maximalen Zahlenraum von 10.000 (ungeraden) Zahlen. Befindet sich dort aber keine neue Primzahl, so kommen keine neuen Ergebnisse Folgendes Ziel habe ich nicht - Das Einsehen der Zahlen auf einer Webspace (da komprimiert) - Ob man im Programm selbst einmal die Packs einsehen werden kann ist fraglich, da ich vorhabe, wegen Speicherplatzmangel hin und wieder vollständige Pakete vom Server zu holen. Soo, ein ausführlicher Beitrag. Wenn ich irgendetwas nicht gut erklärt habe, so werde ich mir Mühe geben, es noch einmal richtig zu machen. Bis dann dann!

Badudel

Betreff: Prime

Do, Jun 10, 2010 20:51
Antworten mit Zitat

Hallo,

hier möchte ich die Gelegenheit nutzen, um mein derzeitiges Programm vorzustellen:

Prime

Hinter diesem äußerst kreativen Namen verbirgt sich ein Programm, welches zum Berechnen von Primzahlen benutzt wird. Dabei wird das Prinzip des "Verteilten Rechnen", auch Distributed Computing genannt, verwendet. Das heißt, es arbeitet im Hintergrund und nutzt Ressourcen, welche nicht benötig werden.

Was ist daran so besonders?
Solche Programme gibt es viele. Doch der Witz an Prime ist nicht, irgendeine höchste Primzahl zu errechnen, sondern eine Liste, die bei 3 anfängt und nach oben hin offen ist.
Per Netzwerk verständigen sich die einzelnen Programme miteinander, um zusammen so weit wie möglich zu kommen.

Ein paar Stichwörter, damit es sich einfacher liest
- Programmiert in BMax
- Fortschritt 85%
- Per Netzwerk gesteuert
- Stringoperationen
- Komprimierte Speicherung
- Spezielle Arbeitsweise mit Packs (Siehe unten)
- Einstellbarer Timer
- Als Hintergrundprozess ausführbar

Technik
Prime zerstückelt und arbeitet mit Packages. Diese sind verschieden groß, deswegen kann ich hier keine genauere Angabe geben
Folgendes Prinzip: Es gibt Self-Berechnungen, sowie Vergleichs-Berechnungen.

Selfberechnung
Die Selfberechnung eines Pakets fängt bei einer bekannten Zahl an, von der wir erst einmal ausgehen, dass es eine Primzahl ist. Dann wird so lange jede größere Zahl getestet, ob sie durch eine kleineren Zahl aus dieser Selfreihe teilbar ist. Wenn nicht, ist es eine potenzielle Primzahl und wird notiert.
Dies wird so lange gemacht, bis wir (derzeit!) 10.000 Zahlen haben.
Selbstverständlich sind das noch keine Primzahlen, die meisten der Zahlen fliegen noch raus - bei den Vergleichs-Berechnungen. Aber zuerst wird das Paket zurück auf den Server übertragen.

Das erste Pack, das bei 3 beginnt, ist bereits nach der Selfberechnung fertig. Nun kann das zweite Pack selfberechnet werden. Ist auch dies fertig, ist das Paket selbst allerdings noch nicht fertig!
Bei den Selfberechnungen werden nur ungerade Zahlen benutzt. Dadurch fliegen schon einmal alle Zahlen, die durch 2 teilbar sind, raus.
Wenn man sich das genau ansieht, reicht es jetzt, jede Zahl mit allen vorherigen Primzahlen zu checken (da alle anderen Zahlen ja bereits durch eine vorhandene Zahl irgendwo anders drinstecken, 2 ist bereits ausgeschlossen).
Dies nenne ich dann eine

Vergleichs-Berechnung
Die Vergleichsberechnung prüft ein Paket und schmeißt alle Zahlen, die durch eine andere Zahl (aus einem Vergleichspaket) teilbar sind, raus. Schlussendlich kriegen wir dann entweder ein fertiges Pack oder ein Pack heraus, dass weitere
Berechnungen braucht.

Beispiel:
Paket 2 braucht nur noch eine VB (Vergleichsberechnung) mit Paket 1
Ist die VB fertig, so haben wir auch das Paket fertig gemacht.

Wenn eine Selfberechnung von Pack 5 fertig ist, so sind die VB mit Pack 4,3,2 und 1 nötig. Dann ist auch dieses Paket fertig.
Selbstverständlich berechnet nicht ein PC ein Paket, sondern macht immer nur entweder eine Selfberechnung oder eine VB. Dann wird wieder synchronisiert.

Fortschritt
Folgenden Arbeitsstand habe ich erreicht:

- Self- und Vergleichsberechnungen funktionieren (näheres dazu später, auf jeden Fall kommen dabei Zwischen- oder Endergebnisse mit Primzahlen heraus)
- Gesamte Kommunikation samt Aufgabenverteilung und Passwortabfrage
- Optimierte Verwaltung, damit so wenig Traffic wie möglich verursacht wird

Folgende Ziele habe ich mir noch gesetzt:

- Datumsfunktion: Wird eine Aufgabe über einen längeren Zeitraum nicht abgeliefert, wird sie jemand Anderem zugewiesen
- Zwischenspeicherung der Ergebnisse, damit bei längeren Aufträgen das Programm zwischenzeitlich geschlossen werden kann
- Systemunabhängigkeit (line end characters)

Folgende Probleme habe ich noch:

- Derzeit arbeite ich mit einem maximalen Zahlenraum von 10.000 (ungeraden) Zahlen. Befindet sich dort aber keine neue Primzahl, so kommen keine neuen Ergebnisse

Folgendes Ziel habe ich nicht

- Das Einsehen der Zahlen auf einer Webspace (da komprimiert)
- Ob man im Programm selbst einmal die Packs einsehen werden kann ist fraglich, da ich vorhabe, wegen Speicherplatzmangel hin und wieder vollständige Pakete vom Server zu holen.

Soo, ein ausführlicher Beitrag. Wenn ich irgendetwas nicht gut erklärt habe, so werde ich mir Mühe geben, es noch einmal richtig zu machen.
Bis dann dann!

Zuletzt bearbeitet von Badudel am Do, Jun 10, 2010 21:55, insgesamt einmal bearbeitet

	Thunder	Do, Jun 10, 2010 21:01 Antworten mit Zitat
Was für Mathefreaks^^ Hört sich gut an - ein Programm, dass Primzahlen errechnet ist eigentlich kein Problem, aber sowas über Netzwerk zu implementieren finde ich gut. Nur damit ich das nicht falsch verstehe: Zitat: Dann wird so lange jede größere Zahl getestet, ob sie durch eine kleineren Zahl aus dieser Selfreihe teilbar ist. Heißt das, du prüfst zB, wenn du die Zahl 10.000 auf Primzahl testest, jede (Prim)zahl vor 10.000 auf einen Modul ungleich 0? Oder prüfst du nur bis zur Quadratwurzel, wie es sich gehört? mfg Thunder
Meine Sachen: https://bitbucket.org/chtisgit https://github.com/chtisgit

Thunder

Do, Jun 10, 2010 21:01
Antworten mit Zitat

Was für Mathefreaks^^
Hört sich gut an - ein Programm, dass Primzahlen errechnet ist eigentlich kein Problem, aber sowas über Netzwerk zu implementieren finde ich gut.
Nur damit ich das nicht falsch verstehe:
Zitat:

Dann wird so lange jede größere Zahl getestet, ob sie durch eine kleineren Zahl aus dieser Selfreihe teilbar ist.

Heißt das, du prüfst zB, wenn du die Zahl 10.000 auf Primzahl testest, jede (Prim)zahl vor 10.000 auf einen Modul ungleich 0? Oder prüfst du nur bis zur Quadratwurzel, wie es sich gehört?

mfg Thunder

Meine Sachen: https://bitbucket.org/chtisgit https://github.com/chtisgit

	Badudel	Do, Jun 10, 2010 21:16 Antworten mit Zitat
Ich versteh nicht, warum??? Wurzel aus 100 ist 10. 100 ist durch 10 teilbar, aber auch durch 20 (und 20 ist größer als 10...) Oder habe ich dich falsch verstanden, und meinst, mein Programm testet eine Zahl auf Primzahl (weil das tut es nicht. Es erstellt eine Liste!)
Wir werden dem Schwein schon schlachten, auch wenn ihm quiekt. Zum Teufel mit das Grammatik!

Badudel

Do, Jun 10, 2010 21:16
Antworten mit Zitat

Ich versteh nicht, warum???
Wurzel aus 100 ist 10. 100 ist durch 10 teilbar, aber auch durch 20 (und 20 ist größer als 10...)

Oder habe ich dich falsch verstanden, und meinst, mein Programm testet eine Zahl auf Primzahl (weil das tut es nicht. Es erstellt eine Liste!)

Wir werden dem Schwein schon schlachten, auch wenn ihm quiekt.
Zum Teufel mit das Grammatik!

	Thunder	Do, Jun 10, 2010 21:37 Antworten mit Zitat
Anscheinend letzteres. Du sagst, dein Programm erstellt eine Liste die bei 3 anfängt. Was für eine Liste? Ich dachte es ist eine, in der Primzahlen eingetragen sind...
Meine Sachen: https://bitbucket.org/chtisgit https://github.com/chtisgit

Thunder

Do, Jun 10, 2010 21:37
Antworten mit Zitat

Anscheinend letzteres. Du sagst, dein Programm erstellt eine Liste die bei 3 anfängt. Was für eine Liste?
Ich dachte es ist eine, in der Primzahlen eingetragen sind...

Meine Sachen: https://bitbucket.org/chtisgit https://github.com/chtisgit

	Midimaster	Do, Jun 10, 2010 21:42 Antworten mit Zitat
naja, du kannst mit dem Ausprobieren immer schon bei der Wurzel aufhören, weil ja bei einer Division mit einer Zahl, die größer als die Wurzel wäre, ein Eregbnis herauskäme, das kleiner der Wurzel ist. Und das wäre ja dann schon vorher gefunden worden. 100:20 zu testen wäre nutzlos, weil das ja schon bei 100:5 aufgefallen wäre. Außerdem ist mir nicht klar ,warum man so wenige Primzahlen verteilt errechnen sollte. Die ersten 10.000 dauern bei meinem alten Notebook 37msec. Die ersten 100.000 nur 700msec. 1.000.000 nach 13 sec!!!

Midimaster

Do, Jun 10, 2010 21:42
Antworten mit Zitat

naja, du kannst mit dem Ausprobieren immer schon bei der Wurzel aufhören, weil ja bei einer Division mit einer Zahl, die größer als die Wurzel wäre, ein Eregbnis herauskäme, das kleiner der Wurzel ist. Und das wäre ja dann schon vorher gefunden worden.

100:20 zu testen wäre nutzlos, weil das ja schon bei 100:5 aufgefallen wäre.

Außerdem ist mir nicht klar ,warum man so wenige Primzahlen verteilt errechnen sollte. Die ersten 10.000 dauern bei meinem alten Notebook 37msec. Die ersten 100.000 nur 700msec. 1.000.000 nach 13 sec!!!

Zuletzt bearbeitet von Midimaster am Do, Jun 10, 2010 22:11, insgesamt einmal bearbeitet

	Badudel	Do, Jun 10, 2010 22:09 Antworten mit Zitat
@Thunder: Das Erstellen der Ausgangsliste ist natürlich wichtig, und mein Beispiel-Paket fing eben bei 3 an. Dann fliegen Zahlen raus, die keine Primzahlen sind. @Midimaster: Jetzt erinnere ich mich wieder. Hatte ich tatsächlich vergessen (bin ich nicht genial?...) Kommt auch noch rein. Wenn ich die Wurzelfunktion für Strings vereinfacht habe. Das verteilte Rechnen ist dann von Nöten, wenn die Primzahlen weiter auseinander liegen. Mit den Packgrößen brauche ich auch noch ein Bisschen, bis ich das richtig ausgetestet habe. Gruß!
Wir werden dem Schwein schon schlachten, auch wenn ihm quiekt. Zum Teufel mit das Grammatik!

Badudel

Do, Jun 10, 2010 22:09
Antworten mit Zitat

@Thunder: Das Erstellen der Ausgangsliste ist natürlich wichtig, und mein Beispiel-Paket fing eben bei 3 an. Dann fliegen Zahlen raus, die keine Primzahlen sind.

@Midimaster: Jetzt erinnere ich mich wieder. Hatte ich tatsächlich vergessen (bin ich nicht genial?...)
Kommt auch noch rein. Wenn ich die Wurzelfunktion für Strings vereinfacht habe.

Das verteilte Rechnen ist dann von Nöten, wenn die Primzahlen weiter auseinander liegen. Mit den Packgrößen brauche ich auch noch ein Bisschen, bis ich das richtig ausgetestet habe.

Gruß!

Wir werden dem Schwein schon schlachten, auch wenn ihm quiekt.
Zum Teufel mit das Grammatik!

	ToeB	Do, Jun 10, 2010 22:11 Antworten mit Zitat
Ohhhh wurzel ziehen Das haben wir mal in Matheinfo gemacht... Mit strings isses nicht so einfach (Halbierungsverfahren).... Dann müsstest du dir einen String "Devidierer" und "Mulriplizierer" und "Addierer" noch schreiben... mfg ToeB
Religiöse Kriege sind Streitigkeiten erwachsener Männer darum, wer den besten imaginären Freund hat. Race-Project - Das Rennspiel der etwas anderen Art SimpleUDP3.0 - Neuste Version der Netzwerk-Bibliothek Vielen Dank an dieser Stelle nochmal an Pummelie, welcher mir einen Teil seines VServers für das Betreiben meines Masterservers zur verfügung stellt!

ToeB

Do, Jun 10, 2010 22:11
Antworten mit Zitat

Ohhhh wurzel ziehen Very Happy

Das haben wir mal in Matheinfo gemacht... Mit strings isses nicht so einfach (Halbierungsverfahren).... Dann müsstest du dir einen String "Devidierer" und "Mulriplizierer" und "Addierer" noch schreiben...

mfg ToeB

Religiöse Kriege sind Streitigkeiten erwachsener Männer darum, wer den besten imaginären Freund hat.
Race-Project - Das Rennspiel der etwas anderen Art
SimpleUDP3.0 - Neuste Version der Netzwerk-Bibliothek
Vielen Dank an dieser Stelle nochmal an Pummelie, welcher mir einen Teil seines VServers für das Betreiben meines Masterservers zur verfügung stellt!

	Holzchopf Meisterpacker	Do, Jun 10, 2010 22:18 Antworten mit Zitat
Hast du den Downloadlink vergessen oder X? Wobei X für "Gibt noch keinen Downloadlink, der uns erlauben würde, daran teilzunehmen, wodurch dieser Thread hier eigentlich was für den WIP-Thread (oder Galerie) wäre" steht. mfG
Erledige alles Schritt um Schritt - erledige alles. - Holzchopf CC BY ♫ BinaryBorn - Yogurt ♫ (31.10.2018) Im Kopf da knackt's und knistert's sturm - 's ist kein Gedanke, nur ein Wurm

Holzchopf

Meisterpacker

Do, Jun 10, 2010 22:18
Antworten mit Zitat

Hast du den Downloadlink vergessen oder X? Wobei X für "Gibt noch keinen Downloadlink, der uns erlauben würde, daran teilzunehmen, wodurch dieser Thread hier eigentlich was für den WIP-Thread (oder Galerie) wäre" steht.

mfG

Erledige alles Schritt um Schritt - erledige alles. - Holzchopf
CC BY ♫ BinaryBorn - Yogurt ♫ (31.10.2018)
Im Kopf da knackt's und knistert's sturm - 's ist kein Gedanke, nur ein Wurm

	Midimaster Betreff: Primzahlen berechnen	Fr, Jun 11, 2010 8:16 Antworten mit Zitat
hier der Quellcode zu meiner Art die Primzahlen zu finden. Wie gesagt 10.000 in 37 msec: BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] SuperStrict ' Programm sucht n% Primzahlen ' hier n festlegen: Global N%=100 Global Zahl%=2, SquareRoot%, i%, Erfolg%, Zeile$, Last% Global Feld%[n+1] Feld%[0]=2 Global Zeit%=MilliSecs() Repeat ' diese Zahl auf Primzahl testen: Zahl=Zahl+1 ' Wurzel vorberechnen: SquareRoot=Sqr(Zahl) ' Zahl mit allen gefundenen Primzahlen testen: For i=0 To Last If (zahl Mod Feld[i]) = 0 Then Erfolg=1 Exit EndIf If Feld[i]>SquareRoot Then Exit Next ' wenn keinen Teiler gefunden, dann aufnehmen: If Erfolg=0 Then Last=Last+1 Feld[Last]=Zahl Else Erfolg=0 EndIf If Last>N Then Exit Until KeyHit(key_escape) ' Fertig: n Zahlen sind gefunden Zeit= MilliSecs()-Zeit For i=0 To n Zeile=zeile + " " + Feld[i] If Len(Zeile)>70 Then Print Zeile Zeile="" EndIf Next Print Print n+ " Primzahlen in " + zeit + " msec" Das Ausgeben der Zahlen erfolgt natürlich in einem zweiten Schritt, weil das sonst die Performance bremst. Während des Tests werden sie nur in Feld%[] gespeichert. Bei einem verteilten Test würde ich immer die untersten 10.000 Elemente (Grundfeld) in 38msec als Feld bei den Teilnehmern berechnen. Damit entstehen kaum Transportprobleme hinwärts und es kommen auch deutlich weniger Zahlen zurück. Mit dieser Vorbereitung checkst Du so 10.000 Zahlen beim Teilnehmer in 50msec. Mit dem Grundfeld erhältst du alle Primzahlen bis 104.743. Daraus ergibt sich, dass du jetzt alle Zahlen bis 104.743104.743, also bis 10.971.096.049 zweifelsfrei auf Primzahlen testen kannst. Bei einem Check beim Teilnehmer von z.b. ab Zahl 10.000.000 werden so ca. 138.000 Zahlen durchlaufen, bevor 10.000 Primzahlen gefunden sind. Und es kommen nur gültige Zahlen zurück zum Server. Ein endgültiger Test entfällt. Kritisch wird es erst, wenn der Teilnehmer z.b. eine Million Zahlen ab 10.971.000.000 testen will. Hier muss das Grundfeld erst bis SQR(10.972.000.000) erstellt werden. Hier noch ein Beispiel für eine zweistufige Analyse. Zunächst werden 10.000 Zahlen im Grundfeld berechnet, dann 100 Primzahlen ab der Zahl 10.000.000 gesucht: BlitzMax:* [AUSKLAPPEN] [EINKLAPPEN] SuperStrict ' Programm sucht n% Primzahlen ab der Zahl StartZahl% ' hier n festlegen: Global N%=100 Global Grundlage:Long =10000 Global StartZahl: Long =10000000 Global Zahl%=2, SquareRoot:Long, i%, Erfolg%, Zeile$, Last% Global Feld:Long[n+Grundlage+1] Feld[0]=2 Global Zeit%=MilliSecs() 'Vorbehandlung: die ersten Zahlen vorgeben Repeat Zahl=Zahl+1 SquareRoot=Sqr(Zahl) For i=0 To Last If (zahl Mod Feld[i]) = 0 Then Erfolg=1 Exit EndIf If Feld[i]>SquareRoot Then Exit Next If Erfolg=0 Then Last=Last+1 Feld[Last]=Zahl Else Erfolg=0 EndIf If Last>Grundlage-1 Then Exit Until KeyHit(key_escape) ' Fertig: die Grundlage ist vorbereitet Zahl=StartZahl Repeat ' diese Zahl auf Primzahl testen: Zahl=Zahl+1 ' Wurzel vorberechnen: SquareRoot=Sqr(Zahl) ' Zahl mit allen gefundenen Primzahlen testen: For i=0 To Last If (zahl Mod Feld[i]) = 0 Then Erfolg=1 Exit EndIf If Feld[i]>SquareRoot Then Exit Next ' wenn keinen Teiler gefunden, dann aufnehmen: If Erfolg=0 Then Last=Last+1 Feld[Last]=Zahl 'Print Zahl Else Erfolg=0 EndIf If Last>N+GrundLage Then Exit Until KeyHit(key_escape) ' Fertig: weitere n Zahlen sind gefunden Zeit= MilliSecs()-Zeit Print "folgende Zahlen sind Primzahlen:" For i= Grundlage+1 To (GrundLage + n) Zeile=zeile + " " + Feld[i] If Len(Zeile)>70 Then Print Zeile Zeile="" EndIf Next Print Print "Die Grunddatenbank reicht bis zur Primzahl: " + Feld[Grundlage] Print n+ " Primzahlen in " + zeit + " msec gefunden" Mit einem Grundfeld von 100.000 Elementen (ca 700msec) kannst du zweifelsfrei Zahlen bis 1.689.274.677.841 testen. Ein Test auf 10.000 Zahlen dauert da aber dann zwischen geschätzt 0.7 und 7 sec. Ob sich das verteilte Rechnen bereits lohnt ist fraglich, denn die Übertragung der Zahlen müßte in unter 3.5 sec durchgeführt werden können. Mit einem Grundfeld von 1.000.000 Elementen (ca 13 sec) kannst du zweifelsfrei Zahlen bis 239.812.076.741.689 testen. Ein Test auf 10.000 Zahlen dauert da aber dann geschätzt 7 bis 70 sec. Hier beginnt sich aber nun zum ersten Mal das verteilte Rechnen zu rentieren, da die Übetragung der Zahlen in unter 35 sec zu bewerkstelligen sein dürfte. Die ersten Primzahlen bis zur Zahl 100.000.000 würde ich auf dem eigenen Rechner erstellen. Hier lohnt sich das Verteilen echt noch nicht.

Midimaster

Betreff: Primzahlen berechnen

Fr, Jun 11, 2010 8:16
Antworten mit Zitat

hier der Quellcode zu meiner Art die Primzahlen zu finden. Wie gesagt 10.000 in 37 msec:

BlitzMax: [AUSKLAPPEN]

SuperStrict
' Programm sucht n% Primzahlen
' hier n festlegen:

Global N%=100


Global Zahl%=2, SquareRoot%, i%, Erfolg%, Zeile$, Last%
Global Feld%[n+1]
Feld%[0]=2
Global Zeit%=MilliSecs()

Repeat
	' diese Zahl auf Primzahl testen:
	Zahl=Zahl+1
	
	
	' Wurzel vorberechnen:
	SquareRoot=Sqr(Zahl)

	' Zahl mit allen gefundenen Primzahlen testen:
	For i=0 To Last
		If (zahl Mod Feld[i]) = 0 Then
			Erfolg=1
			Exit
		EndIf
		If Feld[i]>SquareRoot Then Exit 
	Next
	
	' wenn keinen Teiler gefunden, dann aufnehmen:
	If Erfolg=0 Then
		Last=Last+1
		Feld[Last]=Zahl
	Else 
		Erfolg=0
	EndIf
	If Last>N Then Exit
Until KeyHit(key_escape)
' Fertig: n Zahlen sind gefunden

Zeit= MilliSecs()-Zeit
For i=0 To n
	Zeile=zeile + " " + Feld[i]
  	If Len(Zeile)>70 Then 
		Print Zeile
		Zeile=""
	EndIf
Next
Print 
Print n+ " Primzahlen in " + zeit + " msec"

Das Ausgeben der Zahlen erfolgt natürlich in einem zweiten Schritt, weil das sonst die Performance bremst. Während des Tests werden sie nur in Feld%[] gespeichert.

Bei einem verteilten Test würde ich immer die untersten 10.000 Elemente (Grundfeld) in 38msec als Feld bei den Teilnehmern berechnen. Damit entstehen kaum Transportprobleme hinwärts und es kommen auch deutlich weniger Zahlen zurück. Mit dieser Vorbereitung checkst Du so 10.000 Zahlen beim Teilnehmer in 50msec.

Mit dem Grundfeld erhältst du alle Primzahlen bis 104.743. Daraus ergibt sich, dass du jetzt alle Zahlen bis 104.743*104.743, also bis 10.971.096.049 zweifelsfrei auf Primzahlen testen kannst.

Bei einem Check beim Teilnehmer von z.b. ab Zahl 10.000.000 werden so ca. 138.000 Zahlen durchlaufen, bevor 10.000 Primzahlen gefunden sind. Und es kommen nur gültige Zahlen zurück zum Server. Ein endgültiger Test entfällt.

Kritisch wird es erst, wenn der Teilnehmer z.b. eine Million Zahlen ab 10.971.000.000 testen will. Hier muss das Grundfeld erst bis SQR(10.972.000.000) erstellt werden.

Hier noch ein Beispiel für eine zweistufige Analyse. Zunächst werden 10.000 Zahlen im Grundfeld berechnet, dann 100 Primzahlen ab der Zahl 10.000.000 gesucht:
BlitzMax: [AUSKLAPPEN]

SuperStrict
' Programm sucht n% Primzahlen ab der Zahl StartZahl%
' hier n festlegen:

Global N%=100
Global Grundlage:Long =10000
Global StartZahl: Long =10000000

Global Zahl%=2, SquareRoot:Long, i%, Erfolg%, Zeile$, Last%
Global Feld:Long[n+Grundlage+1]
Feld[0]=2
Global Zeit%=MilliSecs()



'Vorbehandlung: die ersten Zahlen vorgeben
Repeat
	Zahl=Zahl+1
	SquareRoot=Sqr(Zahl)
	For i=0 To Last
		If (zahl Mod Feld[i]) = 0 Then
			Erfolg=1
			Exit
		EndIf
		If Feld[i]>SquareRoot Then Exit 
	Next
	If Erfolg=0 Then
		Last=Last+1
		Feld[Last]=Zahl
	Else 
		Erfolg=0
	EndIf
	If Last>Grundlage-1 Then Exit
Until KeyHit(key_escape)
' Fertig: die Grundlage ist vorbereitet


Zahl=StartZahl
Repeat
	' diese Zahl auf Primzahl testen:
	Zahl=Zahl+1
	
	
	' Wurzel vorberechnen:
	SquareRoot=Sqr(Zahl)

	' Zahl mit allen gefundenen Primzahlen testen:
	For i=0 To Last
		If (zahl Mod Feld[i]) = 0 Then
			Erfolg=1
			Exit
		EndIf
		If Feld[i]>SquareRoot Then Exit 
	Next
	
	' wenn keinen Teiler gefunden, dann aufnehmen:
	If Erfolg=0 Then
		Last=Last+1
		Feld[Last]=Zahl
		'Print  Zahl
	Else 
		Erfolg=0
	EndIf
	If Last>N+GrundLage Then Exit
Until KeyHit(key_escape)
' Fertig: weitere n Zahlen sind gefunden



Zeit= MilliSecs()-Zeit
Print "folgende Zahlen sind Primzahlen:"
For i= Grundlage+1  To (GrundLage + n)
	Zeile=zeile + " " + Feld[i]
  	If Len(Zeile)>70 Then 
		Print Zeile
		Zeile=""
	EndIf
Next
Print
Print "Die Grunddatenbank reicht bis zur Primzahl: " +  Feld[Grundlage]
Print n+ " Primzahlen in " + zeit + " msec gefunden"

Mit einem Grundfeld von 100.000 Elementen (ca 700msec) kannst du zweifelsfrei Zahlen bis 1.689.274.677.841
testen. Ein Test auf 10.000 Zahlen dauert da aber dann zwischen geschätzt 0.7 und 7 sec. Ob sich das verteilte Rechnen bereits lohnt ist fraglich, denn die Übertragung der Zahlen müßte in unter 3.5 sec durchgeführt werden können.

Mit einem Grundfeld von 1.000.000 Elementen (ca 13 sec) kannst du zweifelsfrei Zahlen bis 239.812.076.741.689
testen. Ein Test auf 10.000 Zahlen dauert da aber dann geschätzt 7 bis 70 sec. Hier beginnt sich aber nun zum ersten Mal das verteilte Rechnen zu rentieren, da die Übetragung der Zahlen in unter 35 sec zu bewerkstelligen sein dürfte.

Die ersten Primzahlen bis zur Zahl 100.000.000 würde ich auf dem eigenen Rechner erstellen. Hier lohnt sich das Verteilen echt noch nicht.

	Badudel	Fr, Jun 11, 2010 18:02 Antworten mit Zitat
Ursprünglich wollte ich keinen Download anbieten, weil man sowieso nicht wirklich viel sieht (dass es Pflicht ist, wusste ich nicht). Jetzt wollte ich es also machen, es gibt aber noch Probleme, BPlaced macht Zicken. Es kommt aber noch...
Wir werden dem Schwein schon schlachten, auch wenn ihm quiekt. Zum Teufel mit das Grammatik!

Badudel

Fr, Jun 11, 2010 18:02
Antworten mit Zitat

Ursprünglich wollte ich keinen Download anbieten, weil man sowieso nicht wirklich viel sieht (dass es Pflicht ist, wusste ich nicht).

Jetzt wollte ich es also machen, es gibt aber noch Probleme, BPlaced macht Zicken.
Es kommt aber noch...

Wir werden dem Schwein schon schlachten, auch wenn ihm quiekt.
Zum Teufel mit das Grammatik!

	GERMAX	Fr, Jun 11, 2010 20:19 Antworten mit Zitat
Primzahlen enden immer auf a)1,3,7,9 (für Zahl>9) ->60% aller Zahlen kann man daher von vornherein ausschliessen (0,2,4,5,6,8). zahl=zahl+1 ist zumindest für a) unnötig! besser: zahl=zahl+2 noch besser: zahl 5 nicht prüfen (das wären dann immerhin 20% weniger (von 1,3,5,7,9)) Edit: Habe noch kleine Änderungen vorgenommen!
Erfolglos begonnene BB-Projekte:TRON/CONVOY/MYSTIC

GERMAX

Fr, Jun 11, 2010 20:19
Antworten mit Zitat

Primzahlen enden immer auf

a)1,3,7,9 (für Zahl>9)

->60% aller Zahlen kann man daher von vornherein ausschliessen (0,2,4,5,6,8).

zahl=zahl+1 ist zumindest für a) unnötig!

besser: zahl=zahl+2

noch besser: zahl 5 nicht prüfen (das wären dann immerhin 20% weniger (von 1,3,5,7,9))

Edit: Habe noch kleine Änderungen vorgenommen!

Erfolglos begonnene BB-Projekte:TRON/CONVOY/MYSTIC

	Vincent	Sa, Jun 12, 2010 1:54 Antworten mit Zitat
Die kleinste Primzahl ist 2 .... und endet somit auf 2 ....
Gott ist nicht mit uns ... weil er mit Idioten keine Gnade kennt !

Vincent

Sa, Jun 12, 2010 1:54
Antworten mit Zitat

Die kleinste Primzahl ist 2 .... und endet somit auf 2 ....

Gott ist nicht mit uns ... weil er mit Idioten keine Gnade kennt !

	das wurgel Betreff: Re: Prime	Sa, Jun 12, 2010 2:09 Antworten mit Zitat
Badudel hat Folgendes geschrieben: - Stringoperationen Sind das Strings, wo z.B. als Text drin steht "1234", oder wird der volle Umfang von Strings benutzt, also ein Byte pro Buchstabe?
1 ist ungefähr 3

das wurgel

Betreff: Re: Prime

Sa, Jun 12, 2010 2:09
Antworten mit Zitat

Badudel hat Folgendes geschrieben:

- Stringoperationen

Sind das Strings, wo z.B. als Text drin steht "1234", oder wird der volle Umfang von Strings benutzt, also ein Byte pro Buchstabe?

1 ist ungefähr 3

	Midimaster	Sa, Jun 12, 2010 9:49 Antworten mit Zitat
@Germax BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] Zahl=Zahl+2 ...bringt noch ca 10% Performancegewinn. Das ist ein guter Vorschlag. Die REPEAT/UNTIL-Schleife wird 50% weniger aufgerufen. Da die gerade Zahlen aber sowieso schon beim Test mit FELD[0] herausfliegen würden, bleibt der Gewinn leider bei unter 10%. Die "5" herauszupicken wäre unsinning, denn es hiese, alle Zahlen vor dem eigentlichen MOD-Lauf auf MOD 5 testen. Die "5" fliegt sowieso spätestens nach dem Test mit FELD[2]raus: MOD 2 MOD 3 MOD 5 Das frühzeitige Herausnehmen der "5" spart also höchsten 3 MOD-Tests, kostet aber 5, weil jetzt alle Zahlen getestet werden.

Midimaster

Sa, Jun 12, 2010 9:49
Antworten mit Zitat

@Germax

BlitzMax: [AUSKLAPPEN]

Zahl=Zahl+2

...bringt noch ca 10% Performancegewinn. Das ist ein guter Vorschlag. Die REPEAT/UNTIL-Schleife wird 50% weniger aufgerufen. Da die gerade Zahlen aber sowieso schon beim Test mit FELD[0] herausfliegen würden, bleibt der Gewinn leider bei unter 10%.

Die "5" herauszupicken wäre unsinning, denn es hiese, alle Zahlen vor dem eigentlichen MOD-Lauf auf MOD 5 testen. Die "5" fliegt sowieso spätestens nach dem Test mit FELD[2]raus:

MOD 2
MOD 3
MOD 5

Das frühzeitige Herausnehmen der "5" spart also höchsten 3 MOD-Tests, kostet aber 5, weil jetzt alle Zahlen getestet werden.

	BtbN	Sa, Jun 12, 2010 11:18 Antworten mit Zitat
Du könntest auch eine BCD-Lib wie gmp verwenden. Hab mein altes modul dafür mal hochgeladen: https://www.blitzforum.de/upload/file.php?id=8790

BtbN

Sa, Jun 12, 2010 11:18
Antworten mit Zitat

Du könntest auch eine BCD-Lib wie gmp verwenden.
Hab mein altes modul dafür mal hochgeladen:

https://www.blitzforum.de/upload/file.php?id=8790

	Midimaster	Sa, Jun 12, 2010 12:10 Antworten mit Zitat
wieso kann er nicht einfach einen Block mit 10.000x 8 Bytes senden? Also LONG-Zahlen, die in einem Block oder Array vorliegen? Oder eine ZIP? Wieso Strings?

Midimaster

Sa, Jun 12, 2010 12:10
Antworten mit Zitat

wieso kann er nicht einfach einen Block mit 10.000x 8 Bytes senden? Also LONG-Zahlen, die in einem Block oder Array vorliegen? Oder eine ZIP?

Wieso Strings?

	BtbN	Sa, Jun 12, 2010 12:11 Antworten mit Zitat
Weil Longs bei weitem nicht genug kapazität haben.

BtbN

Sa, Jun 12, 2010 12:11
Antworten mit Zitat

Weil Longs bei weitem nicht genug kapazität haben.

	GERMAX	Sa, Jun 12, 2010 16:32 Antworten mit Zitat
Nehmen wir folgendes an (die kleineren Zahlen wurden vorher berechnet, dann wird mit diesen Prog-Teil weitergerechnet (und dafür braucht man gar kein mod x): Start bei zahl=9: zeile10: zahl=zahl+2--->11-->testen zahl=zahl+2--->13-->dto zahl=zahl+4--->17-->dto zahl=zahl+2--->19-->dto:goto zeile 10! Würde mal behaupten, dass das noch effektiver arbeitet!
Erfolglos begonnene BB-Projekte:TRON/CONVOY/MYSTIC

GERMAX

Sa, Jun 12, 2010 16:32
Antworten mit Zitat

Nehmen wir folgendes an (die kleineren Zahlen wurden vorher berechnet, dann wird mit diesen Prog-Teil weitergerechnet (und dafür braucht man gar kein mod x):

Start bei zahl=9:

zeile10:
zahl=zahl+2--->11-->testen
zahl=zahl+2--->13-->dto
zahl=zahl+4--->17-->dto
zahl=zahl+2--->19-->dto:goto zeile 10!

Würde mal behaupten, dass das noch effektiver arbeitet!

Erfolglos begonnene BB-Projekte:TRON/CONVOY/MYSTIC

Übersicht

Sonstiges

Projekte

Nach Oben

BlitzBasic Portal

Prime

Betreff: Prime

Betreff: Primzahlen berechnen

Betreff: Re: Prime