| Autor |
Beitrag |
    
Eulereuklid (Eulereuklid)
Junior Mitglied
Benutzername: Eulereuklid
Nummer des Beitrags: 10
Registriert: 08-2002
| | Veröffentlicht am Sonntag, den 14. Dezember, 2003 - 09:47: | 
|
Ich möchte hier mal einen kleinen Informatik-Wettbewerb starten:
Wer schreibt mir ein Programm welches schnellstmöglich eine Primzahltabelle in einen bestimmten Bereich "ausspuckt".
Mein Programm schafft bis jetzt alle Primzahl von 0 bis 1 Mio in 13 Sekunden und von 0 bis 10 Mio in 5:24 Minuten.
Wer kann das überbieten? |
Martin243 (Martin243)
Senior Mitglied
Benutzername: Martin243
Nummer des Beitrags: 939
Registriert: 02-2001
| | Veröffentlicht am Sonntag, den 14. Dezember, 2003 - 21:30: |
|
Hi!
Mein Programm schafft die Million in weniger als einer Sekunde und die 10 Millionen in 8 Sekunden.
Und nun möchte ich kurz erläutern, warum so ein Vergleich relativ wenig aussagekräftig ist:
- verschiedene Prozessoren, Speicher, Ausgabegeräte
Ich habe mein Ausgabefenster ganz klein gemacht, so dass die Ausgabe extrem schnell war.
Bei Ausgabe in eine Datei schafft es die 10 Mio. in ca. 2 Sekunden!
- verschiedene Sprachen, Compiler, Assembler etc.
Ich habe es in C programmiert, benutze gcc
- verschiedene Auslastungen der Rechner zur Laufzeit
Wonach man natürlich fragen kann, ist beispielsweise ein möglichst einfacher oder möglichst geschickter Algorithmus, der mit möglichst einfachen oder wenigen Operationen auskommt.
Wenn du willst, kannst du ja schreiben, in welcher Sprache dein Programm geschrieben ist und direkt den Quelltext bzw. den Algorithmus posten.
Dann kann ich hier auch meine sehr simple Lösung beisteuern...
MfG
Martin
Die Natur spricht die Sprache der Mathematik:
Die Buchstaben dieser Sprache sind Dreiecke, Kreise und andere mathematische Figuren.
Galileo Galilei
|
Eulereuklid (Eulereuklid)
Junior Mitglied
Benutzername: Eulereuklid
Nummer des Beitrags: 11
Registriert: 08-2002
| | Veröffentlicht am Montag, den 15. Dezember, 2003 - 17:24: |
|
Also ich habe ein Pascal-Programm. Ist im Grunde auch recht simpel. Es testet alle ungeraden Zahlen, es fängt also bei 3 an und erhöht in 2er Schritten (2 selbst ist natürlich gesondert, als Primzahl). Der eigentliche Test geht so:
Testzahl wird wieder nur durch alle ungeraden Zahlen geteilt und dabei geschaut, ob der Quotient ganzzahlig ist. Der Divisor wird so lange erhöht bis er so groß ist wie der Wurzel der Testzahl.
Den genauen Quelltext kann ich jetzt hier posten, da Turbo Pascal im DOS-Mode arbeitet und ich da nicht einfach kopieren und einfügen machen kann.
Ich wäre sehr an deinen Programm interessiert. |
Martin243 (Martin243)
Senior Mitglied
Benutzername: Martin243
Nummer des Beitrags: 942
Registriert: 02-2001
| | Veröffentlicht am Montag, den 15. Dezember, 2003 - 20:00: |
|
Hi!
Ich poste mal eine etwas veränderte Version des ursprünglichen Programms.
Das Prinzip kennst du bestimmt als das Sieb des Erastosthenes. Dabei streicht man immer alle Vielfachen der aktuellen Zahl weg und gibt dann die am Ende nicht durchgestrichenen aus. Dadurch muss man dann keinen Teilertest mehr machen.
Bei der Implementierung kann man das Ganze dann so angehen, dass man den Speicherplatz optimal nutzt. Da es in C keinen boolschen Datentyp gibt, nutzt man ints. Dabei passen in einen int 32 Wahrheitswerte hinein. Betrachtet man dabei nur ungerade Zahlen, dann erledigt man 64 aufeinanderfolgende natürliche Zahlen mit dem Speicherplatz für nur eine Integer-Zahl.
Wie auch immer: Wenn etwas unklar ist, einfach fragen.
Übrigens brauchte diese Version für alle Primzahlen bis 1 Mrd. 2 Minuten und 56 Sekunden. Das gab dann aber auch eine 527MB-Textdatei.
Leider leidet wahrscheinlich das Layout, wenn ich das hier einfach einfüge:
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#define MAX_N 1000000
#define BITS_PER_INT 32
int
main()
{
int i, j, m, n;
int arrSize = (MAX_N+1)/2/BITS_PER_INT + 1.5;
int *p = malloc(arrSize*sizeof(int));
FILE *f= fopen("primes.txt","w");
fprintf(f,"%d ",2);
for (i=3; i<sqrt(MAX_N); i+=2)
{
m=i/2/BITS_PER_INT;
n=i/2%BITS_PER_INT;
if ((p[m] & 1<<n) == 0)
{
fprintf(f,"%d ",i);
for (j=i;j<=MAX_N ; j+=2*i) //Inkrementierung um 2*i, da gerade Zahlen ausgeschlossen sind
{
m=j/2/BITS_PER_INT;
n=j/2%BITS_PER_INT;
p[m] = p[m] | (1<<n);
}
}
}
for (; i<MAX_N; i+=2)
{
m=i/2/BITS_PER_INT;
n=i/2%BITS_PER_INT;
if ((p[m] & 1<<n) == 0)
{
fprintf(f,"%d ",i);
}
}
fclose(f);
exit(0);
}
MfG
Martin
Die Natur spricht die Sprache der Mathematik:
Die Buchstaben dieser Sprache sind Dreiecke, Kreise und andere mathematische Figuren.
Galileo Galilei
|
Eulereuklid (Eulereuklid)
Junior Mitglied
Benutzername: Eulereuklid
Nummer des Beitrags: 12
Registriert: 08-2002
| | Veröffentlicht am Donnerstag, den 18. Dezember, 2003 - 17:23: |
|
Hab jetzt einige Tage nach einen C-Compiler gesucht und auch einige gefunden. Kriege damit dein Programm aber trotzdem nicht zum laufen, weil irgendein Fehler in der stdlib.h Bibliothek kommt. Kannst du mir irgend ein Compiler empfehlen oder das schon compilierte Programm an meine email-Adresse (tylerdurden104@web.de) schicken (genial,fände ich es wenn du eine Version schreibt,die dann Ober- und Untergrenze als manuelle Eingabe verlangt). |
Martin243 (Martin243)
Senior Mitglied
Benutzername: Martin243
Nummer des Beitrags: 955
Registriert: 02-2001
| | Veröffentlicht am Donnerstag, den 18. Dezember, 2003 - 19:23: |
|
Hi!
Ich benutze Cygwin, da ich ab und zu auch unter Linux programmiere. Da kann es sein, dass es da Unterschiede in der Standardbibliothek gibt.
Ich schicke dir gern das auführbare Programm zu, kann aber nicht garantieren, dass da nicht irgenwelche Bibliotheken fehlen. Ich versuche, das Pogramm so unabhängig zu machen wie möglich.
Zu Ober- und Untergrenze:
Eine Obergrenze einzubauen ist kein Problem, da ändert man nur die Schleifenparameter.
Bei der Untergrenze ist es nur möglich, einen Wert festzulegen, ab dem die Primzahlen ausgegeben werden. Zum Testen muss das Programm dennoch alle Zahlen von 1 bis Obergrenze durchlaufen. Also wird nur die Ausgabe kürzer, das Programm jedoch nicht schneller, wenn man die Untergrenze variiert.
Genaueres schreibe ich dir aber in der Mail.
MfG
Martin
Die Natur spricht die Sprache der Mathematik:
Die Buchstaben dieser Sprache sind Dreiecke, Kreise und andere mathematische Figuren.
Galileo Galilei
|
Murray (Murray)
Erfahrenes Mitglied
Benutzername: Murray
Nummer des Beitrags: 222
Registriert: 10-2001
| | Veröffentlicht am Montag, den 29. Dezember, 2003 - 09:56: |
|
BTW, lang lang ist es her ...
mein Amiga 500 mit 8 MB RAM spuckte mir damals nach 31 Sekunden Primzahlen bis 56 Millionen aus.
Das Ding hatte nur ein halbes MIPS (heute hab ich 2,5 GIPS und viel mehr RAM :-)
Erathostenes und Assembler machen's moeglich :-)
Cu, Onkel Murray
|
|
