Wer kann die schnellsten Primzahlen?

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?

Walli

SideWinder schrieb:

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?

Man soll so wie ich das verstanden habe eine beliebige Folge von Zahlen prüfen können. Ich habe mir zunächst ein isPrime geschrieben und die ersten 10-Millionen Zahlen überprüft um herauszufinden wie schnell der ist.

SideWinder

Achso das meinst du mit "die ersten 10Mio hab ich" Gut okay

Statt hier zu quatschen könnt ich auch mal an die Entwicklung gehen. Aber ich habs im Kopf auf morgen verschoben. Wenn ich während der Arbeit nix zu tun hab kann ich mir mein Gehirn darüber zerbrechen

MfG SideWinder

otze

bin immernoch bei 2^32 dran^^ tjaja, den vector zu nutzen war keine gute idee^^

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).

Für soetwas nimmt man ja auch andere Algorithmen. Wenn du sehen willst, wie du da mit deinem Algorithmus aussiehst. Hier mal ne Ausgabe von einem alten Javaprogramm von mir (Pentium M mit 1,86 GHz):

Zwischen 0 und 1000000000 liegen 50847534 Primzahlen.
GesamtZeit : 41632 Millisekunden

...und von nem alten C++-Programm, das genau das gleiche macht:

Zwischen 0 und 1000000000 liegen 50847534 Primzahlen.
GesamtZeit : 38 Sekunden