Wer findet den schnellsten Primzahlalgorithmus

[Lord Nikon]

Hi,
es sind alle Programmiersprachen erlaubt , die unter Windows laufen.
Bei der Prüfung von 1 bis 30000 braucht mein Algorithmus 6,529 Sekunden inklusive der grafischen Ausgabe aller Primzahlen in einem Memofeld. Die Programmiersprache ist bei mir c++. Es ist gedacht, das jeder selbst einen Algorithmus programmiert, so dass man sich über Optimierungen im Quelltext diskutiert werden kann.

[Stone2001]

hmm, wenn du wirklich den schnellsten Primzahlenalgorithmus haben willst, wäre es nicht schlecht, wenn du:
- ein Rahmenprogramm vorgibst,
- mal sagst, was für einen Rechner du hast
Denn, ein gleiches Programm läuft auf unterschiedlichen Rechnern unterschiedlich schnell und ich denke, das die Ausgabe den größten Anteil an der Rechenzeit hat.

[Lord Nikon]

Rechner:
Mainboard: ECS K7S5A
CPU: Athlon Xp 1600
Ram: 256 Mb Nanya und 256 Mb Infineon DDR Ram
Grafikkarte: GeForce4 Ti 4200 von MSI

Die Programmiesprache sollte zur Vergleichbarkeit in c++ sein.

[DocEW]

Original geschrieben von Lord Nikon
Bei der Prüfung von 1 bis 30000 braucht mein Algorithmus 6,529 Sekunden inklusive der grafischen Ausgabe aller Primzahlen in einem Memofeld.
Ui, das ist aber lang! =)
Also ich habe jetzt gerade mal schnell (ehrlich, 5 Minuten) in Java was zusammengehackt, und es braucht deutlich unter 100ms. Die Funktion System.currentTimeMillis() mag ungenau sein, aber bei einer Ausgabe von meistens ca. 15ms behaupte ich mal daß ich schneller bin! :D

Hier noch der Algorithmus:

public class Primzahl {

static boolean[] nonPrims = new boolean[30000];
static long timeBegin;
static long timeEnd;

public static void main(String[] args) {

timeBegin = System.currentTimeMillis();
for (int i = 2; i < nonPrims.length / 2; i++) {

for (int j = 2; j * i < nonPrims.length; j++) {

nonPrims[j*i] = true;

}
}
timeEnd = System.currentTimeMillis();

for (int i = 0; i < nonPrims.length; i++) {

if ( !nonPrims[i] ) {
System.out.print(i + " ");
}

}
System.out.println("\n\nEs wurden " + (timeEnd-timeBegin) + " ms benötigt.");
}

}


P.S.: Athlon XP 2400+ und einfach mit Eclipse (JDK 1.3.1) laufen lassen...

/EDIT1:
Achja, das Feld heißt "nonPrims", weil ich es andernfalls alles mit "true" hätte initialisieren müssen... ;)

/EDIT2:
Vielleicht noch zwei etwas "größere" Werte: Für 10000000 braucht er ca. 5 Sekunden, bei 50000000 27 Sekunden und bei 100000000 ist dann der Speicher zu klein - das passiert dir wahrscheinlich mit deiner Methode nicht (ich nehme an, du prüfst tatsächlich in irgendeiner Form jede einzelne Zahl)

[DocEW]

Noch 'ne kleine Verbesserung mit (relativ) großer Wirkung:

In der ersten Schleife eine zusätzliche IF-Abfrage:

for (int i = 2; i <= 2*Math.sqrt(nonPrims.length); i++) {

if ( !nonPrims[i] ) {
for (int j = 2; j * i < nonPrims.length; j++) {

nonPrims[j*i] = true;

}
}
}


Ergebnisse damit:
10000000 -> 1,2 s
50000000 -> 5,6 s

/EDIT:
Und vielleicht zur Kontrolle: Von 1 bis 50000000 findet er bei mir 3001135 Primzahlen, incl. 1 und 2. Kommt zumindest grob hin mit der Formel pi(n) ~ n/(ln(n)-C) mit C= 1,08366...

[Stone2001]

Meine Java-Kenntnisse sind recht bescheiden, aber könntest du mir erklären, wo bei dir die "Graphische Ausgabe" ist!
Weil, ich vermute stark das Lord Nikon, die Zeit mitzählt, die er noch braucht, um die Zahlen auszugeben.
(Falls er das nicht tut, hat er wohl den ineffizientesten Primzahlen-Alogrithmus gefunden, den ich kenne ;) )

[DocEW]

Ich weiß nicht genau, was du mit "Graphische Ausgabe" meinst. Also dieses Stückchen hier

for (int i = 0; i < nonPrims.length; i++) {

if ( !nonPrims[i] ) {
System.out.print(i + " ");
}
}

gibt halt die Zahlen aus. Eine graphische Ausgabe war ja nicht gefordert, oder?
Ich finde es übrigens nicht besonders sinnvoll, die Ausgabe noch mitzustoppen. Es soll ja der Algorithmus zur Primzahlbestimmung verglichen werden und nicht der GUI-Speed verschiedener Sprachen, oder? =)
Vielleicht kann Lord Nikon das ja noch ändern.

[HellHorse]

Text zählt doch auch als Graphik? :D
Mit GUI macht es dann natürlich einen grossen Unterschied, ob man für jede einzelene gefundene Primzahl das GUI updated und wartet bis das gesehen ist, oder ob man erst am Ende das GUI updatet.


hmm, ein paar Minuten zu spät :(

[Stone2001]

Eine graphische Ausgabe war nur implizit gefordert, da sonst die Vergleichbarkeit der Algorithmen nicht gewährleistet wäre. ;)
Und eine Ausgabe in einer DOS-Box zähle ich noch lange nicht zu einer graphischen Ausgabe! ;)

Und natürlich macht es keinen Sinn, die Ausgabe auch zu stoppen! Naja, jetzt müssen wir nur noch einen finden, der die Algorithmen test, damit wir alle ein einheitliches System haben.

[DocEW]

Zählen auch probabilistische Algorithmen? Hab da noch 'nen Monte-Carlo Algorithmus in meinem Info-Buch, den könnte ich mal ausprobieren... liefert dann aber leider nur so eine Aussage wie: "Das hier sind mit 99,92% Wahrscheinlichkeit alles Primzahlen." :D
Könnte aber auch ziemlich schnell sein.

[zeckensack]

Das Sieb des Erastothenes ist Scheiße, ganz große Scheiße.

Bencht und staunt:
#include <vector>
#include <time.h>
#include <math.h>

typedef unsigned int uint;
const uint max_range=10000000;

int
main()
{
clock_t start_time=clock();
std::vector <uint> primes;

primes.push_back(2);

uint num_primes=1;
uint max_divisor_ix=0;

uint n=3;
while (n<max_range)
{
uint max_div2=primes[max_divisor_ix];
max_div2*=max_div2;
while (n<=max_div2)
{
for (uint i=1;i<=max_divisor_ix;++i)
{
if ((n%primes[i])==0) goto nope;
}
primes.push_back(n);
nope:
n+=2;
}
++max_divisor_ix;
}

clock_t end_time=clock();
double elapsed=(end_time-start_time)/CLOCKS_PER_SEC;

printf("found %u primes in %f seconds\n",primes.size(),elapsed);
printf("stopped searching at %u\n",n-2);

printf("biggest found prime is %d!\n",primes.back());

return(0);
}

Zahlenraum bis 1 Mio unterhalb der Meßbarkeit (<1 Sekunde).
Zahlenraum bis 10 Mio in sieben Sekunden.
Dabei wurden 664861 Primzahlen gefunden, die größte war 10004557. Ja, der Algo läuft etwas zu weit :)
(XP2400+, KT266A, Forum inklusive Flash-Banner lief im Hintergrund)

[DocEW]

Schneller als meins ist es ja nicht... hat aber natürlich den Vorteil des geringeren Speicherbedarfs.
Wenn ich meins bis 10004557 laufen lasse bekomme ich übrigens eine Primzahl mehr... naja egal, "Meßfehler"... :D
Das ganze dauert dann (ebenfalls mit ein paar Browserfenster, FlashGet, Virenscanner usw.) ca. 1 Sekunde.

[DocEW]

Original geschrieben von zeckensack
Das Sieb des Erastothenes ist Scheiße, ganz große Scheiße.
Warum? Nur weil's in der Anwendung nach oben beschränkt ist? Ich find's schnell und einfach. Und bis 30000 (s.o. Threadthema) reicht's ja locker.

[HellHorse]

@DocEW
Ich weiss nicht, wie clever javac ist, aber ev wird
2*Math.sqrt(nonPrims.length)
bei jedem Durchgang ausgegrechnet. Vielleicht machst du eine Variable mit diesem Wert.
Auch kannst du mal versuchen das Array final zu machen. Soll schneller sein, k.A. ob's was bringt.

Und dann habe ich noch folgenden Vorschlag
statt

for (int j = 2; j * i < nonPrims.length; j++) {

nonPrims[j*i] = true;

}

versuche mal

int j = 2 * i;
while (j <= nonPrims.length) {
nonPrims[j] = true;
j += i;
}

statt 2mal *, bloss 1mal + und dann ev noch j vor dem for definieren.
Das ist alles, was mir bis jetzt eingefallen ist.

[DocEW]

Original geschrieben von HellHorse
@DocEW
Ich weiss nicht, wie clever javac ist, aber ev wird
2*Math.sqrt(nonPrims.length)
bei jedem Durchgang ausgegrechnet. Vielleicht machst du eine Variable mit diesem Wert.
Ahhh, das war Quatsch. 2* ist noch vom Testen übrig geblieben. Da hatte ich geguckt, ob Math.sqrt(...) auch wirklich reicht! ;)

Original geschrieben von HellHorse
Auch kannst du mal versuchen das Array final zu machen. Soll schneller sein, k.A. ob's was bringt.
Jo, hast recht. Bringt eine Verbesserung von 1,1 auf 1 Sekunde, soweit man das bei der Genauigkeit überhaupt messen kann.

Original geschrieben von HellHorse
Und dann habe ich noch folgenden Vorschlag
statt

for (int j = 2; j * i < nonPrims.length; j++) {

nonPrims[j*i] = true;

}

versuche mal

int j = 2 * i;
while (j <= nonPrims.length) {
nonPrims[j] = true;
j += i;
}

statt 2mal *, bloss 1mal + und dann ev noch j vor dem for definieren.
Das ist alles, was mir bis jetzt eingefallen ist.
Ich hab's jetzt so:

int temp; // außerhalb deklariert (Klassenvariable)
(...)
for (int j = 2,temp=j*i; temp < nonPrims.length; j++) {

nonPrims[temp] = true;
temp = j*i;
}

j+=i funktioniert aber nicht, da muß schon j++ stehen.

Danke für die Tipps!

[zeckensack]

Original geschrieben von DocEW
Schneller als meins ist es ja nicht... hat aber natürlich den Vorteil des geringeren Speicherbedarfs.
Wenn ich meins bis 10004557 laufen lasse bekomme ich übrigens eine Primzahl mehr... naja egal, "Meßfehler"... :DJapp. Die "1" wird nicht mitgezählt.
Das ganze dauert dann (ebenfalls mit ein paar Browserfenster, FlashGet, Virenscanner usw.) ca. 1 Sekunde. Das Sieb???
Sorry, aber das glaube ich dir einfach nicht.
Vielleicht doch eher der Monte Carlo?

[zeckensack]

Original geschrieben von DocEW
Warum? Nur weil's in der Anwendung nach oben beschränkt ist? Ich find's schnell und einfach. Und bis 30000 (s.o. Threadthema) reicht's ja locker. Es skaliert nicht. Der Algorithmus wurde unter der Annahme entworfen, daß Speicherzugriffe unendlich schnell sind, und Division (bzw Modulo) unendlich teuer. Beides ist Quatsch, insbesondere auf aktuellen Rechnern.

[KiBa]

@zecke
zwei anmerkungen zum code:
1. besser die standard-header <ctime> und <cmath> nehmen, da kommen die meisten compiler mit klar.
2. ersetz mal im code folgende zeile:
double elapsed=double(end_time-start_time)/CLOCKS_PER_SEC; dann gibts genauere zahlen (milisekundenbereich statt ganzer sekunden)

zum ergebnis: auf meinem 1333er athlon dauerts gut 10s.
der sieb-algo mag ja nicht so gut skalieren, aber für die gegebenen anforderungen ist er ideal, da keine speicherbegrenzung vorgegeben ist. (und der ist wirklich so schnell)
hab mich um die speicherproblematik mal gekümmert und einen "verbessertes sieb"-algo vor ca. 2 jahren geschrieben. (hab mich da mit c++ noch nicht so gut ausgekannt, also gnade bitte) dieser läuft bei zahlen bis 10.000.000 glatt 10mal schneller als deiner... beweis:

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <ctime>
using namespace std;

typedef unsigned Number;

const Number mem = 25000;
const Number test = 10000000 + mem;

int main()
{
clock_t start_time = clock();

cout << "Speicherbelegung..." << endl << endl;
vector<Number> prim, pm(mem);

cout << "Berechnung..." << endl << endl;
for (Number i = 0; i < (test - 1) / mem; ++i)
{
const Number begin = mem * i + 2, end = mem * i + mem + 1;
for (Number j = 0; j < mem; ++j) pm[j] = begin + j;

for (Number j = 2; j <= sqrt(double(end)); j == 2 ? ++j : j += 2)
if (!i || binary_search(prim.begin(), prim.end(), j))
{
Number p = begin / j;
if (begin % j) p++;
if (!i) p++;
Number t;
while ((t = j * p++) <= end) pm[(t - 2) % mem] = 0;
}

for (Number j = 0; j < mem; ++j) if (pm[j]) prim.push_back(pm[j]);
if (!((i + 1) % 100)) cout << (i + 1) / ((test - 1) / mem / 100) << "%" << endl;
}

clock_t end_time = clock();
double elapsed = double(end_time - start_time) / CLOCKS_PER_SEC;

cout
<< endl << "Ausgabe..." << endl << endl
<< "Primzahlen bis: " << ((test - 1) / mem) * mem << endl
<< "Groesste Primzahl: " << prim[prim.size() - 1] << endl
<< unsigned(prim.size()) << " Primzahlen: " << elapsed << "s" << endl;

// copy(prim.begin(), prim.end(), ostream_iterator<Number>(ofstream("prim.txt"), "\n"));
}

dauert bei mir genau ne sekunde. wie der algo genau funktioniert hab ich vergessen und das nachvollziehen wird wegen dem grauenhaften code auch nicht unbedingt erleichtert... ;)
- es kann vielleicht helfen, die mem konstante anzupassen, da spielt wohl auch der cache der cpu ne rolle.
- lässt man den kommentar der letzten codezeile weg, werden die primzahlen auf die platte geschrieben (55mb bei 100.000.000 zahlen in 12 sekunden)
das sieb mag zwar scheiße sein, aber bei solchen anwendungen (begrenzter zahlenbereich) ist es imo ungeschlagbar. komm, beweise mir das gegenteil!
*fehdehandschuh zück* ;)

edit: habe mir den algo nochmal angesehen:
- der zahlenbereich wird in test / mem blöcke aufgeteilt
- für jeden block wird der sieb-algo ausgeführt und die gefundenen primzahlen im vector prim gespeichert
- der algo benötigt gefundene primzahlen aus allen bisher berechneten blöcken, ein binary_search algorithmus sucht im vector prim nach diesen

das speicherproblem ist gelöst bis auf die speicherung der primzahlen selbst. ein auslagern auf platte wird schwierig, da der binary_search alle gefundenen primzahlen im speicher benötigt. vielleicht weiss einer da weiter...

[Lord Nikon]

Original geschrieben von Stone2001
ich vermute stark das Lord Nikon, die Zeit mitzählt, die er noch braucht, um die Zahlen auszugeben.

Jo , diese Zeit habe ich mitgestoppt.


Mit "Graphische Ausgabe" hab ich gemeint , dass in meinem Primzahlen GUI Programm , bei jeder gefundenen Primzahl diese in einem Memo Feld ausgeben werden.
@all
thx für die Antworten.
EDIT: Ohne Ausgabe
4,597 Sekunden

[micki]

#include <stdio.h>
#include <fcntl.h>
#include <windows.h>
#include <ctype.h>
#include <sys/types.h>
#include <sys/stat.h>


__int64 clockCycles;

__forceinline void CountCycles()
{
__asm {
RDTSC
mov DWORD PTR[ clockCycles + 4 ], edx
mov DWORD PTR[ clockCycles ], eax
}
}

inline int IsPrimeasm(int num)
{
__asm
{
mov Ecx,num
mov Ebx,1
mov num,0
m1:
add Ebx,2
mov Edx,0
mov Eax,Ecx
div Ebx
test edx,edx
jz m2
cmp Ebx,Eax
jb m1
mov num,1
m2:
}
return num;
}



int main()
{
SetPriorityClass( GetCurrentProcess(), HIGH_PRIORITY_CLASS );
SetThreadPriority( GetCurrentThread(), THREAD_PRIORITY_HIGHEST );

unsigned int uiMinCycles = 0xffffffff;
unsigned int uiCyclesDiffSum = 0;
for ( int i = 0; i < 3; ++i ) {

CountCycles();
__int64 CyclesStart = clockCycles;

////////////// FUNCTION CALL HERE ////////

const int Loops = 1000000;
for(int a=3,c=0;a<Loops;a+=2)
c+=IsPrimeasm(a);
//////////////////////////////////////////

CountCycles();

unsigned int uiCyclesDiff = (unsigned int)( clockCycles - CyclesStart );
if ( uiCyclesDiff < uiMinCycles ) { uiMinCycles = uiCyclesDiff; }
}

SetPriorityClass( GetCurrentProcess(), NORMAL_PRIORITY_CLASS );
SetThreadPriority( GetCurrentThread(), THREAD_PRIORITY_NORMAL );

printf("\n\nMinimal CPU cycles : %d " , uiMinCycles);
return 0;
}}




vielleicht bin ich ein wenig Out of competition, aber ich mag bruteforce assembler.
variablen-speicherverbrauch? 4byte würde ich sagen :D (vielleicht ist es sogar auf 0byte wegoptimiert)

ein 1.166GHz P4 sollte alle prims bis 1M in 1sec durchrechnen meiner benches nach.. vielleicht kann ja mal jemand mit nem Athlon benchen.

MfG
micki

ps. da die ausgabe nichts mit dem algorithmus selbst zu tun hat, hab ich das weggelassen... ich wüste auch nicht welchen zweck die ausgabe erfüllen sollte.

[HellHorse]

@DocEW
Du brauchst aber das j nicht. Du brauchst bloss j * i, wobei i fest ist und j bei jedem loop inkrementiert ist.
Daher mein Vorschag:

public class Primzahl2 {
public static void main(String[] args) {
long timeBegin;
long timeEnd;
final boolean[] nonPrims = new boolean[5000000];
timeBegin = System.currentTimeMillis(); //nicht ganz korrekt erst hier zu beginnen, ist aber nötig um die Vergleichbarkeit zu erhalten
final int sqrt = (int) Math.sqrt(nonPrims.length);
int j;

for (int i = 2; i <= sqrt; i++) {
if ( !nonPrims[i] ) {
j = i * 2;
while (j < nonPrims.length) {
nonPrims[j] = true;
j += i;
}
}
}

timeEnd = System.currentTimeMillis();
int amountOfPrims = 0;
for (int i = 0; i < nonPrims.length; i++) {

if ( !nonPrims[i] ) {
amountOfPrims++;
}

}
System.out.println("\n\nEs wurden " + amountOfPrims + " Primzahlen gefunden.");
System.out.println("\n\nEs wurden " + (timeEnd-timeBegin) + " ms benötigt.");
}
}

[Stone2001]

Sagt mal, warum sind eure Rechner so schnell?
Mein Rechner braucht so zwischen 6 und 7 Sekunden um alle Primzahlen bis 1 mio zu finden.

[micki]

wegen der langsammen software die auf ihm läuft.

gruesse
micki

[Stone2001]

hmm, mein Algorithmus ist zur Zeit um ca. Faktor 7 langsamer als zeckensacks! (169 zu 24 Sek)
Vielleicht hilft es was, wenn ich mal alle überflüssigen Tasks kille. (Sowas wie SETI läuft ja ständig im Hintergrund...) Nachher mal testen.

[micki]

seti läuft eigentlich mit einer derart niedrigen priorität, dass das kaum auswirkungen haben sollte.

speichernutzung und der algorithmus selbst sind die beiden entscheidenden faktoren bei der performance (naja, vielleicht macht die programmiersprache und der compiler noch was aus)

gruesse
micki

[DocEW]

Original geschrieben von HellHorse
@DocEW
Du brauchst aber das j nicht. Du brauchst bloss j * i, wobei i fest ist und j bei jedem loop inkrementiert ist.
Daher mein Vorschag: (...)
Jo, haste Recht, jetzt raff ich's. =) Bringt allerdings rein von der Geschwindigkeit nix mehr.

[DocEW]

Original geschrieben von zeckensack
Japp. Die "1" wird nicht mitgezählt.
Das Sieb???
Sorry, aber das glaube ich dir einfach nicht.
Vielleicht doch eher der Monte Carlo?
Jo, öhhm... was soll ich sagen? Dann glaub's halt nicht und huldige weiter deinem Algorithmus... :eyes:
Alternativ könntest du es mal eben selbst bei dir ausprobieren. Meinetwegen auch in C, dadurch wird's höchstens noch schneller! :D
Oder ich schicke dir 'nen Screenshot! :deal:
;)

[DocEW]

Original geschrieben von micki
ein 1.166GHz P4 sollte alle prims bis 1M in 1sec durchrechnen meiner benches nach..
Mach doch mal bitte 10Mio und 50Mio, das ist etwas aussagekräftiger!

[micki]

da kann ich nur mit sekunden dienen, wären 14.515s und 143.125s auf p4 2Ghz

garnet mal so schlecht für brute force finde ich!

gruesse
micki

[Stone2001]

Hier mal mein aktueller Versuch, ich bin für vorschläge jederzeit offen.

#include <cmath>
#include <ctime>
#include <iostream>
#include <vector>

using namespace std;

const unsigned int max_number = 1000000;

int main()
{
vector<unsigned int> primes;
unsigned int akt_max_prime = 2; //Die aktuell größte Primzahl
int anz_prime = 1;
int last_try;

primes.push_back(2);

clock_t start_time = clock();

for (int a = 3; a <= max_number ; a +=2)
{
for (int b = 0; b <= sqrt(akt_max_prime); b++) //anz_prime
{
if (a % primes[b] == 0)
{
last_try = primes[b];
break;
}
}

if (a % last_try != 0)
{
primes.push_back(a);
anz_prime++;
akt_max_prime = a;
}
}

clock_t end_time = clock();
double elapsed = double ((end_time - start_time) / CLOCKS_PER_SEC) * 1000;

/* for (int c = 0; c < anz_prime; c++)
{
cout << endl << "Primzahl " << c << " : " << primes[c];
} */

cout << endl << "Es wurden " << anz_prime << " Primzahlen gefunden";
cout << endl << "Die größte ist : " << akt_max_prime;
cout << endl << "Verstrichene Zeit : " << elapsed << " ms" << endl;

return 0;
}

[DocEW]

Original geschrieben von Stone2001
Hier mal mein aktueller Versuch, ich bin für vorschläge jederzeit offen.
Hm.

for (int b = 0; b <= sqrt(akt_max_prime); b++)

Das verstehe ich nicht so ganz... müßte das nicht heißen

for (int b = 0; b <= sqrt(a); b++)

??? Oder ist das jetzt schon eine Optimierung, die ich nur nicht raffe? =)

Ansonsten könntest du statt der last_try Variablen einfach ein boolean benutzen ("prim") und dir das nochmalige Ausrechnen hier

if (a % last_try != 0)

sparen.

@micki
Hätte gedacht ASM wäre schneller... naja, die Compiler sind halt doch schon ganz gut heute! =)

Ansonsten habe ich meine Version noch ein bißchen verbessert:


for (int i = 2; i <= sqrt; i++) {

if ( !nonPrims[i] ) {
temp = 2*i;
while( temp < nonPrims.length ) {
if( !nonPrims[temp] ) {
nonPrims[temp] = true;
}
temp += i;
}
}
}


Die neue "innerste" if-Abfrage brachte bei mir nochmal eine Verbesserung bei von 4,5 auf 3,3 Sekunden ( Primszahlen bis 50.000.000 ).

[DocEW]

Original geschrieben von zeckensack
Es skaliert nicht. Der Algorithmus wurde unter der Annahme entworfen, daß Speicherzugriffe unendlich schnell sind, und Division (bzw Modulo) unendlich teuer. Beides ist Quatsch, insbesondere auf aktuellen Rechnern.
Hi nochmal,
ich habe mal ein bißchen gebencht und das ganze sieht mir ziemlich linear aus... skaliert dein Algorithmus denn noch besser...?

[micki]

1. fag mal früher an zu benchen, dort wo z.b. der cache fixer ist und mach ein paar schritte weiter wo dann so langsamm die festplatte ins spiel kommt... dann kannste sehen wie der algorithmuss suckt.

2. wir machen ja nur kleine primzahlen hier, wenn du wirklich grosse testest, dann hat dein sieb mehr speicherverbrauch als du im größten server zusammengesteckt findest.



damit will ich dich nicht flamen, nur erklären was zs wohl meint. wobei für soeinen kleinen zahlenbereich ein sieb eine der schnellsten sachen ist, wenn nicht sogar die schnellste, da haste "räscht"

gruss
micki

[KiBa]

so, ich hab meinen algorithmus nochmal verbessert, muss wohl tomaten auf den augen gehabt haben, als ich den geschrieben hab.

hier ne messreihe: (cachegröße 15625)

1Mio : 0,02s
5Mio : 0,09s
10Mio : 0,2s
50Mio : 1,1s
100Mio : 2,5s
500Mio : 17,2s
1Mrd : 43s
2^32-cache : 7,5min

hab ich jetzt gewonnen? ;)
die ersten beiden werte sind wegen geringer timer-auflösung ungenau und der letzte wert (größter, den ich mit unsigned int nehmen kann) verursachte swapping. dies könnte man noch beseitigen, indem man nur sqrt(end) viele primzahlen bei jedem block-durchlauf im speicher behät und den rest auf platte speichert. das würde nun funktionieren, da ich das binary_search wegbekommen habe.

allerdings sieht man auch, dass dieser algo wirklich nicht gut skaliert, reicht aber für 32-bit zahlen aus und ist dabei superschnell... würde mich interessieren, bei welcher zahlengröße sich zecke's und mein algorithmus treffen.

hier noch der code:

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <ctime>
//#include <limits>
using namespace std;

typedef unsigned Number;

const Number cache = 15625;
const Number test = 100000000;//numeric_limits<Number>::max() - cache + 1;

int main()
{
clock_t start_time = clock();

cout << "Speicherbelegung..." << endl << endl;
vector<Number> prim, pm(cache);

cout << "Berechnung..." << endl << endl;
for (Number i = 0; i < (test + cache - 1) / cache; ++i)
{
const Number begin = cache * i + 2, end = cache * i + cache + 1;
for (Number j = 0; j < cache; ++j)
pm[j] = begin + j;

for (Number j = 2, in = 0; j <= sqrt(double(end)); !i ? ++j : j = prim[++in])
for (Number k = !i ? 2 : Number(ceil(double(begin) / j)); k <= end / j; ++k)
pm[j * k - begin] = 0;

for (Number j = 0; j < cache; ++j)
if (pm[j]) prim.push_back(pm[j]);
if (!((i + 1) % 100))
cout << (i + 1) / ((test + cache - 1) / cache / 100) << "%" << endl;
}

clock_t end_time = clock();
double elapsed = double(end_time - start_time) / CLOCKS_PER_SEC;

cout
<< endl << "Ausgabe..." << endl << endl
<< "Primzahlen bis: " << ((test + cache - 1) / cache) * cache << endl
<< "Groesste Primzahl: " << prim[prim.size() - 1] << endl
<< unsigned(prim.size()) << " Primzahlen: " << elapsed << "s" << endl;

// copy(prim.begin(), prim.end(), ostream_iterator<Number>(ofstream("prim.txt"), "\n"));
}


edit: cache muss teiler von test sein, hab die cachgröße von 16000 auf 15625 angepasst.

[micki]

Original geschrieben von KiBa

hab ich jetzt gewonnen? ;)
.
.
.

allerdings sieht man auch, dass dieser algo wirklich nicht gut skaliert


mehr hat man hier nie behauptet... oder?


gruesse
micki

ps. wir sollten hier öfters mal so einen wettbewerb machen, mit weniger competition und mehr codeanalyse und spass.. mir gefällt's :D

[Stone2001]

Original geschrieben von micki
ps. wir sollten hier öfters mal so einen wettbewerb machen, mit weniger competition und mehr codeanalyse und spass.. mir gefällt's :D
yup, es ist schon beeindruckend, ein Programm zu schreiben, das für eine bestimmte Aufgabe ca. 5 Sekunden braucht, nur um dann zu erfahren, das es auch in 0.3 Sek geht... . ;)

[DocEW]

Original geschrieben von KiBa
hab ich jetzt gewonnen? ;)
Ich glaube schon! Zumindest bis jetzt... ;)
Jo, fand ich aber auch echt witzig, den kleinen Wettbewerb. Obwohl ich ehrlich gesagt nicht die Lust habe, wirklich jeden Algo im Detail zu raffen...

Original geschrieben von Stone2001
yup, es ist schon beeindruckend, ein Programm zu schreiben, das für eine bestimmte Aufgabe ca. 5 Sekunden braucht, nur um dann zu erfahren, das es auch in 0.3 Sek geht... . ;)
Das finde ich auch immer wieder krass, was da geht... wir hatten an der Uni neulich so einen kleinen Wettbewerb und da waren echt riesige Unterschiede. Von ca. 10 Sekunden bis "habe ich nach einer halben Stunde abgebrochen"! :)
Und kommerzielle Programme können das gleiche wohl in < 1 Sekunde, wurde uns gesagt... war übrigens der Netzwerk-Simplex Algorithmus, falls das jemandem was sagt.

[KiBa]

hab jetzt noch ein wenig gefeilt am algorithmus. zusätzlich hab ich das ganze mal nach c# portiert unter verwendung des .net-frameworks. hier die ergebnisse:

anzahl...c++......c#
-----------------------
10mio....0,15s....0,35s
100mio...2,1s.....3,5s
1mrd.....39s......44s

eigentlich nix aufregendes. zu beachten ist aber, dass die c#-variante bei großen zahlen gegenüber c++ immer schneller wird. liegt wohl daran, dass das anlegen des speichers beim managed-heap schneller vonstatten geht, als es in c++ möglich wäre. die optimale cachegröße bei c# ist übrigens bei mir um die 50000 gegenüber ca 16000 bei c++.

[micki]

könnte auch daran liegen dass codeabschnitte vor dem ersten durchlauf optimiert bzw compiliert werden beim bytecode von .net (wenn du das mit c# machst)


so, was machen wir als nächtes für nen wettbewerb?
nicht zu komplex, nicht zu einfach und nicht sowat wie sortieren oder palindrome *kotz* :)

was ich lustig fände wäre etwas bekanntes mit bedingungen, sodass wir unsere kenntnisse anwenden können aber noch niemand eine perfekte lösung hat wegen der bedingung.
z.b. rasterisierung eines polygones mit texturen, bedingungen: darf keine division benutzt werden.

hätte jemand hier wat nettes?


n8liche grüsse
micki

[DocEW]

Original geschrieben von micki
z.b. rasterisierung eines polygones mit texturen, bedingungen: darf keine division benutzt werden.
Uii... also irgendwas mit weniger Anforderungen an Spezialkenntnisse wäre mir ganz Recht... ?-)

[micki]

um ein zahlensieb zu coden braucht man auch schon einiges an spezialkenntniss... ich hatte ja kein besseres beispiel und hielt es für absurt genug dass man es nicht nimmt, sollt beispiel bleiben.

wir könnten ja RSA schlüssel knacken :).. wäre ja aber fast das gleiche wir Primzahlen suchen ...

gruesse
micki

[zeckensack]

Krass, einfach nur krass :o
Ich kann mich erinnern, daß das 'normale' Sieb (so wie's in Info-Büchern beschrieben wird), ziemlich stark stinkt. Hätte echt nicht gedacht, daß man da noch so viel optimieren kann.
Vielleicht sollte ich 'meine' Idee auch noch ein bisserl durchoptimieren, und schauen, wohin das führt.
Vielleicht auch nicht ;D


Nur um mal die theoretische Basis zu schaffen, unter "Sieb" verstehe ich die Klasse von Algos, die mit vielen möglichen Primzahlen starten, und dann mittels Multiplikation (oder äquivalenter Abkürzung) Kandidaten killen.
Frage an die "Top-Implementoren":
Werden Einträge mehrfach untersucht (und mehrfach auf "keine Primzahl" gesetzt)?

'Meine' Idee prüft per Modulo, ob der aktuelle Kandidat durch eine kleinere Primzahl teilbar ist, was ggü der naiven Prüfung aller kleineren ganzen Zahlen schonmal mächtig Berechnung einspart.

Eine Optimierung, die auf beide Methoden anwendbar ist, ist die Verwertung der Erkenntnis daß ein möglicher Primfaktor nicht größer sein kann als die Quadratwurzel des untersuchten Kandidaten.

Wenn ein optimiertes Sieb den Zustand erreichen kann, daß pro Multiplikation exakt ein (bisher nicht bestimmter) Kandidat ausgeschlossen werden kann, dann leuchtet mir jetzt auch ein, warum das schneller sein kann. 'Mein' Ansatz braucht pro Kandidat mindestens eine Division, und die Performance sinkt im worst case reziprok mit der Anzahl der bekannten Primzahlen, die <= der Wurzel des aktuellen Kandidaten sind. Wie genau die Skalierungskurve aussieht, kann ich aufgrund der für mich undurchschaubaren Verteilung der Primzahlen nicht sagen. Als ich das Ding entworfen habe, war ich davon ausgegangen, daß das "Sieb" O(n*sqrt(n)) sein müsste, und daß meine Idee das locker schlagen kann (kann sie auch; nur die weitere Optimierbarkeit des Siebs war mir in der Form nicht bekannt).

PS: Das sollte jetzt kein Rausgerede sein, die Niederlage ist hiermit eingestanden :)
Hochinteressant, so Zeugs ... ?-)

[KiBa]

Nur um mal die theoretische Basis zu schaffen, unter "Sieb" verstehe ich die Klasse von Algos, die mit vielen möglichen Primzahlen starten, und dann mittels Multiplikation (oder äquivalenter Abkürzung) Kandidaten killen.
exakt.
Werden Einträge mehrfach untersucht (und mehrfach auf "keine Primzahl" gesetzt)?
nein. (fast)
genauer: ich unterteile die natürlichen zahlen von 2 bis n ja in blöcke. beim ersten block wird von 2 bis sqrt(max nummer in block) jede zahl durchgegangen und alle vielfache davon gestrichen. die 20 würde z.b. durch 10*2 und 5*4 gestrichen werde. die gefundenen primzahlen im ersten block werden dann gespeichert.
für alle weiteren blöcke werden dann nicht mehr alle zahlen von 2 bis sqrt(max nummer in block) genommen, sondern nur noch die gespeicherten primzahlen, mit denen die vielfachen gebildet werden. da eine primzahl keine weiteren teiler hat, wird auch jede nicht-primzahl im aktuellen block nur einmal gestrichen.
das kann auch nie schief gehen, da für jeden weiteren block garantiert bereits eine größere primzahl als sqrt(max nummer in block) ausgerechnet wurde. bei mehreren millionen blöcken fällt der erste dann nicht mehr ins gewicht...
man kann beim normalen sieb-algorithmus auch verhindern, dass mehrfache streichungen passieren, indem man schon gestrichene zahlen nicht zum streichen deren vielfachen benutzt. dann bleibt nur noch der speicheraufwand für alle zahlen bis n.
Eine Optimierung, die auf beide Methoden anwendbar ist, ist die Verwertung der Erkenntnis daß ein möglicher Primfaktor nicht größer sein kann als die Quadratwurzel des untersuchten Kandidaten.
was ich bei meinem algorithmus ja auch anwende...

was noch anzumerken wäre:
eine möglichst große primzahl finden und alle primzahlen bis n finden sind völlig unterschiedliche aufgaben. für die zweite ist das sieb imo am besten.
mit der optimierung brauchts dann nur noch speicherplatz für den cache (nimmt einen block auf, bei mir 16000 bis 50000 zahlen) und für die gefundenen primzahlen selber (nicht mehr alle zahlen bis n wie beim normalen sieb-algo). auch die geschwindigkeit ist wesentlich besser als beim normalen sieb, da nur noch vielfache von schon gefundenen primzahlen gestrichen werden. diese ausführungsgeschwindigkeit dürfte nicht zu toppen sein...

edit: ein weiterer vorteil meiner optimierten variante ist die möglichkeit der parallelisierung. hier werden die einzelnen blocks einfach von mehreren rechnern bearbeitet. dann brauchts nur noch eine zentrale instanz, welche die primzahlen speichert.
wer leiht mir mal schnell seine dual-workstation; linux-cluster; earth-simulator? hab was wichtiges vor... ;)
ok, zeit ins bett zu gehen! (hach ja, semesterferien)
:biggrin:

[micki]

ich hätte da wat:


We have an array of chars, with N cells (4<=N<=50). In the array will be stored a mathematical expression with unknown X. Your program should solve the expression and find X.
Example:
(4*X+3)*6=186
Your program should find X. In the example above x=7, because (4*7+3)*6=187
You should make a function, that will take two parameters- char array[], int array_size. Your program should return an int which is the value of X._
Function prototype:
int find_x(char a[], int size);
Notice:
__ 1) All numbers in the expression will be ints, but not floats. For example, 3.1 is illegal number.
__ 2) In the expression, you can meet these mathematical signs-> +,-,*,/
__ 3) The priorities of the mathematical operations are (from higher priority to lower): *,/,-,+ (notice that + and - are with equal priorities)
__ 4) X may occur more than once, but no matter how many times it occur, it will always remain on first power. For example (4*X+1)*2-X/6=49. The value of X here, is 6. Because (4*6+1)*2-6/6=49.
__ 5) The input will be correct. This means that there will be just one '=', and X will always be integer!


hab ich ma irgendwoher geklaut aus dem netz (google sei dank)
ich fände das eine interresante sache, wobei ich garnichts mit sowas zu tun habe, aber es wäre sicherlich mal nen expression solver zu coden... vielleicht in assembler.

wäre das zu komplex für nen kleinen contest-codereview?
vielleicht sollten wir am anfang versuchen dass es überhaupt fehlerfrei läuft:)

gruesse
micki

[Xmas]

Original geschrieben von micki
hab ich ma irgendwoher geklaut aus dem netz (google sei dank)
ich fände das eine interresante sache, wobei ich garnichts mit sowas zu tun habe, aber es wäre sicherlich mal nen expression solver zu coden... vielleicht in assembler.

wäre das zu komplex für nen kleinen contest-codereview?
vielleicht sollten wir am anfang versuchen dass es überhaupt fehlerfrei läuft:)

gruesse
micki
Ist zwar ein ganz interessantes Problemchen, aber eigentlich nicht als Contest geeignet. Höchstens least LOC, und da muss die Umgebung festgelegt sein.

Aber wie wäre es denn mit dem Feld der NP-Probleme? ;)

[micki]

naja, das hab ich von einer contestseite, war also wohl geeignet :)

was ist mit "feld der NP-probleme" gemeint?

gruesse
micki

[Xmas]

Original geschrieben von micki
naja, das hab ich von einer contestseite, war also wohl geeignet :)

was ist mit "feld der NP-probleme" gemeint?

gruesse
micki
Nun ja, aber als Contest in welcher Form? Schnellster Algorithmus? Kann ich mir irgendwie nicht vorstellen, das Problem ist so reduziert dass selbst ein schlechter Algorithmus nur Sekundenbruchteile brauchen sollte.


Zu NP (und auch weiter unter NP-vollständig):
http://de.wikipedia.org/wiki/NP

[Stone2001]

Original geschrieben von Xmas
Aber wie wäre es denn mit dem Feld der NP-Probleme? ;)
Was schwebt dir den so für ein Problem vor? Wie wäre es mit Minesweeper? (Minesweeper ist NP-Vollständig)

[DocEW]

Original geschrieben von KiBa
man kann beim normalen sieb-algorithmus auch verhindern, dass mehrfache streichungen passieren, indem man schon gestrichene zahlen nicht zum streichen deren vielfachen benutzt. dann bleibt nur noch der speicheraufwand für alle zahlen bis n.
Ja, das benutze ich bei mir auch und das ist wirklich hocheffizient! Während man ansonsten sqrt(n) Zahlen betrachten muß, von denen man jeweils die Vielfachen streicht, sind es danach nur noch pi( sqrt(n) ), wobei ja wie schon weiter oben geschrieben pi(n) ~ n/(ln(n)-C) mit C= 1,08366... die Anzahl der vorkommenden Primzahlen bis n ist. Bei n=50000000 wird die Schleife bei mir z.B. nur 908 Mal statt 7070 Mal durchlaufen.


Original geschrieben von KiBa
ok, zeit ins bett zu gehen! (hach ja, semesterferien)
:biggrin:
Dito, hehe... aber *so* spät war's bei mir diese Ferien noch nicht! =)

[micki]

http://www.cpp-home.com/contests/6/contest6.php






es gibt so ein spielchen bei dem es ein spielfeld gibt, dass so ausschaut wie ein kreuz, darauf sind felder, auf jedem feld befindet sich ein steinchen außer dem feld in der mitte, nun kann man, indem man mit einem steinchen ein anderes überspringt, das übersprungene wegnehmen, wobe man immer nur eines überspringen darf (ein feld) und auch nur felder wo ein steinchen ist, also keine lehren. es endet damit, dass nur ein steinchen vorhanden ist.

wir können das natürlich darauf hin trimmen, dass unsere algos felder belibiger art nehmen und die lösung dazu errechnen..

das ist ein ziemlich komplexes problem, weil viele kleine züge am ende "ein ganzes" ergeben müssen.




naja, ich weiß nicht ob das nicht schon zu überdimensioniert wäre...

alternativ hätte ich vorzuschlagen, dass wir einen huffman bauen, der addaptiv für streamingdaten läuft. meine erste version läuft mit ca 6kb/s bei mir, wobei ich einen konventionellen huffman habe der für einen bestimmten datenbereich (z.B.4kb) erstellt wird und der datenbereich jeweils um ein byte weiterbewegt wird... also ein sehr fummeliges zeug.


es wäre vielleicht auch cool ströhmungen zu simulieren (z.b. mit einem formel 1 wagen als testobjeckt), das wäre heutzutage mit 1GB ram oder so wohl nicht mehr unmöglich

oder änlich: ausbreitung von wärme simulieren, z.b. für kühler für cpus

natürlich könnte man auch noch beides zusammen simulieren.. wobei ich das dann für zu rechenintensiv ansehen würde :)


knacken eines rc5 schlüssels?

oder wir machen pack-algos, also nicht performance, sondern größencontest.

ein OCR wäre sicherlich auch cool


das problem des handelsreisenden, wäre das nicht ca der selbe schwierigkeitsgrad?
(wobei die lösungen viel komplexer wären)


ich weiß net mehr

micki

[Magnum]

Wie wärs mit Grötschels TSP Problem der 442 Bohrlöcher?
Die Koordinaten der Bohrlöcher gibts hier: http://homepages.uni-regensburg.de/~scj04369/tsplib/tsps/tsp442.dat

[Stone2001]

Original geschrieben von Magnum
Wie wärs mit Grötschels TSP Problem der 442 Bohrlöcher?
Die Koordinaten der Bohrlöcher gibts hier: http://homepages.uni-regensburg.de/~scj04369/tsplib/tsps/tsp442.dat
Ich glaube, bei einem NP-Vollständigen Problem dieser Größenordnung, dürfte wohl nur eine Näherungslösung in Frage kommen, oder? ;)

[Frank]

Original geschrieben von DocEW
Hab da noch 'nen Monte-Carlo Algorithmus in meinem Info-Buch, den könnte ich mal ausprobieren... liefert dann aber leider nur so eine Aussage wie: "Das hier sind mit 99,92% Wahrscheinlichkeit alles Primzahlen." :D
Könnte aber auch ziemlich schnell sein. Ist auch schnell. Ausserdem sind die Montecarlo Algorithmen die ich für Primzahltests kenne, auch zu einer 100% Aussage "zu mißbrauchen" - nicht nur 99,92 oder sowas.
Zudem muss man ja bei der Praxis bleiben - und da ist eher die Frage, ob eine Zahl eine Primzahl ist oder welche Primzahl(en) es in einem festen Intervall gibt. (zb [10^300,10^300+20000]) - nicht spucke alle von 0 bis x aus.
Original geschrieben von Stone2001
Was schwebt dir den so für ein Problem vor? Wie wäre es mit Minesweeper? (Minesweeper ist NP-Vollständig)Das wär wohl ganz ok. Zumal da 1Mio$ frohlocken, wenn das ein polynomialer Algo ist.

Original geschrieben von micki
wir könnten ja RSA schlüssel knacken .. wäre ja aber fast das gleiche wir Primzahlen suchen ...
ungeeignet. Da gibts schon Algorithmen wie das quadratische Sieb, die man letztendlich nur noch implementieren brauch.

[Stone2001]

Original geschrieben von Frank
Ist auch schnell. Ausserdem sind die Montecarlo Algorithmen die ich für Primzahltests kenne, auch zu einer 100% Aussage "zu mißbrauchen" - nicht nur 99,92 oder sowas.

Yup, es gibt Monte-Carlo-Algorithmen, deren Fehlerwahrscheinlichkeit viel kleiner ist, als die Rechnengenauigkeit heutiger Rechner. ;)
Gab es nicht vor kurzem einen Wirbel um ein (Mersenne'sche) Primzahl, die dann doch keine war?
Original geschrieben von Frank
Das wär wohl ganz ok. Zumal da 1Mio$ frohlocken, wenn das ein polynomialer Algo ist.

Zusätzlich gibt es dann nochmal 1 Mio$ vom Clay Institut für Mathematik (University of Birmingham in London), einen SLK von meinem Info 2 Dozent, Ruhm und Ehre, einen Ehrendoktor-Titel,... :D

[Frank]

Original geschrieben von Stone2001
Yup, es gibt Monte-Carlo-Algorithmen, deren Fehlerwahrscheinlichkeit viel kleiner ist, als die Rechnengenauigkeit heutiger Rechner. ;)nein nein ... die treffen nach gewisser Laufzeit wirklich eine 100% Aussage. Kann man (natürlich) beweisen. "natürlich" bedeutet 1Mio$ zu ernten
Original geschrieben von Stone2001
Minesweeper...
Ich denke der SLK ist Anreiz genug (nicht die 1Mio $), sich da zu versuchen. :D

[Stone2001]

Original geschrieben von Frank
nein nein ... die treffen nach gewisser Laufzeit wirklich eine 100% Aussage. Kann man (natürlich) beweisen.

hmm, dann haben die aber sicherlich eine Laufzeit, die größer ist als die Laufzeiten von deterministischen Algorithmen, oder?

Bisher hatte ich immer gedacht, das Monte-Carlo-Algorithmen das richtige Ergebnis nur mit einer gewissen Wahrscheinlichkeit zurückliefern und man diese Wahrscheinlichkeit beliebig nahe an 100% bekommen kann. Es aber trotzdem eine geringe Wahrscheilichkeit vorhanden ist, das das Ergebnis falsch ist.

[Frank]

Original geschrieben von Stone2001
hmm, dann haben die aber sicherlich eine Laufzeit, die größer ist als die Laufzeiten von deterministischen Algorithmen, oder?

Bisher hatte ich immer gedacht, das Monte-Carlo-Algorithmen das richtige Ergebnis nur mit einer gewissen Wahrscheinlichkeit zurückliefern und man diese Wahrscheinlichkeit beliebig nahe an 100% bekommen kann. Es aber trotzdem eine geringe Wahrscheilichkeit vorhanden ist, das das Ergebnis falsch ist. ist bei dem letztendlich auch so - nur wenn du dann die Testanzahl exorbitant erhöhst, hast du wirklich irgendwann die 100%. Vermutlich halt eine Ausnahme bei den MC Algos. Meines Wissens wird der MillerRabin Test (den meine ich) aber auch in der Praxis verwendet um eine Primzahl zu finden. Allerdings wird da wirklich nur auf die sogenannte "starke Pseudoprimzahl" (zur Basis blabla) getestet - nur wenns 100% sicher sein muss und die Zahl nicht schon vorher rausgefallen ist: testen bis... blabla

[Stone2001]

hmm, der Miller Rabin Test hat doch bei einem Durchlauf eine Fehlerwahrscheinlichkeit von 1/4, oder? Naja, wenn ich den 25 mal ausführen lasse, dann bin ich doch schon recht nahe an den 100%!
Was verstehst du unter "starken Pseudoprimzahl"? Hat das irgendwas mit Carmicheal-Zahlen zu tun? (Bitte verzeih, ich bin kein Zahlentheoretiker, ich kenne den Miller-Rabin-Test auch nur vom Schöning her und es ist lange her das ich den gelesen habe)

[Godlike]

Wenns net zviel umstände macht, könnt bitte wer einen schnellen Code in C# posten?

Thx!

[Frank]

Original geschrieben von Stone2001
hmm, der Miller Rabin Test hat doch bei einem Durchlauf eine Fehlerwahrscheinlichkeit von 1/4, oder? Naja, wenn ich den 25 mal ausführen lasse, dann bin ich doch schon recht nahe an den 100%!
Was verstehst du unter "starken Pseudoprimzahl"? Hat das irgendwas mit Carmicheal-Zahlen zu tun? (Bitte verzeih, ich bin kein Zahlentheoretiker, ich kenne den Miller-Rabin-Test auch nur vom Schöning her und es ist lange her das ich den gelesen habe) Den MillerRabin Test mach ich zu einer Basis a. Wenn Zahl x den besteht, ist es eine starke Pseudoprimzahl. Teste ich eine Zahl x mit dem Fermat Test und die besteht diesen, dann ist es eine Pseudoprimzahl. Durch den Fermattest fallen aber gerade alle Carmichealzahlen durch.

Mach ich den MillerRabin für alle Basen kleinergleich 2*(ln x)^2 dann hat der 100% Ja-Aussagekraft. Dürfte man aber schon ablesen, dass das Sehr rechenintensiv ist. Die Laufzeit von einen deterministischen hab ich da jetzt grad nicht zur Hand im Vergleich (aber wohl einfacher - klar).

Achso ja doch - für die Aussage muss man noch die verallg. Riemannsche Vermutung beweisen. Wieder 1Mio $ verdient.

[Stone2001]

Original geschrieben von Frank
Den MillerRabin Test mach ich zu einer Basis a. Wenn Zahl x den besteht, ist es eine starke Pseudoprimzahl. Teste ich eine Zahl x mit dem Fermat Test und die besteht diesen, dann ist es eine Pseudoprimzahl. Durch den Fermattest fallen aber gerade alle Carmichealzahlen durch.

Mach ich den MillerRabin für alle Basen kleinergleich 2*(ln x)^2 dann hat der 100% Ja-Aussagekraft. Dürfte man aber schon ablesen, dass das Sehr rechenintensiv ist. Die Laufzeit von einen deterministischen hab ich da jetzt grad nicht zur Hand im Vergleich (aber wohl einfacher - klar).

Achso ja doch - für die Aussage muss man noch die verallg. Riemannsche Vermutung beweisen. Wieder 1Mio $ verdient.
Aha, thx! :up:
(OT: Kannst du mir sagen, welche Mathevorlesungen ich besuchen muß, um mehr über sowas zu erfahren! Oder reicht es, wenn ich mich in Kryptographie vertiefe?)

[Frank]

Bei uns gibts vom Institut Algebra eine superhochkompetente Frau (stets Kinnladeneffekt in der Vorlesung), die direkt zwei Vorlesungen: "Kryptologie" und "Kryptologie auf elliptischen Kurven" zum Thema ließt. Ua. sollte man Zahlentheorie nicht ganz unbewandert sein. Kann man mit der Kryptovorlesung von Informatik 0,00 vergleichen - die machen ja eher allg Kram und/oder nur auf Rechner/Anwendungsfall bezogen. Bei "uns" - Mathematik - könnte man öfters denken, gar nicht in einer Kryptovorlesung zu sitzen. Irgendwelche andere AlgebraVorlesungen beschäftigen sich nicht mit dem Thema. (ausser halt 2..3 Grundlagen)

[Lokadamus]

mmm...

Das mit den Primzahlen erinnert mich an einen kleinen Wettbewerb Ende 99 oder Mitte 2000, den einige im Chat veranstaltet hatten. Ziel war es dabei, alle Primzahlen bis zu der Zahl 1 Milliarde zu finden und das in schnellster Zeit. Der Rechner, auf dem die Zeit gemessen wurde, war ein kleiner P 266 oder sowas. Die ganzen Sourcecodes aller Leute, die daran teilgenommen haben, liegen im Forum The Next Generation oder so ähnlich, nur leider finde ich das Forum nicht mehr. Naja, zum Schluss gabs 2 Leute, die sich den griechischen Mathematikern zugewendet haben und dabei jeweils unter 1 Sekunde geblieben sind ...

[micki]

mein vorschlag für nen neuen "wer findet den schnellsten ... algorithmus" thread wäre den schnellsten algo für die permutation aller möglichkeiten einer wertefolge

z.b. int A[]={0,1,2,3,4,5,6,7};
0,1,2,3,4,5,7,6
0,1,2,3,4,6,5,7
0,1,2,3,4,6,7,5
.
.
.


nützlich z.b. um beim problem des handelsreisenden nur die städteverbindungen zu testen die wirklich Sinn machen und nicht irgendwelche in denen städte doppel und manche garnicht vorkommen.

oder weiß das schon jemand etwas perfecktes?

gruesse
micki

[Lokadamus]

mmm...

Wenn ich dich richtig verstanden habe, willst du einfach nen dicken Array haben, der alle Vielfachen von 2, 3, 5 usw, (eben alle Primzahlen) auskommentiert und dann nur noch zu den Zahlen springt, die bisher keine Vielfachen von irgendwas sind ... ja, hatte einer auch als Idee, war zu langsam ;D ... das Next Generation Board gibt es wohl nicht mehr, also auch keine Chance, an den alten Sourcecode zu kommen :( ... oder willst du ganz was anders machen ? dabei versteh ich aber nicht, wie du auf die Primzahlen selber kommen willst ...

[micki]

vielfache? emm , nö
nur vertauschen von werten im array, so dass alle kombinationen rauskommen die man damit erreichen könnte.

Mfg
micki

[Xmas]

Original geschrieben von micki
mein vorschlag für nen neuen "wer findet den schnellsten ... algorithmus" thread wäre den schnellsten algo für die permutation aller möglichkeiten einer wertefolge

z.b. int A[]={0,1,2,3,4,5,6,7};
0,1,2,3,4,5,7,6
0,1,2,3,4,6,5,7
0,1,2,3,4,6,7,5
.
.
.


nützlich z.b. um beim problem des handelsreisenden nur die städteverbindungen zu testen die wirklich Sinn machen und nicht irgendwelche in denen städte doppel und manche garnicht vorkommen.

oder weiß das schon jemand etwas perfecktes?

gruesse
micki
Ich nehme mal an die Reihenfolge soll egal sein. Dann hab ich nämlich nen recht genialen Algorithmus ;)

[micki]

Original geschrieben von Xmas
Ich nehme mal an die Reihenfolge soll egal sein. Dann hab ich nämlich nen recht genialen Algorithmus ;)

den würd ich gerne sehen :)

MfG
micki

[Xmas]

Habs mal kurz in Python versucht zu realisieren, ist dank integriertem Listentyp so schön einfach. Diese Variante ist zwar nicht schnell, aber elegant. Da lässt sich noch viel rausholen.

Die Basis des Algorithmus ist die Tatsache, dass man die Permutationen folgendermaßen erzeugen kann:

ABCD
+ BCDA
+ CDAB
+ DABC
++ BCAD
+ CADB
+ ADBC
+ DBCA
++ CABD
+ ABDC
+ BDCA
+ DCAB
+++ BACD
...und wieder rückwärts

Hier im Beispiel mit n = 4 hat man also Vierergruppen bei denen man immer ein Zeichen von vorne hintendranhängt, Dreiergruppen dieser Vierergruppen, zwischen denen zwei Zeichen von vorne nach hinten verschoben werden, und eine Zweiergruppe dieser Dreiergruppen, zwischen denen drei Zeichen von vorne nach hinten verschoben werden (jeweils in umgekehrter Reihenfolge)
Insgesamt also 1*2*3*4 = 24 Permutationen.

Es ist auch einfach möglich, die Permutationen "in Reihenfolge" zu erzeugen, aber ich habe mal diesen Ansatz gewählt, weil man so die Permutationen ineinander Schachteln kann und kein speicherfressendes Array nutzen muss (kann man aber).



def findPerm(liste):
erg = []
findPerm_rec(liste, erg, len(liste), len(liste))
return erg


def findPerm_rec(liste, ergebnis, n, l):
if l == 1:
ergebnis.append(liste[-n:])
else:
findPerm_rec(liste, ergebnis, n, l - 1)
for i in xrange(n - l + 1):
rev = liste[-n:-n+l-1]
rev.reverse()
liste += rev
findPerm_rec(liste, ergebnis, n, l - 1)

[LudiKalell]

schööönes Thema

kurze Vorstory: hier an der Uni Jena mussten wir für paralleles Rechnen (Cluster) nen parallelen Algo schreiben, der in 5 Minuten folgendes tut:
- der Reihe nach alle Primzahlen finden (NUR 2 und 3 sind vorgegeben !!) und als lesbare Zahlen mit Zeilenumbruch nacheinander in eine Textdatei aufm Server speichern

wir kamen wegen der lahmen Platte nur auf 8 GByte = alle Primzahlen bis ~17 Miarden, damit wären wir erster geworden.. das lustige.. Parallelisierung war kaum nötig, denn der Server konnte nicht schnell genug auf Platte schreiben.. 2 Rechner arbeiteten, der Rest war idle..

tja ich hab mich laaaange hingesetzt, auch fremde Implementierungen getestet..

am Ende wurden wir disqualifiziert, weil wir nen fremden Code genommen haben den wir nich kommentieren konnten.. aber er war sau schnell

zurück zum Thema:

nachdem wir uns nun ein halbes Jahr mit dem Thema sporadisch auseinandergesetzt haben, etwas Theorie:
(ich habe leider nicht alle Postings gelsen, wenn ich was wiederhole möge man mir verzeihen..)

Der triviale Algo läuft in O(n^2), ist als extrem suboptimal.. wenn man diesen ansetzt, käme man auf gerade mal 100 MB in 5 Minuten.. (das hat auch unser Kursleiter so erwartet.. am Ende dann 8 GB.. man man man..)

der hier bestimmt schon genannte Algo ist das sogenannte Sieb des Erathostenes (von Kyrene), ein Grieche, der's einfach mal faustdick hinter den Ohren hat(te)

dieser Algo läuft in O(n*logn),(im Endeffekt hat man ein Bitsieb, jedes Bit steht für ne ungerade Zahl(wenn man clever ist sogar für eine Zahl die nicht durch 2 UND 3 teilbar ist -> Stempelverfahren) wenn man ne Primzahl findet streicht man deren Vielfache raus indem man die entsprechenden Bits auf 1 setzt) ist also schon verdammt nah dran am Optimum, zumindest theoretisch..
wie auch immer.. wenn man diesen Algo nun implementiert und gut optimiert (Bitsiebe, in C, aber ohne Assember) kommt man schon auf nette ~30 Sekunden bis 2^32 (4,1.. Mia.) auf einem Athlon XP mit 2,2 Ghz (tadaa) (wohgemerkt: mit dem MS Visual 6 Compiler.. der ist rel. langsam)

das ist absolute Spitzenzeit, es geht mit gehörigem Aufwand noch schneller (siehe hier: http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html , das ist der Algo den wir genommen haben und dessen Leistung ich zu 90 % erreicht habe)
die eben genannte Adresse ist auch gut um ne Tabelle zu haben, wenn man die Anzahl der gefundenen Primzahlen abgleichen muss (100 mal gemacht.. und wenn nur eine feht.. und das wird's bei den ersten 30 mal.. naja)

AAABER nun kommen wir zum absoluten Highlight, und der Creme de la Creme:
primegen

dies ist ein Programm, das wohl die Perfektion fast erreicht hat.. ein Mensch namens Atkins hat mit einem Herrn Bernstein vor ein par Jahren einen neuen Algo entwickelt, der da heisst: Sieb von Atkin
http://cr.yp.to/primegen.html

das ist DEFINITIV das beste was ihr finden werdet, sein Algo stellt das Mass der Dinge dar

dabei liegt "mal eben so" eine Super Implementierung des Erathostenes Siebs dabei(als traditioneller ALgo bezeichnet, allerdings sind die ersten paar hundert Primzahlen vorgegeben, aber das könnte man leicht mit nem eigenen Algo ersetzen..), welches nochmal fast doppelt so schnell ist wie mein Algo

wie auch immer: die Zahlen sprechen für sich.. wenn man Linux sein eigen nennt, gcc verwendet und in der Datei conf-words die Grösse des Siebs für den L1 Cache der eigenen CPU anpasst.. dann pfeift die Oma..

wichtig: Primegen funzt auch für Zahlen > 32 Bit, was eine Hürde darstellt(mein Algo ja auch, bei dem von Herrn Flammenkamp bin ich mir nicht so sicher..)

[LudiKalell]

*räusper* ich muss mich entschuldigen.. bis 10 Mia. in ~35 Sek.

[Stone2001]

Ich liebe die Wirren des O-Kalküls! ;)
Bezogen auf die Eingabelänge, hat der Sieb des Erathostenes eine expontielle Laufzeit. Erst 2002 kommte man wirklich nachweisen, das das Problem ob eine Zahl jetzt Prim ist oder nicht, in P liegt (also polynomiale Laufzeit hat). Soweit ich weiß, hat der Algorithmus eine Laufzeit von O(log^12(n)).

[Magnum]

Original geschrieben von Stone2001
Ich liebe die Wirren des O-Kalküls! ;)
Bezogen auf die Eingabelänge, hat der Sieb des Erathostenes eine expontielle Laufzeit. Erst 2002 kommte man wirklich nachweisen, das das Problem ob eine Zahl jetzt Prim ist oder nicht, in P liegt (also polynomiale Laufzeit hat). Soweit ich weiß, hat der Algorithmus eine Laufzeit von O(log^12(n)).
Was meinst du mit O(log^12(n))? (sprich: O von log hoch zwölf von n ??)

Aber mit meinen bescheidenen Kenntnissen, dürfte so ein Algoritmus nicht länger brauchen als O(n^2).
Zum Testen, ob n prim ist, muss man ja nur n durch jede Zahl <n teilen und schauen, ob ein Rest raus kommt! Das wären also insgesamt O(n) Divisionen. Wenn man jetzt noch berücksichtigt, das Divisionen großer Zahlen nicht unerheblich sind, sind wir bei O(n^2). (Division geht in O(n), vgl "Divisionsalgorithmus aus der Grundschule")

[PH4Real]

Original geschrieben von Stone2001
Ich liebe die Wirren des O-Kalküls! ;)
Bezogen auf die Eingabelänge, hat der Sieb des Erathostenes eine expontielle Laufzeit. Erst 2002 kommte man wirklich nachweisen, das das Problem ob eine Zahl jetzt Prim ist oder nicht, in P liegt (also polynomiale Laufzeit hat). Soweit ich weiß, hat der Algorithmus eine Laufzeit von O(log^12(n)).

Müsste das nicht O((log n)^12) heissen :kratz2: ?

Das mit Primes in P (http://www.cse.iitk.ac.in/primality.pdf) ist aber wirklich interessant...

PS: Schöner rekursiver Algorithmus Xmas. Erinnert mich irgendwie an Scheme :D

[Stone2001]

Original geschrieben von PH4Real
Müsste das nicht O((log n)^12) heissen :kratz2: ?

Also in dem Paper steht:
Theorem 5.1 The asymptotic time complexity of the algorithm is O(log^12 n).
Die mathematische Interpretation überlasse ich jedem selber! :D

[Magnum]

Also in dem Paper steht bei mir auch Seite 2, Zeilen 3,4:
... We give a deterministic, O((log n)^12) time algorithm for testing if an number is prime. ...
Ich denke, das ist jetzt deutlich!

[LudiKalell]

joah, Primes in P war schon mal ne ganz nette Sache, speziell wenn man immer wieder liest "ist in NP.. (ach ?!)vielleicht auch in P" .. wird's irgendwann frustrierend..

aber zum Glück heisst das ja nich dass alle Algos die Primzahlzerlegung für Kryptographie nutzen (also fast alle Kryptoalgos) jetzt Gefahr laufen geknackt zu werden...

[Senior Sanchez]

Ich hab nen neuen Coding-Vorschlag:


Bestimmung der Zahl pi. Natürlich muss noch die Genauigkeit, also korrekte Nachkommastellen und so weiter festgelegt werden, aber im grunde ist es doch schön, da ich denke jeder was hier damit anfangen kann und auch es ne Vielzahl von Algorithmen schon von vornerein zur Auswahl gibt.



mfg Senior Sanchez

[LudiKalell]

hm is mir jetzt nich intuitiv klar wie man da anfangen könnte..

klar, 2*radius*PI is der Umfang eines Kreises, und daher stammt's ja auch, aber wie bitte schön kann man NUR dieses Wissen nutzen um eine Art Aproximation zu proggen ? Ich kann ja schlecht mit nem Zirkel nen Kreis malen und PI per Hand annähernd (PI mal Daumen -> haha) berechnen ?!

gibt es irgendeine Formel zur Berechnung von PI ?

[Senior Sanchez]

na gut, stimmt, da gibts nich soviele varianten (z.b. monte-carlo)

bei der eulerschen Zahl gibts aber mehr, das wäre vllt auch mal nen versuch wert, obwohl das vllt zu einfach ist.


mfg Senior Sanchez

[LudiKalell]

mal dringend:
kennt einer ne nette Sache die man nicht-trivial parallelisieren kann ? geht um die Programmieraufgabe für Cluster Computing, der Mensch sucht noch nach ner Aufgabe die seeeehr CPU astig ist aber eben nicht Festplatten lastig

am besten wäre etwas das man eben besser parallelisieren kann als nur einen Suchabschnitt in Teile zu unterteilen(Bsp.: Primzahlen bis Zahl x finden.. ist zu billig zu parallelisieren, einfach nen Suchblock an die Clients schicken.. eine andere Aufgabe ist erwünscht)

das Problem sollte mathematisch sein, die Sache mit der Eulerschen Zahl ist schonmal ne nette Sache.. (fällt mir nich sofort ein wie man das parallelisieren kann ->gut)

[Trap]

n-Körper Problem der Astronomie? n Körper so mit Anfangsposition und Anfangsgeschwindigkeit anordnen, dass sie stabile Umlaufbahnen haben.
Ne am Anfang feststehende Sonne in der Mitte und die Massen der Körper vorgeben und Regeln was als stabil gilt.

Eulersche Zahl ist einfach. Die hat eine Definition als unendliche Reihe, einfach wieder in gleichgroße Abschnitte unterteilen und an die Rechner verteilen.

[Stone2001]

Original geschrieben von Trap
Eulersche Zahl ist einfach. Die hat eine Definition als unendliche Reihe, einfach wieder in gleichgroße Abschnitte unterteilen und an die Rechner verteilen.
hmm, um die Eulersche Zahl zu berechnen, braucht man keinen Cluster. Ein normaler Rechner mit einer extrem hohen Genauigkeit reicht vollkommen aus. (1 + 1/n)^n hat für n gegen unendlich den Grenzwert die Eulersche Zahl e.

Und wie wäre es mit einem Problem aus der Bildverarbeitung? (Naja, sind wahrscheinlich zu leicht parallisierbar, oder?)

[Gast]

faktorisieren; n > 2^128

[Magnum]

Original geschrieben von Gast
faktorisieren; n > 2^128
Einfach! Verteile einfach Zahlenbereiche, die jeder einzelne Rechner dann durchprobieren darf!

[Gast]

Original geschrieben von Magnum
Einfach! Verteile einfach Zahlenbereiche, die jeder einzelne Rechner dann durchprobieren darf! lol, du musst ca sqrt(2^128)/2 = 2^63 ~= 1,8*10^19 Zahlen ausprobieren. Wenn du 1000 Rechner hast, die 10000 Zahlen/s schaffen, brauchst du ca. 1,8*10^12 Sekunden oder ~58494 Jahre.

[Magnum]

Original geschrieben von Gast
lol, du musst ca sqrt(2^128)/2 = 2^63 ~= 1,8*10^19 Zahlen ausprobieren. Wenn du 1000 Rechner hast, die 10000 Zahlen/s schaffen, brauchst du ca. 1,8*10^12 Sekunden oder ~58494 Jahre.
Kennst du nen Algorithmus, ders schneller kann?

[Gast]

http://www.crypto-world.com/FactorPapers.html

[Gast]

Mein Programm kann 2^128+1 in 9,12s auf einem PIII450.

[Magnum]

Nette Seite, aber jetzt ist die Aufgabe witzlos! Denn hier (ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Richard.Brent/rpb193.ps.gz) gibts nen parallel Algorithmus dazu!
Und hey, ich habe nie behauptet, dass mein Algo schnell ist! Er ist nur leicht zu parallelisieren!

[LudiKalell]

es sol ja weniger etwas sein wo die Leuts die die geniale "Idee" haben 3 Trilliarden mal mehr rausbekommen als die welche es "standardmässig" bearbeiten

es sollte halt etwas sein was JEDER ohne grosses Vorwissen versteht, was jedoch trotzdem knifflig zu parallelisieren ist.. oder sagen wir mal was BESSER läuft wenn die Parallelisierung NICHT trivial ist

Primzahlfaktorisierung vielleicht ??? muha, sorry ;) musste sein.. na ja vielleicht kommt der Vorschlag durch...

[[3rd-B][Thomas]]

class so{

public static void main (String [] args ) {
System.out.println("bis wo?" );
int a,b,c,d,e,f,g,h,z,i,anz;
long start, stop;
anz = Tastatur.readint();
//anz=1000;
boolean prim[][] = new boolean [8][anz/10];
//int ausw[] = new int [anz];
a=3;
b=4;
c=3;
d=13;
e=12;
f=13;
g=28;
h=32;
start=System.currentTimeMillis();
for(i=0;i<8;i++){
if(i==0){
a=3;
b=4;
c=3;
d=13;
e=12;
f=13;
g=28;
h=32;

//1

}
if(i==1){
a=7;
b=6;
c=8;
d=6;
e=8;
f=22;
g=22;
h=7;

//7

}
if(i==3){
a=4;
b=8;
c=13;
d=16;
e=4;
f=8;
g=16;
h=13;

//13

}
//---------
if(i==4){
a=2;
b=2;
c=12;
d=17;
e=14;
f=14;
g=12;
h=17;

//17

}
if(i==5){
a=1;
b=10;
c=5;
d=9;
e=19;
f=17;
g=10;
h=19;

//19

}
if(i==6){
a=6;
b=4;
c=4;
d=10;
e=10;
f=23;
g=6;
h=23;

//23

}
if(i==7){
a=3;
b=6;
c=9;
d=3;
e=6;
f=9;
g=29;
h=29;

//29

}
if(i==2){
a=5;
b=11;
c=7;
d=7;
e=18;
f=5;
g=18;
h=11;

//11

}

for(z=0 ; z*30 <= anz ; z+=7){
prim[i][(z+a)]= true;
}
for(z=0 ; z*30 <= anz ; z+=11){
prim[i][(z+b)]= true;
}
for(z=0 ; z*30 <= anz ; z+=13){
prim[i][(z+c)]= true;
}
for(z=0 ; z*30 <= anz ; z+=17){
prim[i][(z+d)]= true;
}
for(z=0 ; z*30 <= anz ; z+=19){
prim[i][(z+e)]= true;
}
for(z=0 ; z*30 <= anz ; z+=23){
prim[i][(z+f)]= true;
}
for(z=0 ; z*30 <= anz ; z+=29){
prim[i][(z+g)]= true;
}
for(z=0 ; z*30 <= anz ; z+=31){
prim[i][(z+h)]= true;
}

}
stop=System.currentTimeMillis();
System.out.println((stop-start) );
/*for(z=0;z*30< anz ; z++){ // <-- zur ausgabe diesen mehrzeiligen Kommentar normal machen!
for(i=0;i<8;i++){
if(i==0){
a=7;
}
if(i==1){
a=11;
}
if(i==2){
a=13;
}
if(i==3){
a=17;
}
if(i==4){
a=19;
}
if(i==5){
a=23;
}
if(i==6){
a=29;
}
if(i==7){
a=31;
}
if( !prim[i][z]){
System.out.println((z*30+a));
}
}
*/
//}
}

}


-----------------------------------------------------------

also der ist sau schnell .. auf meim 1,4er Thunderbird läuft es von 0 bis 61 mio in ~0,5 sec. ... zwar begrenzt nach oben, aber immernoch schneller als alle anderen ;-) ...
evtl noch verbesserungsfähig :-) (ich bin ja nur ein anfanger" aber toll nicht? ...
es ist echt naja n bissle kompliziert, aber ich blick ihn ;-)

MFGT

[[3rd-B][Thomas]]

ach .. anstattanz = Tastatur.readint();
könnt ihr auch einfach anz=50000000; schrieben ;-) ...
, er läüft zwar auch um bis zu max. ende+30 weiter aber das könnte man unterumständen "wegschneiden ;-)
und immer wenn ich hier den code poste, dann verratzts den .. naja also Tabs gehen weg ;-) ...
und wenn ihr wissen wollt, wo ich die "Idee" herhab hier (http://www.primzahlen.de/files/referent/dk/)

MFGT

[KiBa]

Hallo [3rd-B][Thomas]
also bevor ich deinen Sieg anerkenne, solltest du etwas zu meinen Anmerkungen sagen ;)

1. fairerweise solltest du die Speicherallokierung mit messen
2. es fehlen am Anfang ein paar Zahlen und am Ende gehts übers Limit, aber nicht so schlimm
3. der Algorithmus speichert nur ein Feld von bool, nicht aber die Primzahlen selbst wie gefordert
4. ich habe den Algorithmus mal nach C# portiert und Punkt 1 und 3 verbessert. Vorrausgesetzt ich habe nichts falsch gemacht, habe ich die Vermutung, dass irgendwas falsch läuft, den bei einem limit von 50mio wird die theoretische Grenze anz / (Math.Log(anz) - 1.08366) mit mehr als der doppelten Anzahl durchbrochen. Bei dir kommen 7642631 Zahlen raus, korrekt müsste 3001134 sein. (kann das jemand bestätigen?)
Hier der Code:


using System;

class Prim
{
const uint anz = 50000000;

static void Main()
{
int start_time = Environment.TickCount;
uint a = 3, b = 4, c = 3, d = 13, e = 12, f = 13, g = 28, h = 32;
bool[,] prim = new bool[8, anz / 10];
uint max = 3 * (uint)(anz / (Math.Log(anz) - 1.08366));
uint[] p = new uint[max];

for(int i = 0; i < 8; ++i)
{
if(i == 1) { a = 7; b = 6; c = 8; d = 6; e = 8; f = 22; g = 22; h = 7; }
if(i == 3) { a = 4; b = 8; c = 13; d = 16; e = 4; f = 8; g = 16; h = 13; }
if(i == 4) { a = 2; b = 2; c = 12; d = 17; e = 14; f = 14; g = 12; h = 17; }
if(i == 5) { a = 1; b = 10; c = 5; d = 9; e = 19; f = 17; g = 10; h = 19; }
if(i == 6) { a = 6; b = 4; c = 4; d = 10; e = 10; f = 23; g = 6; h = 23; }
if(i == 7) { a = 3; b = 6; c = 9; d = 3; e = 6; f = 9; g = 29; h = 29; }
if(i == 2) { a = 5; b = 11; c = 7; d = 7; e = 18; f = 5; g = 18; h = 11; }

for (uint z = 0; z * 30 <= anz; z += 7) prim[i, z + a] = true;
for (uint z = 0; z * 30 <= anz; z += 11) prim[i, z + b] = true;
for (uint z = 0; z * 30 <= anz; z += 13) prim[i, z + c] = true;
for (uint z = 0; z * 30 <= anz; z += 17) prim[i, z + d] = true;
for (uint z = 0; z * 30 <= anz; z += 19) prim[i, z + e] = true;
for (uint z = 0; z * 30 <= anz; z += 23) prim[i, z + f] = true;
for (uint z = 0; z * 30 <= anz; z += 29) prim[i, z + g] = true;
for (uint z = 0; z * 30 <= anz; z += 31) prim[i, z + h] = true;
}

uint n = 0;
for(uint z = 0; z * 30 < anz; ++z)
{
for(uint i = 0; i < 8; ++i)
{
if (i == 0) a = 7;
if (i == 1) a = 11;
if (i == 2) a = 13;
if (i == 3) a = 17;
if (i == 4) a = 19;
if (i == 5) a = 23;
if (i == 6) a = 29;
if (i == 7) a = 31;
if (!prim[i, z]) p[n++] = z * 30 + a;
}
}

int end_time = Environment.TickCount;
double elapsed = (end_time - start_time) / 1000f;
Console.WriteLine(elapsed);
Console.WriteLine(n);
}
}

[[3rd-B][Thomas]]

ja ... stimmt ;-) .. also sorry :-(
ich hab da noch kleinere Fehler verbessert und unteranderem auch bei der "ausgabe" ein Fehler verbessert ...
er macht jetzt auch nicht mehr Primzahlen und die Zahlen die am Anfang fehlen sind nur die 2,3 und 5 (begründung: bei dem algo werden nur gewisse Spalten überprüft siehe Quelle)
das mit dem zuviele Primzahlen berechnen, bin ich grad dabei zu lösen, denn er macht ne konstante anzahl an Primzahlen weg ... aber nach hintenhin, müssen mehr weggestrichen werden .. evtl. hab ich da in dem Text, was überlesen, was wichtig ist .. mus mal nochmal checken ...
ich hab aber noch n kleinen fehler bei der Berechnung, da hab ich irgendwo den Falschen Wert genommen vermutlich ... mal sehen .. hab mich wahrscheinlich wo verrechnet! ...
wenn man das noch hinbekommen würde, dass er die anderen zahlen auchnoch rausstreicht, dann wird der algo trotzdem sau schnell sein! ...
Das speichern, mit boolean hat aber DocEW auch gemacht ;-) .. also ist es "ganz einfach" nachher die primzahlen zu "berechnen" .. ich hab nen 2D Feld, und weis wo Primzahlen sin, und weis den x Wert,und weis den y Wert ...
bei DocEW ist es eben nur ein x Wert, also 1D ;-)

ich guck mal ob ich den algo "richtigmachen" kann, damit er den rest auch rausstreicht ... evtl. wenn ich es ned ganz recht hinbekomme, dann könnt ihr ja noch probieren ...
denn dass ist ja ein recht guter ansatz von dem Typ (Quelle) ... also ich würde da mal der sache näher auf den Grund gehen ... ;-)

MFGT

[KiBa]

die "berechnung" der primzahlen, also z*30+a dauert halt auch seine zeit, genauso wie das durchlaufen des feldes. das muss imo schon mit in die zeitnahme... der algo ist dann aber immer noch schneller als meiner (so faktor 2), vorausgesetzt, er arbeitet dann auch korrekt.
wenn du ihn noch überarbeiten solltest, poste das ergebniss bitte hier, dann kann man auch beurteilen, wie diese methode skaliert.

[LudiKalell]

manchmal fragt man sich warum man postet..

aalso nochmal langsam:
1. bitte schau dir mal die GANZEN Posts vorher an, dein Post hätte sonst wohl anders ausgesehen...
2. der von dir benutzte Algo ist ziemlich ähnlich der des beim primegen Code benutzten eratspeed.c(von mir mal auf Seite3 glaub ich erwähnt), nur mit dem unterschied dass er saulahm ist.. soll heissen der Algo ist grundlegend der selbe, aber mein Algo der das klassiche Sieb bneutzt ist um Faktor 3 besser
3. sorry, das mein ich aber ernst: der Algo selbst ist gut, nur die Implementierung ist schlecht

also, auch wenn ich mich wiederhole: geh auf http://cr.yp.to/primegen.html ,zieh das .zip, schau dir eratspeed.c an und dann hast du's .. und dann kompilierst du mal primegen.c (editiere vorher Datei conf-words) mit dem Makefile.. und dann staunst du !

[Coda]

Mein Programm kann 2^128+1 in 9,12s auf einem PIII450.
Faktorisieren? Egal welche Zahl von 0-2^128? Dann hättest du damit sämtliche Cryptographieverfahren gebrochen wenn er wirklich stimmt :rolleyes:

[Gast]

Faktorisieren? Egal welche Zahl von 0-2^128? Dann hättest du damit sämtliche Cryptographieverfahren gebrochen wenn er wirklich stimmt :rolleyes:Quatsch, die arbeiten im Bereich > 2^1024. Wenn du es nicht glaubst, gib mir eine (nicht Prim-)Zahl < 2^160 und ich faktorisiere sie dir.

[micki]

Quatsch, die arbeiten im Bereich > 2^1024. Wenn du es nicht glaubst, gib mir eine (nicht Prim-)Zahl < 2^160 und ich faktorisiere sie dir.
nur so aus neugierde:
182 687 704 666 362 864 775 433 705 490 048 951 957 854 356 193

MfG
micki

[Coda]

Nein, tun sie nicht. Sicherer Internetverbindungen haben meistens 128 bit Keys.

[Trap]

Nein, tun sie nicht. Sicherer Internetverbindungen haben meistens 128 bit Keys.
Die basieren aber nicht auf Primzahlen, bei Primzahlverschlüsslung nimmt man immer mindestens 1024 Bit...

[Gast]

182687704666362864775433705490048951957854356193 = 302231454903657293676533*604462909807314587353021

etwa 6 Sekunden gebraucht.

[micki]

stimmt :)

naja, man muss nur beachten ob man symmetrische oder assymetrische verfahren benutzt, assymetrische müssen meißte 4mal so lange schlüssel haben um gleich sicher zu sein.

MfG
micki

[Coda]

Hmm ok, da hab ich wohl was durcheinander gebracht. RSA benützt ja auch sehr lange Schlüssel.

[Pinoccio]

182687704666362864775433705490048951957854356193 = 302231454903657293676533*604462909807314587353021
~10^43 ... ;-)
BTW: SSL hat mitnichten genau einen Schlüssel. http://de.wikipedia.org/wiki/Secure_Sockets_Layer oder halt die entsprechenden Spezifikationen.

mfg Sebastian

[Gast]

~10^43 ... ;-)Was hat das ";-)" zu bedeuten? Es ging um < 2^160, nicht um < 10^160

[Gast]

Die basieren aber nicht auf Primzahlen, bei Primzahlverschlüsslung nimmt man immer mindestens 1024 Bit...
stimmt :)

naja, man muss nur beachten ob man symmetrische oder assymetrische verfahren benutzt, assymetrische müssen meißte 4mal so lange schlüssel haben um gleich sicher zu sein.

MfG
micki

Nein das stimmt so nicht. Die Kryptverfahren basierend auf elliptischen Kurven sind auch asymetrisch und kommen mit vergleichsweise geringer Bitzahl beim Schlüssel daher.

-frank

[BAGZZlash]

Hier (http://www.arndt-bruenner.de/mathe/scripts/primzahlen.htm) auch noch etwas Lesestoff zum Thema Primzahlen/Primfaktorenzerlegung.

[Thunderhit]

Wow, nur 7 Jahre später! Danke für die Info.

[CokeMan]

Hier eine Doku zum Thema Primzahlen und die Geschichte dahinter.

Die Code Knacker

Part 1 http://youtu.be/VxzajTaNyNw
Part 2 http://youtu.be/IRZUc4nVDiA