3. Wer kann die schnellsten Primzahlen?

Wer kann die schnellsten Primzahlen?

  • V

    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

    6

    aus, wenn ich die standardwerte lasse.

    0
  • O

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

    0
  • V

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

    0
  • V

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

    0
  • V

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

    0
  • V

    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
    0
  • ?

    Wer hat überhaupt alles mitgemacht?

    0
  • V

    interessanter wäre... schrieb:

    Wer hat überhaupt alles mitgemacht?

    nur er.

    0
  • ?

    ROFLMAO! 🤡

    0
  • B

    Schlägt er denn deine Variante, volkard?

    0
  • J

    Nein, ziemlich sicher nicht. Hier werden ja relativ stupide alle Teiler getestet. Miller-Rabin (auch entrandomisiert) kann da aber was rausholen.

    0
  • O

    ok, meine version wär schneller gewesen 🙄

    0
  • V

    otze schrieb:

    ok, meine version wär schneller gewesen 🙄

    warum haste nicht eingeschickt?

    0
  • ?

    bestimmt weil er dachte jester macht mit. :p

    0
Anmelden zum Antworten