ich sah mich nun gezwungen das Sieb des Eratosthenes in einem von mir veränderten Algorithmus in c++ zu erstellen, hierbei wollte ich auch kurz demonstrieren was ich mit dynamischer Liste ( in der STL ist dies ein TemplateClass welche vector<T> heisst )
ich habe Testhalber mal versucht Primzahlen bis 200.000 zu erstellen nach ein paar Minuten habe ich dann einfach abgebrochen, weil es einfach zu lange dauert. Ich habe wie du siehst von vornherein die geraden Zahlen gemieden, und dann habe ich alle 2
verschachtelete Schleifen welche die Vielfachen ermitteln und diese aus der List ( vecotr<int> ) entfernen somit habe ich mit jedem äußeren durchlauf immer weniger elemente in der List (vector<int>). So das zu letzt die Liste (vector<int>)
nur noch die Primzahlen enthält.
Und dennoch muss ich sagen auch wenn der algorithmus nun dem Sieb entspricht und auch einige Modifikationen daran gemacht wurden, muss ich sagen das mir die Assembler variante einfach besser gefällt da diese extrem schnell ist.
Code: Alles auswählen
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> m_Sieb = vector<int>(5000);
// Explizites initialisieren des ersten Elements mit der ersten Primzahl
m_Sieb[0] = 2;
// Initialisiere vector(array) mit alle ungeraden Zahlen von 3 bis xxx
for (int i = 1; i < 5000; m_Sieb[i] = i++ * 2 + 1){}
vector<int>::iterator m_CurrentIndex = m_Sieb.begin();
m_CurrentIndex++; ///erfordelich da die Vielfachen von 2 nicht enthalten sind
while (m_CurrentIndex < m_Sieb.end())
{
if (*m_CurrentIndex != 0)
{
/// Dann bitte finden und eliminieren
vector<int>::iterator m_VielfacheIndex = m_CurrentIndex;
while (++m_VielfacheIndex < m_Sieb.end())
{
if (*m_VielfacheIndex%*m_CurrentIndex == 0)
{
//*m_VielfacheIndex = 0;
vector<int>::iterator tmpIterator = m_VielfacheIndex - 1;
m_Sieb.erase(m_VielfacheIndex);
m_VielfacheIndex = tmpIterator;
}
}
}
m_CurrentIndex++;
}
// *********************************** an diesem Punkt
m_CurrentIndex = m_Sieb.begin();
while (++m_CurrentIndex < m_Sieb.end())
{
cout << "Primzahl : " << *m_CurrentIndex << endl;
}
int m_Value;
cin >> m_Value; /// Total sinnlos einfach nur um die Konsole nicht sofort zu schliessen;
return 0;
}
ok die Zeile
if (*m_CurrentIndex != 0) ist unnötig da alle Felder bei dieser Zeile auf jeden Fall einen Wert haben, dies war ein Überbleibsel aus der Markierung mit 0 wo ich noch nicht die Liste (vector<int>) gelöscht hatte, aber diese unnötige Zeile sollte nicht allzuviel zusätzl. Taktzyklen erzeugen.
das sieb hat // *********************************** an diesem Punkt
nur noch eine Größe von 1229 elemente
dauer bis ca. 5 sekunden
Ich habe auch einfach mal etwas aus dem compilat (des c++ compilers ) rausgesucht.
Es geht schlichtweg nur um das initialisieren der Liste (vector<int>)
// Explizites initialisieren des ersten Elements mit der ersten Primzahl
m_Sieb[0] = 2;
00A16F0E push 0
00A16F10 lea ecx,[m_Sieb]
00A16F13 call std::vector<int,std::allocator<int> >::operator[] (0A115CDh)
00A16F18 mov dword ptr [eax],2
// Initialisiere vector(array) mit alle ungeraden Zahlen von 3 bis xxx
for (int i = 1; i < 5000; m_Sieb = i++ * 2 + 1){}
00A16F1E mov dword ptr [ebp-30h],1
00A16F25 jmp main+95h (0A16F45h)
00A16F27 mov eax,dword ptr [ebp-30h]
00A16F2A lea esi,[eax+eax+1]
00A16F2E mov ecx,dword ptr [ebp-30h]
00A16F31 push ecx
00A16F32 lea ecx,[m_Sieb]
00A16F35 call std::vector<int,std::allocator<int> >::operator[] (0A115CDh)
00A16F3A mov dword ptr [eax],esi
00A16F3C mov edx,dword ptr [ebp-30h]
00A16F3F add edx,1
00A16F42 mov dword ptr [ebp-30h],edx
00A16F45 cmp dword ptr [ebp-30h],1388h
00A16F4C jge main+0A0h (0A16F50h)
soviel zur optimalen umsetzung des compilers in Maschinensprache.
Ich glaube da musst du mir doch hoffentlich Recht geben, wenn ich sage das mit jeder Erkennung eines Vielfachen auch die Gesamtmenge der Liste(vector<int>) verringert wird, das das vom Sinn ( der heran gehensweise ) optimal sein müsste, darum ging es dir doch das
der Algorithmus im Vordergrund stand, mir ging es lediglich um die Geschwindigkeit.
Achso weil du ja nochmal nachgehakt hattest
Das Argument mit dem gegenläufigen Verhalten verstehe ich nicht? Was verhält sich da gegenläufig? `r10` wird in jedem Durchlauf erhöht und `rax` bleibt doch wohl hoffentlich immer gleich,
nämlich der Kandidat der auf prim getestet wird. Und für den Fall, dass er das *ist*, wird `r10` bis zur Primzahl und nur bis zur Wurzel hochgezählt, was unnötig ist.
Das Hochzählen um 1 ist auch nicht besonders glücklich, weil man die Anzahl der Divisionen für einen Kandidaten locker mal halbieren kann, wenn man erst auf Teilbarkeit durch 2 testet, und dann nur noch ungerade Testdivisionen rechnet.
hier nochmal die Sequenz
@Weiter:
xor rdx, rdx
MOVE_PARAM rax, 1
div r10
cmp rdx, 0
jz @NoPrime
inc r10
cmp r10, rax
jb @Weiter
kurze Erklärung:
divident ist im Registerpaar rdx:rax
divisor ist im Register r10
nach efolgter divison (div r10)
ist Quotient im Reigster RAX ( den ich dann als Prüfbedingung im cmp Befehl verwenden werde )
und Remainder (Rest) im Register RDX
jetzt prüfe ich ob es keinen Rest gegeben hat und falls die Bedingung zutrifft springe ich zu NoPrime
ansonsten erhöhe ich r10
und prüfe ob divisor < als Quotient ( denn die Vielfachen des Quotienten brauchen ja nicht mehr geprüft zu werden daher zähle ich nie bis n komplett hoch )
wenn das so ist dann springe auf Weiter, falls nein ist es eine Primzahl
Beispiel:
die Zahle 101 = Primzahl
zuvor
r10 = 2
1. Schleifendurchlauf
rdx = 0
rax = 101
-> div r10
rdx = 1
rax = 50
-> cmp rdx, 0
-> nein also nicht springen
-> inc r10
r10 = 3
-> cmp r10, rax (3 < 50)
-> jb @Weiter ( sprung wird ausgeführt )
2. Schleifen durchlauf
rdx = 0
rax = 101
-> div r10
rdx = 2
rax = 33
-> cmp rdx, 0
-> nein also nicht springen
-> inc r10
r10 = 4
-> cmp r10, rax (4 < 33)
-> jb @Weiter ( sprung wird ausgeführt )
3. Schleifen durchlauf
rdx = 0
rax = 101
-> div r10
rdx = 1
rax = 25
-> cmp rdx, 0
-> nein also nicht springen
-> inc r10
r10 = 5
-> cmp r10, rax (5 < 25)
-> jb @Weiter ( sprung wird ausgeführt )
4. Schleifen durchlauf
rdx = 0
rax = 101
-> div r10
rdx = 1
rax = 20
-> cmp rdx, 0
-> nein also nicht springen
-> inc r10
r10 = 6
-> cmp r10, rax (6 < 20)
-> jb @Weiter ( sprung wird ausgeführt )
5. Schleifen durchlauf
rdx = 0
rax = 101
-> div r10
rdx = 5
rax = 16
-> cmp rdx, 0
-> nein also nicht springen
-> inc r10
r10 = 7
-> cmp r10, rax (7 < 16)
-> jb @Weiter ( sprung wird ausgeführt )
6. Schleifen durchlauf
rdx = 0
rax = 101
-> div r10
rdx = 3
rax = 14
-> cmp rdx, 0
-> nein also nicht springen
-> inc r10
r10 = 8
-> cmp r10, rax (8 < 14)
-> jb @Weiter ( sprung wird ausgeführt )
7. Schleifen durchlauf
rdx = 0
rax = 101
-> div r10
rdx = 5
rax = 12
-> cmp rdx, 0
-> nein also nicht springen
-> inc r10
r10 = 9
-> cmp r10, rax (9 < 12)
-> jb @Weiter ( sprung wird ausgeführt )
8. Schleifen durchlauf
rdx = 0
rax = 101
-> div r10
rdx = 2
rax = 11
-> cmp rdx, 0
-> nein also nicht springen
-> inc r10
r10 = 10
-> cmp r10, rax (10 < 11)
-> jb @Weiter ( sprung wird ausgeführt )
9. Schleifen durchlauf
rdx = 0
rax = 101
-> div r10
rdx = 1
rax = 10
-> cmp rdx, 0
-> nein also nicht springen
-> inc r10
r10 = 11
-> cmp r10, rax (11 < 10
-> jb @Weiter ( sprung wird NICHT ausgeführt )
-> Ende der Prüfungen die Zahl 101 ist eine Primzahl ( dazu habe ich insgesamt 9 mal die Schleife durchlaufen und wenn man dann analysiert kommt folgende Formel heraus : (Wurzel aus N)-1 divisionen ( im max. Fall )
Ich hoffe jetzt ist es ein bisschen transparenter
Viele Grüße
DT
)
.
.
.