Keskustelu: Koodit: C++: rnd32

/**********************
* Jouni Aro 20.7.2020 *
**********************/

/******************************************************
* Ohessa kooditiedosto Xrandom.cpp, joka käyttää      *
* alkulukuja.                                         *
*                                                     *
* Sen main -funktio tutkii, kuinka pitkiä numero-     *
* ketjuja rnd32 -funktio tuottaa.                     *
*                                                     *
* Koodi menee liian kryptiseksi, jos mukaan sekoittaa *
* neliöjuuri 2:n bitit. Koodi Xrandom.cpp toimii nyt  *
* alkuluvuilla.                                       *
******************************************************/

#include <time.h>
#include <math.h>

#include <stdio.h>
#include <conio.h>

#include <memory.h>
#include <assert.h>

typedef unsigned short uint16;
typedef unsigned long  uint32;

inline void setBit(char *a, int bitNro)
{
    a[bitNro>>3]|=(char)(1<<(bitNro&7));
}

inline void clrBit(char *a, int bitNro)
{
    a[bitNro>>3]&=(char)~(1<<(bitNro&7));
}

inline int testBit(char *a, int bitNro)
{
    int v=(char)bitNro&7;
    int e=(int)bitNro>>3;
    return a[e]&(1<<v)? 1: 0;
}

int primeNumber(int x)
{
    if (x<2) return (int)0;
    else if (x==2) return 1;
    else if (!(x%2)) return 0;
    else
    {
        int end=(int)(sqrt((double)x)+2.0);
        for (int y=3; y<end; y+=2)
        if (!(x%y)) return 0;
        return (int)0x01;
    }
}

class Eratos
{
    public:

    Eratos(void);
    ~Eratos(void);

    unsigned getN(void);
    uint32 swap(uint32, uint32);

    private:

    char *E;
    unsigned f;
    uint16 *Memory;
    unsigned N, BitSize;

    void backward(void);
    void MakePrimeNumbers(char*);
};

inline unsigned Eratos::getN(void)
{
    return N;
}

inline uint32 Eratos::swap(uint32 a, uint32 b)
{
    if (a>=N||b>=N) assert(0);
    uint16 tmp = Memory[a];
    Memory[a] = Memory[b];
    Memory[b] = (uint16) tmp;
    return uint32(Memory[a]^Memory[b]);
}

///////////////////////
#define SL 17 // shl //
///////////////////////

Eratos::Eratos(void)
{
    memset(this,0,sizeof(Eratos));
    E=new char[N=(0x0001<<SL)];
    Memory=new uint16[1<<16];
    BitSize=(0x01<<SL)<<3;
    MakePrimeNumbers(E);

    for (f=N=0; f<BitSize; f++)
    if (testBit(E, f))
    {
        Memory[(int)N] = (uint16) f;
        if ((++N) == (1<<16)) break;
    }

    if (N!=(1<<16))
    assert((int)0);
    else backward();
}

void Eratos::backward(void)
{
    for (--N; N; N--)
    if (primeNumber(N))
    {
        N+=1;
        break;
    }
}

Eratos::~Eratos(void)
{
    delete[] Memory;
    delete[] E;
}

void Eratos::MakePrimeNumbers(char *X)
{
    memset(X, 0xff, sizeof(char)*N);
    int end=(int)sqrt(double(BitSize))+2;
    clrBit((char*)X, 0);
    clrBit((char*)X, 1);

    for (int x=2; x<=end; x++)
    {
        if (testBit((char*)X, x))
        {
            for (int y=x+x; y<(int)BitSize; y+=x)
            clrBit((char*)X, y);
        }
    }
}

/////////////////////////////////////
unsigned rnd32(void)               //
{                                  //
    static Eratos *E=new Eratos;   //
    static unsigned long r1=1L;    //
    static unsigned long r2=2L;    //
    r1 -= 0x012357bfL;             //
    r2 += 0xfedca201L;             //
    unsigned a=E->getN();          //
    unsigned b=E->getN();          //
    r1 ^= E->swap(~r1%a, (~r2)%b); //
    r2 ^= E->swap(r1%a, r2%b)<<16; //
    r1 += (r1>>16)^(r2<<16);       //
    r2 -= (r1<<16)^(r2>>16);       //
    return r1^r2;                  //
}                                  //
/////////////////////////////////////

/////////////////////////////////////
#define KPL 17 // Tällä parametril-//
// la voi säätää tutkittavan       //
// numerosarjan pituutta. main-    //
// funktio ottaa sitten selvää     //
// sekvenssin jakaumasta.          //
/////////////////////////////////////

int main(int argc, char** argv)
{
    unsigned maxKpl[KPL];
    unsigned ketjut[KPL];

    memset(maxKpl, 0, sizeof(unsigned)*KPL);
    memset(ketjut, 0, sizeof(unsigned)*KPL);

    for (int n, ede=0, print=0;;)
    {
        n=rnd32()%KPL;
        ketjut[n]+=1;

        for (int i=0; i<KPL; i++)
        {
            if (ketjut[i]!=maxKpl[i])
            {
                if (ketjut[i]>maxKpl[i])
                {
                    maxKpl[i]=ketjut[i];
                    print=1;
                }
            }
        }

        if (n!=ede && print==0)
        {
            ede=n;
            memset(ketjut, 0, sizeof(unsigned)*KPL);
        }

        if (print)
        {
            print=0;
            memset(ketjut, 0, sizeof(unsigned)*KPL);
            printf("| ");
            for (int i=0; i<KPL; i++)
            printf("%u | ", maxKpl[i]);
            printf("\n");
        }
    }
    return 0;
}