INFO: Dieses Forum nutzt Cookies...
Cookies sind für den Betrieb des Forums unverzichtbar. Mit der Nutzung des Forums erklärst Du dich damit einverstanden, dass wir Cookies verwenden.

Es wird in jedem Fall ein Cookie gesetzt um diesen Hinweis nicht mehr zu erhalten. Desweiteren setzen wir Google Adsense und Google Analytics ein.


Antwort schreiben 

Primzahlen finden



Wenn dein Problem oder deine Frage geklärt worden ist, markiere den Beitrag als "Lösung",
indem du auf den "Lösung" Button rechts unter dem entsprechenden Beitrag klickst. Vielen Dank!

06.09.2011, 15:22 (Dieser Beitrag wurde zuletzt bearbeitet: 06.09.2011 15:51 von BNT.)
Beitrag #1

BNT Offline
LVF-Freak
****


Beiträge: 740
Registriert seit: Aug 2008

5.0 - 22Q3
1999
EN

64291
Deutschland
Primzahlen finden
Liebe LabVIEW Fans

Im Rahmen der Betreuung von Schülerpraktikanten lasse ich die Praktikanten zum Einstieg in LabVIEW immer die Primzahlen berechnen.

Aufgabe: Finde alle Primzahlen <= Maximum.

Eingabe: Maximum
Ausgabe:
- Anzahl der gefundenen Primzahlen
- Array mit den gefundenen Primzahlen
- Zeit in Sekunden, die zur Berechnung nötig waren.

Die Aufgabe stelle ich hiermit auch einmal in dieses Forum. Wer findet den schnellten Algorithmus im Sinne Ausführungszeit.
(Eine Array-Konstante mit den Primzahlen zurückgeben, gilt nicht!)

Mein Vergleichsrechner: Dell D830, Intel Core 2 Duo T7700@2.4GHz 3,5 GB RAM, Win XP SP 3, LabVIEW 2011

Es gilt folgende Vorgabe eines Schülerpraktikanten zu schlagen:
Maximum = 1000000
Zeit gemittelt über 100 VI-Aufrufe:
- Mean=833ms
- Std.Dev.=13ms
- Maximum=894ms
- Minimum= 814ms

   

Viel Spaß beim Programmieren. Dem Sieger gebührt Ruhm und Ehre.

Ich werde nach einer angemessesen Zeit die Lösung meines Praktikanten hier einstellen.

Gruß Holger

NI Alliance Partner & LabVIEW Champion
GnuPG Key: 6C077E71, refer to http://www.gnupg.org for details.
Webseite des Benutzers besuchen Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren to top
06.09.2011, 15:47 (Dieser Beitrag wurde zuletzt bearbeitet: 08.09.2011 15:27 von Y-P.)
Beitrag #2

GerdW Offline
______________
LVF-Team

Beiträge: 17.398
Registriert seit: May 2009

LV2021
1995
DE_EN

10×××
Deutschland
RE: Primzahlen finden
Hallo BNT,

nur bis 1Mio? Das ist nicht dein Ernst...

Anbei ein PDF mit Messwerten über einen weiten Bereich (x-Achse gibt Maximum in 2^x an, 20 entspricht in etwa deiner 1Mio). Ist schon was älter, der Core2 ist ein T5400 mit 1.6GHz. Und sind nicht meine schnellsten Algorithmen Smile

1Mio auf meinem aktuellen Core2Quad benötigen 11.5ms zum Rechnen (hauptsächlich zum Initialisieren der nötigen Datenstrukturen) und mit Ausgabe in ein Array ~50ms:
   

Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren to top
08.09.2011, 12:34 (Dieser Beitrag wurde zuletzt bearbeitet: 08.09.2011 12:39 von GerdW.)
Beitrag #3

GerdW Offline
______________
LVF-Team

Beiträge: 17.398
Registriert seit: May 2009

LV2021
1995
DE_EN

10×××
Deutschland
RE: Primzahlen finden
Hallo BNT,

kurzes Update (i5-2410M-2.3GHz):
Code:
Test: Prime_Generator, Bitarray
number    min    mean    max    result
100000    0,000656    0,000698    0,000795    9592
1000000    0,006362    0,006469    0,006619    78498

(min/mean/max in Sekunden, result = Anzahl der Primes)

Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren to top
08.09.2011, 15:03
Beitrag #4

BNT Offline
LVF-Freak
****


Beiträge: 740
Registriert seit: Aug 2008

5.0 - 22Q3
1999
EN

64291
Deutschland
RE: Primzahlen finden
Hallo GerdW
Das ist ein tolles Ergebnis.

Ich möchte darauf hinweisen, dass es sich bei dem Code, den ich zeigen werde, um denjenigen eines Schülerpraktikanten der Oberstufe handlet. Das Resultat hat er nach drei Stunden erreicht, LabVIEW lernen inklusive!

Ich möchte also allen LabVIEW Fans - auch den Anfängern - Mut machen[/i], zu versuchen, selbst eine Lösung zu finden. Die Laufzeit-Performanz ist bei einem solchen Algorithmus natürlich wesentlich.

Aber auch Lösungen mit wenigen Strukturen können interessant sein, weil sie vermutlich leicht zu verstehen und leicht zu warten sind. Verschiedene Lösungen geben auch Einblick in die Datenflussverarbeitung von LabVIEW. Also welche Programmierstrukturen sind effizient und welche nicht so sehr.

Ich habe die Metrik des VIs angehängt.

Gruß Holger


Angehängte Datei(en)
0.0 .txt  Primzahlen Metrik.txt (Größe: 492 Bytes / Downloads: 547)

NI Alliance Partner & LabVIEW Champion
GnuPG Key: 6C077E71, refer to http://www.gnupg.org for details.
Webseite des Benutzers besuchen Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren to top
08.09.2011, 15:28
Beitrag #5

Y-P Offline
☻ᴥᴥᴥ☻ᴥᴥᴥ☻
LVF-Team

Beiträge: 12.612
Registriert seit: Feb 2006

Developer Suite Core -> LabVIEW 2015 Prof.
2006
EN

71083
Deutschland
RE: Primzahlen finden
Bitte nicht wundern. Ich habe das PDF durch ein JPG ersetzt. Ist einfacher zu handhaben.

Gruß Markus

(06.09.2011 15:47 )GerdW schrieb:  Anbei ein PDF mit Messwerten über einen weiten Bereich (x-Achse gibt Maximum in 2^x an, 20 entspricht in etwa deiner 1Mio). Ist schon was älter, der Core2 ist ein T5400 mit 1.6GHz. Und sind nicht meine schnellsten Algorithmen Smile

--------------------------------------------------------------------------
Bitte stellt mir keine Fragen über PM, dafür ist das Forum da - andere haben vielleicht auch Interesse an der Antwort !!
--------------------------------------------------------------------------
Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren to top
09.09.2011, 09:04 (Dieser Beitrag wurde zuletzt bearbeitet: 17.09.2012 07:14 von jg.)
Beitrag #6

jg Offline
CLA & CLED
LVF-Team

Beiträge: 15.864
Registriert seit: Jun 2005

20xx / 8.x
1999
EN

Franken...
Deutschland
RE: Primzahlen finden
OK, mit GerdW kann ich nicht mithalten. Gehe ich recht in der Annahme, dass dein Algorithmus kein Trial-and-Error Test ist?!

Ich biete bei 1 Mio bei einem "Trial and Error"-Test mit etwas Knoff-Hoff:
Testsystem i7 unter Win7 / lv11_img
Bei expliziter Parallelisierung auf 2 Cores ca . 360 ms, ohne Parallisierung ca. 385 ms.

Testsystem Athlon X2 5050e (nicht gerade der Schnellste) unter WinXP / Lv10
Bei expliziter Parallelisierung auf 2 Cores ca . 700 ms, ohne Parallisierung ca. 985 ms.

Gruß, Jens

Wer die erhabene Weisheit der Mathematik tadelt, nährt sich von Verwirrung. (Leonardo da Vinci)

!! BITTE !! stellt mir keine Fragen über PM, dafür ist das Forum da - andere haben vielleicht auch Interesse an der Antwort!

Einführende Links zu LabVIEW, s. GerdWs Signatur.
Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren to top
Anzeige
09.09.2011, 09:23
Beitrag #7

GerdW Offline
______________
LVF-Team

Beiträge: 17.398
Registriert seit: May 2009

LV2021
1995
DE_EN

10×××
Deutschland
RE: Primzahlen finden
Hallo Jens,

nee, Trial&Error isses nicht, eher das gute alte Sieb!

Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren to top
09.09.2011, 09:32
Beitrag #8

jg Offline
CLA & CLED
LVF-Team

Beiträge: 15.864
Registriert seit: Jun 2005

20xx / 8.x
1999
EN

Franken...
Deutschland
RE: Primzahlen finden
(09.09.2011 09:23 )GerdW schrieb:  Hallo Jens,

nee, Trial&Error isses nicht, eher das gute alte Sieb!
Aha, dann muss ich nochmal zurück ans Reissbrett. Smile

Wer die erhabene Weisheit der Mathematik tadelt, nährt sich von Verwirrung. (Leonardo da Vinci)

!! BITTE !! stellt mir keine Fragen über PM, dafür ist das Forum da - andere haben vielleicht auch Interesse an der Antwort!

Einführende Links zu LabVIEW, s. GerdWs Signatur.
Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren to top
09.09.2011, 14:25 (Dieser Beitrag wurde zuletzt bearbeitet: 09.09.2011 14:26 von Lucki.)
Beitrag #9

Lucki Offline
Tech.Exp.2.Klasse
LVF-Team

Beiträge: 7.699
Registriert seit: Mar 2006

LV 2016-18 prof.
1995
DE

01108
Deutschland
RE: Primzahlen finden
1990 habe ich mal bei einem Preisausschreiben um das gleiche Problem bei einer PC-Zeitschrift mitgemacht und dafür ein Paket "Power-Basic deutsch" gewonnen. Es steht seitdem unbenutzt auf dem Dachbodenregal und verstaubt. Big Grin
Ich hatte es glaube ich so gemacht:
Eine Zahl N ist auf Primzahl zu untersuchen. Der Test für alle Zahlen <N wurde schon gemacht, das Array der bisher gefundenen Primzahlen liegt vor. Wenn N keine Primzahl ist und es werden Primfaktoren gefunden, dann muß einer der gefundenen Primfaktoren kleiner als SQRT(N) sein.
Man muß also die Zahl N durch die bisher gefunden Primzahlen im Bereich 2..SQRT(N) zu teilen versuchen. Wenn der Rest niemals Null ist, ist N eine neue Primzahl. Sowie ein Rest Null ist, wird die Suche abgebrochen werden und die nächste ungerade Zahl getestet.
So ungefähr, und vielleicht mit noch eine paar zusätzlichen Tricks, damit es so schnell wir möglich geht.
Mir diesem Hinweis sollte es doch möglich sein, es mit Gerd aufzunehmen!
Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren to top
09.09.2011, 14:35
Beitrag #10

GerdW Offline
______________
LVF-Team

Beiträge: 17.398
Registriert seit: May 2009

LV2021
1995
DE_EN

10×××
Deutschland
RE: Primzahlen finden
Hallo Lucki,

Zitat:So ungefähr, und vielleicht mit noch eine paar zusätzlichen Tricks, damit es so schnell wir möglich geht. Mir diesem Hinweis sollte es doch möglich sein, es mit Gerd aufzunehmen!
Nichts für ungut, aber das bezweifel ich! Die Q&R-Funktion (oder auch die Divide) sind dafür einfach zu langsam. Mit einem Sieb ist man da immer schneller - man muss nur genügend Speicher reservieren können. Wobei das heute auch kein großes Problem mehr darstellt: um alle Zahlen bis 2^32 zu sieben, benötigt man "nur" ~137MB für eine Routine "mittlerer" Geschwindigkeit. (Wenn's wirklich schnell sein soll, wären 2GB am Stück und ein 64bit-OS/LV nötig.)

1990 habe ich auch angefangen, an Primzahl-Algorithmen zu feilen. In den letzten 2 Jahrzehnten hat sich da einiges getan Smile

Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren to top
Antwort schreiben 


Möglicherweise verwandte Themen...
Themen Verfasser Antworten Views Letzter Beitrag
  Farbe finden und verfolgen snuz 3 6.642 25.05.2011 07:27
Letzter Beitrag: unicorn

Gehe zu: