Wer kann die schnellsten Primzahlen?

FireFlow

Jester schrieb:

FireFlow schrieb:

Für kleine Zahlen hab ich 100% bei extrem großen dann eigentlich nicht mehr aber es ist sooooo unrealistisch dass ich dabei etwas falsch erkenne dass ich es schon fast ausschließe. Momentan bastel ich aber noch dran rum.

Hatten wir nicht genau dieses Vorgehen ausgeschlossen?

Wenn ich damit fertig bin wirds noch bischen langsamer aber ich bekomm es hin dass es keine Fehler gibt.

FireFlow schrieb:

Wenn ich damit fertig bin wirds noch bischen langsamer aber ich bekomm es hin dass es keine Fehler gibt.

Wenn dein Verfahren wirklich so schnell ist, wie du sagst, kannst du die Korrektheit ja mal halbwegs durch einen Vergleich mit meinem Primzahlzählprogramm überprüfen. Zähl mit deinem Programm oben doch einfach auch mal die Primzahlen zwischen 0 und 1.000.000.000. Was da IMHO rauskommen sollte, habe ich weiter oben schon gepostet. Ich bin mir relativ sicher, dass der Wert, den ich da rauskriege korrekt ist.

/me würde das Ergebnis sehr interessieren.

Hier nochmal das IMHO korrekte Ergebnis:

Zwischen 0 und 1000000000 liegen 50847534 Primzahlen.

FireFlow

Gregor@Home schrieb:

Hier nochmal das IMHO korrekte Ergebnis:

Zwischen 0 und 1000000000 liegen 50847534 Primzahlen.

Bin grade bei 60Mio das ghet noch ne Weile *narf-narf*. Ich erwarte aber eher etwas falsches hab grade etwas rumoptimiert und geh davon aus dass ich hier oder da ein Fehler hab. Hab extra die langsame Variante gewählt die nicht auf Wahrscheinlichkeiten aufbaut. Wenn ich fertig bin gibts mein Ergebniss auch.

Woher hast du das Ergebniss?

FireFlow schrieb:

Woher hast du das Ergebniss?

Primzahlen von 0 bis n zählen kann man ja deutlich schneller machen als wenn man eine einzelne Primzahl überprüfen muss. Ich habe da vor Jahren mal ein Programm zum Primzahlzählen geschrieben (Optimizer kann dir dazu auch was erzählen ). Das nutzt letztendlich ein einfaches Sieb des Erathostenes.

Wenn du willst, kann ich auch nochmal die Anzahl der Primzahlen bis zu einer kleineren Obergrenze posten. 100.000.000 oder 10.000.000 oder so.

FireFlow

Wooh stimmt ich hab über das Sieb was gefunden hab aber keine Implementation. Wär super wenn du mal immer so von 10^n die Anzahl angibst. 1Mrd reicht ja als Obergrenze. Wenn mein Programm bis dahin und darüber stichprobebartig korrekt arbeitet gehe ich davon aus dass es klappt.

Ich muss das noch irgendwie optimieren, naja bin ja Schüler und hab massig Zeit *hihi*

Zarniwoop

Kan man seinen Code auch einrechen, wenn man beim Forumstreffen nicht dabei ist?

Gibt es eigentlich einen Einsendeschluss?
edit: erst lesen, dann posten... steht gleich im ersten Post.

Zarniwoop

Da sind ein paar andere Ergebnisse:

Zwischen 0 und 100000000 liegen 5761455 Primzahlen.
Zwischen 0 und 10000000 liegen 664579 Primzahlen.
Zwischen 0 und 1000000 liegen 78498 Primzahlen.
Zwischen 0 und 100000 liegen 9592 Primzahlen.

Gregor@Home schrieb:

Ich habe da vor Jahren mal ein Programm zum Primzahlzählen geschrieben (Optimizer kann dir dazu auch was erzählen ).

Nein, kann ich nicht.

Optimizer schrieb:

Nein, kann ich nicht.

otze

FireFlow schrieb:

Wooh stimmt ich hab über das Sieb was gefunden hab aber keine Implementation. Wär super wenn du mal immer so von 10^n die Anzahl angibst. 1Mrd reicht ja als Obergrenze. Wenn mein Programm bis dahin und darüber stichprobebartig korrekt arbeitet gehe ich davon aus dass es klappt.

nein, kannst du nicht. eine milliarde ist nur ein winzig kleiner bruchteil von der 64bit reichweite die hier gefordert ist, dh wenn dein schätz algo irgendeine minimalabweichung hat, finden wir die spätestens nach der veröffentlichung des codes

übrigens braucht man maximal eine minute, um folgenden link bei google zu bekommen:

http://www.utm.edu/research/primes/howmany.shtml

volkard

Der Generator ist vorläufig fertig.

Er hat eine Periode von 2^64.
Er bringt die Zahlen in folgender Verteilung:

<10: 0.00924%
<100: 0.09225%
<1000: 0.93736%
<10000: 6.20014%
<100000: 12.5577%
<1000000: 19.0556%
<10000000: 25.3772%
<100000000: 31.7213%
<1000000000: 38.1788%
<10000000000: 44.5419%
<100000000000: 50.9001%
<1000000000000: 57.3257%
<10000000000000: 63.7329%
<100000000000000: 70.0624%
<1000000000000000: 76.4963%
<10000000000000000: 82.874%
<100000000000000000: 89.1879%
<1000000000000000000: 95.4239%

Das ist die Ausgabe folgenden Messprogramms:

#include <iostream>
using namespace std;

typedef long long i64;

int main()
{
    //diese werte werden normalerweise eingelesen
    i64 randa=123;
    i64 randb=456;
    i64 randx=789;
    i64 count=10000000;

    //macht die periode des zufallszahlengenerators lang
    randa=2*randa+1;
    randb=4*randb+1;

    for(i64 max=10;max>0;max=max*10){
        i64 c=0;
        for(i64 i=0;i<count;++i){
            randx=randx*randa+randb;
            i64 n=(randx&0x7fffffff80000000LL)>>31;
            randx=randx*randa+randb;
            n=n|(randx&0x7fffffff00000000LL);
            randx=randx*randa+randb;
            int shift=(randx&0x7fffffff00000000LL)>>32;
            n=n>>(shift%52);

            if(n<max) ++c;

        }
        cout<<"<"<<max<<": "<<c/double(count/100)<<'%'<<endl;
    }
	return 0;
}

Um Zu testen, ob der Generator bei Euch funktioniert, nehmt vielleicht

#include <iostream>
using namespace std;

typedef long long i64;

int main()
{
    //diese werte werden normalerweise eingelesen
    i64 randa=123;
    i64 randb=456;
    i64 randx=789;
    i64 count=100000;

    //macht die periode des zufallszahlengenerators lang
    randa=2*randa+1;
    randb=4*randb+1;

    i64 test=0;
    for(i64 i=0;i<count;++i){
        randx=randx*randa+randb;
        i64 n=(randx&0x7fffffff80000000LL)>>31;
        randx=randx*randa+randb;
        n=n|(randx&0x7fffffff00000000LL);
        randx=randx*randa+randb;
        int shift=(randx&0x7fffffff00000000LL)>>32;

        n=n>>(shift%52);
        test+=n%1000000*i;
    }
    cout<<test<<endl;
    return 0;
}

Ausgabe:
2153201463864000

Das Hauptprogramm soll dann so aussehen:

int main()
{
    //diese werte werden normalerweise eingelesen
    i64 randa=123;
    i64 randb=456;
    i64 randx=789;
    i64 count=100;

    //zum normalen testen einfach folgende zeile auskommentieren
    cin>>randa>>randb>>randx>>count;

    //macht die periode des zufallszahlengenerators lang
    randa=2*randa+1;
    randb=4*randb+1;

    i64 ergebnis=0;
    for(i64 i=0;i<count;++i){
        randx=randx*randa+randb;
        i64 n=(randx&0x7fffffff80000000LL)>>31;
        randx=randx*randa+randb;
        n=n|(randx&0x7fffffff00000000LL);
        randx=randx*randa+randb;
        int shift=(randx&0x7fffffff00000000LL)>>32;

        n=n>>(shift%52);
        if(isPrime(n)){
            ++ergebnis;
//            cout<<n<<endl;
        }
    }
    cout<<ergebnis<<endl;
	return 0;
}

es gibt bei mir

aus, wenn ich die standardwerte lasse.

otze

aha...also ist es nicht erlaubt, die werte nach der generierung zu sortieren...schade

volkard

otze schrieb:

aha...also ist es nicht erlaubt, die werte nach der generierung zu sortieren...schade

doch, klaro.
das "Das Hauptprogramm soll dann so aussehen:" war nicht würtlich zu nehmen.
"das hauptprogramm soll dann so aussehen oder eine ausgabe erzeugen, die gleich ist, ganz völlig egal, wie ihr das hinkriegt".

volkard

ein weiteres ergebnis:
echo 1234 4711 8000 1000 | fpc.exe
gibt bei mir
55
aus.

volkard

bringt euren code einfach zum treffen mit.
wer nicht kommt, kann auch nach volkard@gmx.net schicken.

volkard

der gewinner ist 0xdeadbeef.

der gewinnercode:

/*	$NetBSD: pr_tbl.c,v 1.7 2003/08/07 09:37:33 agc Exp $	*/

/*
 * Copyright (c) 1989, 1993
 *	The Regents of the University of California.  All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Landon Curt Noll.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <stdio.h>

unsigned long const primes[] = {
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,101,103,
...und so weiter...
65407,65413,65419,65423,65437,65447,65449,65479,65497,65519,65521,65537,0
};

bool isPrime(unsigned long long x) {
  unsigned long long i;
  unsigned j;

  if(x == 2 || x == 3 || x == 5 || x == 7)
    return 1;
  if(x < 2 || x % 2 == 0 || x % 3 == 0 || x % 5 == 0 || x % 7 == 0)
    return 0;

  if(x <= 65537 * 65537) {
    for(i = 4; primes[i] * primes[i] <= x; ++i)
      if(x % primes[i] == 0)
	return 0;
  } else {
    for(i = 4; primes[i]; ++i) 
      if(x % primes[i] == 0)
	return 0;
    j = 2;
    for(i = primes[i - 1] + 2; i * i <= x; i += (j = 6 - j))
      if(x % i == 0)
	return 0;
  }

  return 1;
}
//nebst der main, die schon gepostet wurde

Wer hat überhaupt alles mitgemacht?

volkard

interessanter wäre... schrieb:

Wer hat überhaupt alles mitgemacht?

nur er.

ROFLMAO!