Wer kann die schnellsten Primzahlen?

volkard

Meep Meep schrieb:

das waer ne feine sache und ne datei, wo die zahlen drinnen sind zum irgendwo runterladen. dann haetten wir was zum vergleichen

korrektheit kannste erstemal einfacher vergleichen.
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A006880

und falls ein fehler dann passiert ist, mußte den noch finden...

ich kann ein programm bereitstellen, das primzahlen auswirft, bis die platte voll ist.

volkard

SideWinder schrieb:

- Haben die Zahlen auch eine gewisse Mindestgröße?

ja. 0.

- Gilt es alle Primzahlen bis zur Maximalgröße vorauszurechnen und die Eregbnisse in einem Baum abzuspeichern?

ja. aber soviel ram haben wir eh nicht. und die einsendung darf gepackt nicht größer als 64k sein. da passen auch nicht alle rein.

- Ist Assembler grundsätzlich erlaubt? Welchen genauen Sinn hat der Wettbewerb in diesem Fall?

java ist ja auch erlaubt.
ich nehme nicht an, daß asm wirklich viel bringt. durch die divisionen müssen alle durch. da ist der prozessor lahm, gal welche sprache. und wenn du einen baum-trick machst, würdest du den baum in asm schreiben? ich erwarte von dir, daß du gerade wegen der hochsprache tricks einbauen kannst, die man in asm nie hinkriegen würde.

otze

alle antworten entnehme ich aus dem,w as bisher gesagt wurde:

- Haben die Zahlen auch eine gewisse Mindestgröße?

nein, aber sie werden sich vorwiegend in einem "niedriegren" bereich aufhalten

- Gilt es alle Primzahlen bis zur Maximalgröße vorauszurechnen und die Eregbnisse in einem Baum abzuspeichern?

alle tricks sind erlaubt

- Ist Assembler grundsätzlich erlaubt? Welchen genauen Sinn hat der Wettbewerb in diesem Fall?

alle sprachen sind erlaubt

SideWinder

ja. 0.

Das heißt wenn ich meinen optimalen Algo gefunden habe fülle ich noch bis 64KB mit if(i == blubb) return blubb; auf?

MfG SideWinder

volkard schrieb:

Die Eingabezahlen werden nicht gleichverteilt sein, sondern kleine Zahlen kommen deutlich häufiger vor. Die Eingabezahlen werden mit x=r()*r()+r() erzeugt, wobei r() gleichverteilte Zahlen zwischen 0 und 2^31-1 zurückliefert.

BTW: Bevor da einer anfängt, eine Sonderbehandlung für Zahlen <2^30 oder so zu programmieren... Vielleicht solltest du ein bischen genauer sagen, was du unter "kleine Zahlen kommen deutlich häufiger vor" verstehst. IMHO kommt es auch bei dieser Art der Generation von Zufallszahlen nahezu nicht vor, dass eine Zahl <2^50 oder so erzeugt wird. ...nur so am Rande. Bei deinen Beispielzahlen könnte man leicht in eine falsche Richtung denken.

volkard

SideWinder schrieb:

Das heißt wenn ich meinen optimalen Algo gefunden habe fülle ich noch bis 64KB mit if(i == blubb) return blubb; auf?

wenn du dich nicht dafür schämst, ja.

FireFlow

Was muss alles in dem Archiv drin sein? 64Kb sind wenig^^ Reicht der Source und nen Comment zu den Compile-Einstellungen? Welcher Compiler wird beim Test genutzt?

Ich mein fertige Binarys testen kanns net sein da kann man bescheissen

otze

volkard schrieb:

- Gilt es alle Primzahlen bis zur Maximalgröße vorauszurechnen und die Eregbnisse in einem Baum abzuspeichern?

ja. aber soviel ram haben wir eh nicht. und die einsendung darf gepackt nicht größer als 64k sein. da passen auch nicht alle rein.

oha, hab das grad erst gesehen...wieviel ram haben wir, und wieviele ram braucht man ca um alle primzahlen bis dahin darzustellen?^^

Walli

FireFlow schrieb:

Ich mein fertige Binarys testen kanns net sein da kann man bescheissen

Wie denn, wenn alle Tricks erlaubt sind?

SideWinder

Walli schrieb:

FireFlow schrieb:

Ich mein fertige Binarys testen kanns net sein da kann man bescheissen

Wie denn, wenn alle Tricks erlaubt sind?

Bei der Eingabe sind ja eben keine erlaubt.

MfG SideWinder

SideWinder

Ich werde den Quellcode einschicken, da kann ich ganz viele peinlich if(i == blubb) einbauen in dem ich bitterböse defines verwende, el harr

MfG SideWinder

FireFlow

Walli schrieb:

FireFlow schrieb:

Ich mein fertige Binarys testen kanns net sein da kann man bescheissen

Wie denn, wenn alle Tricks erlaubt sind?

Da die Reihe der zu testende Zahlen wie es aussieht vorgegeben ist (z.b. gleichen Seed für alle) kann man einfach alles vorrechnen und nur noch die Ausgabe in die Binary machen^^

otze

FireFlow schrieb:

Walli schrieb:

FireFlow schrieb:

Ich mein fertige Binarys testen kanns net sein da kann man bescheissen

Wie denn, wenn alle Tricks erlaubt sind?

Da die Reihe der zu testende Zahlen wie es aussieht vorgegeben ist (z.b. gleichen Seed für alle) kann man einfach alles vorrechnen und nur noch die Ausgabe in die Binary machen^^

ja, aber der seed wird via eingabe übergeben, man eknnt ihn also nicht

//edit vorberechnen ist btw auch keine gute idee, das berechnen aller zahlen im unsigned int bereich sprengt schon das platzlimit.

SideWinder

Eventuell Packalgo? Weiß nicht ob der bei reinen Zahlen viel bringt.

MfG SideWinder

otze

überleg ich auch grad. besten algo für einmalige 4byte werte raussuchen, und dann mal schauen...

SideWinder

Gings hier nicht ursprünglich um die Entwicklung eines Algos?

MfG SideWinder

otze

nicht zum packen^^ nur zum ausrechnen XD

Walli

Gibt es schon Zahlen? Ich schaffe mit meiner (noch) recht einfachen Implementierung von isPrime die ersten 10⁷ Primzahlen in knapp 21s zu ermitteln (1.5GHz Dothan).

SideWinder

Walli schrieb:

Gibt es schon Zahlen? Ich schaffe mit meiner (noch) recht einfachen Implementierung von isPrime die ersten 10⁷ Primzahlen in knapp 21s zu ermitteln (1.5GHz Dothan).

Nochmal für weniger Schnelle: Gehts hier jetzt um die Entwicklung eines Algorithmus der möglichst schenll nachsieht ob eine Zahl eine Primzahl ist, oder darum einen Algorithmus zu finden der möglichst viele Zahlen berechnet?

Du hast isPrime() und ich dachte auch an Aufgabe 1. Aber was heißt du hast "die ersten 10⁷ berechnet?

MfG SideWinder

volkard

Gregor@Home schrieb:

BTW: Bevor da einer anfängt, eine Sonderbehandlung für Zahlen <2^30 oder so zu programmieren...

gute idee. ich denke, das sollte jeder machen.
nee, mal im ernst, irgendwelche sonderbehandlungen müssen eh sein.

if(n<2) return false;

dürfte wohl der anfang aller primzahlenfunktionen sein. wenn SideWinder echt seine if-orgie macht, ist das auch sonderbehandlung. ich sehe darin kein problem.

Vielleicht solltest du ein bischen genauer sagen, was du unter "kleine Zahlen kommen deutlich häufiger vor" verstehst.

IMHO kommt es auch bei dieser Art der Generation von Zufallszahlen nahezu nicht vor, dass eine Zahl <2^50 oder so erzeugt wird. ...nur so am Rande. Bei deinen Beispielzahlen könnte man leicht in eine falsche Richtung denken.

stimmt. diese berechnung war kacke.
kleine sollten viel häufiger vorkommen als bei rand()*rand()+rand().

ähm. was ist denn gut?
ich probier was. momentchen.

#include <iostream>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long i64;

int bigrand(){
    return rand()|(rand()<<8)|(rand()<<16);
}
i64 megarand(){
    return (i64(bigrand())<<31)|bigrand();
}
int main()
{
    for(i64 max=10;max>0;max*=10){
        int c=0;
        for(int i=0;i<1000000;++i){
            i64 x=megarand();
            x>>=rand()%50;
            if(x<max) ++c;
        }
        cout<<"<"<<max<<": "<<double(c)/10000<<'%'<<endl;
    }
	return 0;
}

<10: 0%
<100: 0.0056%
<1000: 0.1167%
<10000: 1.2614%
<100000: 7.3182%
<1000000: 14.3283%
<10000000: 21.2051%
<100000000: 28.0856%
<1000000000: 35.0752%
<10000000000: 41.9018%
<100000000000: 48.7581%
<1000000000000: 55.7992%
<10000000000000: 62.7778%
<100000000000000: 69.5799%
<1000000000000000: 76.6079%
<10000000000000000: 83.5278%
<100000000000000000: 90.332%
<1000000000000000000: 96.9142%

also alle größenbereiche so ungefäht gleich oft.
die ganz kleinen, also unter 10000 benachteiligt, damit man nicht sofort zu tabellen greifen muss.

wäre das ok?