3. Wer kann die schnellsten Primzahlen?

Wer kann die schnellsten Primzahlen?

  • W

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

    0
  • S

    Walli schrieb:

    Gibt es schon Zahlen? Ich schaffe mit meiner (noch) recht einfachen Implementierung von isPrime die ersten 107 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 107 berechnet? 😕

    MfG SideWinder

    0
  • V

    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?

    0
  • W

    SideWinder schrieb:

    Walli schrieb:

    Gibt es schon Zahlen? Ich schaffe mit meiner (noch) recht einfachen Implementierung von isPrime die ersten 107 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.

    0
  • S

    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

    0
  • O

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

    0
  • ?

    Walli schrieb:

    Gibt es schon Zahlen? Ich schaffe mit meiner (noch) recht einfachen Implementierung von isPrime die ersten 107 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

    0
  • ?

    endlich ein beweis das c++ schneller ist

    0
  • ?

    endlich!! schrieb:

    endlich ein beweis das c++ schneller ist

    Ok, ich geb mich geschlagen. 🙂 😃

    0
  • W

    Gregor@Home schrieb:

    Walli schrieb:

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

    Für soetwas nimmt man ja auch andere Algorithmen.

    Es geht mir weniger darum zu ermitteln wieviele Zahlen dazwischen liegen, sondern nur mal darum meine Funktion mit vielen Zahlen zu testen. Weil noch kein Generator da ist habe ich halt mal aufeinanderfolgende Zahlen genommen.

    0
  • S

    Am schnellsten wärs wohl, wenn einem doch noch eine Formel dafür einfällt 😉

    MfG SideWinder

    0
  • W

    Ich habe die Zahlen bis 2^32 nun in 22 Sekunden geprüft. Das eben war eine fehlerhafte Messung in der ich noch ein paar Debugsachen drin hatte.

    0
  • ?

    Walli schrieb:

    Ich habe die Zahlen bis 2^32 nun in 22 Sekunden geprüft. Das eben war eine fehlerhafte Messung in der ich noch ein paar Debugsachen drin hatte.

    Wow. Wieviele findest du denn bis 2^32? 👍

    0
  • O

    wie erreichst du 22s? schätzt du die zahlen nur?

    0
  • ?

    volkard schrieb:

    #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?

    Sieht auf den ersten Blick zumindest sehr gut aus. 🙂

    0
  • S

    otze schrieb:

    wie erreichst du 22s? schätzt du die zahlen nur?

    Vielleicht hat er im Gegensatz zu dir aber auch bloß ein Dual-System mit zwei Intel Pentium 3,2 GHz und fängt auf einem Rechner von oben nach unten und auf dem anderen von unten nach oben an 😉

    MfG SideWinder

    0
  • V

    hab ein sieb hochgeladen, falls jemand ne referenzimplementierung braucht.

    windows: http://www.volkard.de/download/primeGenerator.exe
    linux: http://www.volkard.de/download/primeGenerator

    aufruf: primeGenerator 100
    und ausgabe ist
    "2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 "
    statt 100 darf man auch größere zahlen nehmen.

    die geschwindigkeit ist vermutlich höher als eure lösung, aber es ist ja auch ein sieb des eratosthenes. kann also nur aufeianderfolgende prim zahlen schnell finden. ihr macht ja ne funktion, die die zahlen durcheiander kriegt und jede zahl einzeln testen muss, weil sie gar nicht hintereinander sind.

    0
  • S

    Da fällt mir ein: Caching in irgendeiner Weise erlaubt? Was natürlich dann auch ein Durchschnittsergebnis aus ~50 Messugnen benötigt um aussagekräftig zu werden. Sonst kann man Glück und Pech haben.

    MfG SideWinder

    0
  • W

    Also ich messe mit so ner Timerklasse die irgendwer mal gepostet hatte. Wie genau die ist, k.A. Deckt sich jedenfalls halbwegs mit der Stoppuhr.

    #ifndef TIMER_HPP
#define TIMER_HPP

#include <ctime>
#include <iostream>

class Timer
{
    unsigned n;
    clock_t start;
public:
    Timer(unsigned number = 0) : n(number), start(clock()) {}
    ~Timer() {
		std::cout << "timer " << n << ": "
			<< static_cast<float>(clock() - start) / CLOCKS_PER_SEC << " sec." << std::endl;
	}
};

#endif

    Aber ich glaube ich muss mein Ergebnis mit den 2^32 nochmal zurückziehen. Irgendwie sind das zu wenige Primzahlen, die der findet... 😞

    0
  • V

    FireFlow schrieb:

    Was muss alles in dem Archiv drin sein? 64Kb sind wenig^^

    naja, gepackt ist das schon einiges. viel größer kann's aber nicht sein, da sonst die leute mit monster-tabellen ankommen.

    Reicht der Source und nen Comment zu den Compile-Einstellungen?

    reicht völlig. das ist mir sogar am liebsten.

    Welcher Compiler wird beim Test genutzt?

    keine ahnung. mal sehen, was wir beim forentreff zur verfügung haben. es haben bisher immer ein genügend leute rechner mitgehabt. nsbesondere moderne rechner. das testen auf meiner alten hardware ergibt eh keine guten ergebnisse. ich hoffe, daß jemand linux und windows auf einem rechner hat. ich denke mal, vom gcc für linux und vom msvc für windows können wir ausgehen. aber wie gesagt, ich weiß nichtmal, ob überhaupt auf dem treffen getestet werden kann.

    weil ich nix über die hardware sagen kann, kann man auch mehrere einsendungen abgeben. vielleicht will SideWinder ja 512MB ram dazu benutzen, eine riesige std::map als cache anzulegen. und wenn der rechner nur 256MB hat, kackt das programm ab. deswegen sollte er zur sicherheit dann auch eine version ohne cache einreichen.

    [quote]Ich mein fertige Binarys testen kanns net sein da kann man bescheissen ;)/quote]
    wie bescheißen?

    das problem ist, daß einer vielleicht was in lisp oder forth oder algol66 einreicht und wir keinen compiler dafür beschaffen können.

    0
Anmelden zum Antworten