Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Primzahlsieb in einer Bit-Version
Fiete - Di 06.03.12 11:33
Titel: Primzahlsieb in einer Bit-Version
Moin an alle Denker, das Programm arbeitet nur mit den ungeraden Zahlen.
Jede Zahl wird durch ein Bit(32) repräsentiert.
Die Manipulation erfolgt mit den Funktionen
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
| function TPrimZahl.TestBit(Zahl:Cardinal;BitNr:Byte):Boolean;
begin TestBit:=(((Zahl shr BitNr) and 1)=1) end;
function TPrimZahl.SetBit(Zahl:Cardinal;BitNr:Byte):Cardinal;
begin SetBit:=Zahl or (1 shl BitNr) end;
function TPrimZahl.ClrBit(Zahl:Cardinal;BitNr:Byte):Cardinal;
begin ClrBit:=Zahl and not(1 shl BitNr) end;
for i:=1 to SiebMax do Sieb[i]:=$FFFFFFFF; Wurzel:=trunc(sqrt(an/2+0.25)-0.5); |
Der Test mit Primzahlen bis 200.000.000 ergibt 11.078.937 Primzahlen in 3,53 sek.
Der Test mit Primzahlen bis 500.000.000 ergibt 26.355.867 Primzahlen in 9,83 sek.
Mit dem Verfahren nach Atkin dauert das Suchen 31,13sek.
Mein PC ist getaktet mit 3,19GHz
Diese Variante entstand zu DOS-Zeiten mit der 64K-Grenze(8-Bitversion)
Viel Spaß beim Studieren des Quelltextes
Gruß Fiete
Anlage: alle ungeraden Zahlen bis 100
1 3 5 7 9 11 13 15 17 19
21 23 25 27 29 31 33 35 37 39
41 43 45 47 49 51 53 55 57 59
61 63 65 67 69 71 73 75 77 79
81 83 85 87 89 91 93 95 97 99
Edit1: neue Version liegt vor
Tastaro - Di 06.03.12 12:07
Nett. Funktioniert astrein. Nur dein PC ist ne Gurke. :)
Mein Notebook (Intel Core i5 M460@2,53GHz) hier findet die Primzahlen bis 200.000.000 in 1,8s und die bis 500.000.000 in 4,94s.
Wohoooo!!! Mal überlegen was ich damit kompensieren könnte... :D
Beste Grüße
Santhro.
Regan - Di 06.03.12 13:59
Moin,
also man sollte definitiv nicht die "Primzahlen anzeigen" lassen. Das dauert ja Ewigkeiten :roll:
Sonst ähnliche Ergebnisse auch hier (i7 2630QM@2,00 GHz):
Quelltext
1:
2:
3:
| 200.000.000 in 1,3
500.000.000 in 3,62
1.000.000.000 in 7,70 |
Wobei die vier rechnenden Kerne nur bis zu 18% ausgelastet werden.
In dem Label steht, dass es Zahlen bis 9999999999 annimmt. Allerdings ist das gar kein gültiger Integerwert (bekomme es mit einem Fehler gemeldet).
Deshalb mal bei MaxInt ausprobiert:
Quelltext
1:
| 2.147.483.647 in 17,85 |
Ich habe ihm gerade auch das Anzeigen bei MaxInt nochmal zum Rechnen gegeben und melde mich, wenn es fertig ist.
Viele Grüße
Regan
Horst_H - Di 06.03.12 14:37
Hallo,
| Zitat: |
Der Test mit Primzahlen bis 200.000.000 ergibt 11.078.937 Primzahlen in 3,53 sek.
Der Test mit Primzahlen bis 500.000.000 ergibt 26.355.867 Primzahlen in 9,83 sek.
Mit dem Verfahren nach Atkin dauert das Suchen 31,13sek.
Mein PC ist getaktet mit 3,19GHz |
Das Verfahren nach Aitken ist doch wesentlich schneller.
http://www.delphi-forum.de/viewtopic.php?t=33013&postorder=asc&start=236
Meine Zeiten damals:
| Zitat: |
alzaimer s Sieb nach Atkins ist erheblich schneller. Ca. 4 sec fuer Primzahlen bis 1e9 , mein Programm fuer Turbo pascal 18.75 sec. Das sind 50,8 Mio Zahlen.
Gruss Horst
P.S.: 800 Mhz Duron. |
Gruß Horst
Fiete - Di 06.03.12 15:14
Moin Regan,
| Zitat: |
| In dem Label steht, dass es Zahlen bis 9999999999 annimmt. Allerdings ist das gar kein gültiger Integerwert |
Kleiner Fehler meinerseits :oops:
Verbesserung:
@Tastaro: meine Kiste ist ein alter Medion Anno 2005
Viele Grüße
Fiete
Tastaro - Di 06.03.12 15:16
 Fiete hat folgendes geschrieben  : |
@Tastaro: meine Kiste ist ein alter Medion Anno 2005
Viele Grüße
Fiete |
Dann ist mein Rechner doch nicht dazu geeignet etwas zu kompensieren. :(
afk Porsche kaufen
Regan - Di 06.03.12 15:25
| Fiete hat folgendes geschrieben : |
| Verbesserung: an,Bis:Int64; |
Kannst du das bitte nochmal als neue Version anhängen? Ich kann hier nichts kompilieren.
Fiete - Di 06.03.12 16:17
Moin Regan,
ist erledigt, viel Spaß
Gruß Fiete
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!