Re: RNGs: A Super KISS

Discussion in 'C++' started by user923005, Nov 4, 2009.

  1. user923005

    user923005 Guest

    On Nov 4, 1:26 pm, user923005 <> wrote:
    > On Nov 4, 9:18 am, David <> wrote:
    >
    > > On an x86-64 machine using GCC version 4.3.3 (Ubuntu 4.3.3-5ubuntu4),
    > > both the C code and C++ code fail for me.
    > > I get:
    > >      x=505478909.
    > > Does x=-872412446?

    >
    > > Changing the unsigned long's to unsigned int's fixed the problem.
    > > And it does matter: before the change, the generator failed a variety
    > > of tests (really odd assortment, though: parking lot, 2dsphere,
    > > 3dsphere, squeeze, and sums).

    >
    > OK, makes sense.  The RNG must assume 32 bit longs.


    Modified C++ code:

    #include <iostream>

    class SuperKiss {

    private:
    unsigned int Q[41790];
    unsigned int indx;
    unsigned int carry;
    unsigned int xcng;
    unsigned int xs;

    int refill ()
    {
    int i;
    unsigned long long t;
    for (i = 0; i < 41790; i++)
    {
    t = 7010176LL * Q + carry;
    carry = (t >> 32);
    Q =(unsigned int) ~(t);
    }
    indx = 1;
    return (Q[0]);
    }

    public:
    // Constructor:
    SuperKiss()
    {
    indx = 41790;
    carry = 362436;
    xcng = 1236789;
    xs = 521288629;
    unsigned i;
    for (i = 0; i < 41790; i++)
    Q = (xcng = 69609 * xcng + 123) +
    (xs ^= xs << 13, xs ^= (unsigned) xs >> 17, xs ^=
    xs >> 5);
    }

    // Collect next random number:
    unsigned int SKRand() {
    return (indx < 41790 ? Q[indx++] : refill ()) +
    (xcng = 69609 * xcng + 123) +
    (xs ^= xs << 13, xs ^= (unsigned) xs >> 17, xs ^= xs >>
    5);
    }
    };

    int
    main ()
    {
    unsigned int i;
    int x=0;
    SuperKiss sk;
    for (i = 0; i < 1000000000; i++)
    x = sk.SKRand();
    std::cout << " x = " << x << std::endl << "Does x=-872412446?"
    << std::endl;
    return 0;
    }

    /* Possible output:
    x = -872412446
    Does x=-872412446?
    */
     
    user923005, Nov 4, 2009
    #1
    1. Advertising

  2. user923005 wrote:
    > [..]
    > Modified C++ code:


    Can be actually made closer to C++, if you initialize variables instead
    of declaring and assigning, etc.

    >
    > #include <iostream>
    >
    > class SuperKiss {
    >
    > private:
    > unsigned int Q[41790];
    > unsigned int indx;
    > unsigned int carry;
    > unsigned int xcng;
    > unsigned int xs;
    >
    > int refill ()
    > {
    > int i;
    > unsigned long long t;


    BTW, currently there is no 'long long' in C++... Although it is offered
    as an extension by some compilers.

    > for (i = 0; i < 41790; i++)
    > {
    > t = 7010176LL * Q + carry;


    And neither is there the 'LL' suffix...

    > carry = (t >> 32);
    > Q =(unsigned int) ~(t);
    > }
    > indx = 1;
    > return (Q[0]);
    > }
    >
    > public:
    > // Constructor:
    > SuperKiss()
    > {
    > indx = 41790;
    > carry = 362436;
    > xcng = 1236789;
    > xs = 521288629;
    > unsigned i;
    > for (i = 0; i < 41790; i++)
    > Q = (xcng = 69609 * xcng + 123) +
    > (xs ^= xs << 13, xs ^= (unsigned) xs >> 17, xs ^=
    > xs >> 5);
    > }
    >
    > // Collect next random number:
    > unsigned int SKRand() {
    > return (indx < 41790 ? Q[indx++] : refill ()) +
    > (xcng = 69609 * xcng + 123) +
    > (xs ^= xs << 13, xs ^= (unsigned) xs >> 17, xs ^= xs >>
    > 5);


    There seems to be a common subexpression in two of those functions (ctor
    and 'SKRand'), I'd create a separate function for it.

    > }
    > };
    >
    > int
    > main ()
    > {
    > unsigned int i;
    > int x=0;
    > SuperKiss sk;
    > for (i = 0; i < 1000000000; i++)
    > x = sk.SKRand();
    > std::cout << " x = " << x << std::endl << "Does x=-872412446?"
    > << std::endl;
    > return 0;
    > }
    >
    > /* Possible output:
    > x = -872412446
    > Does x=-872412446?
    > */


    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Nov 4, 2009
    #2
    1. Advertising

  3. On 4 nov, 22:51, Victor Bazarov <> wrote:
    > user923005 wrote:
    > [...]
    >
    > > #include <iostream>

    >
    > > class SuperKiss {

    >
    > > private:
    > >     unsigned int  Q[41790];
    > >     unsigned int  indx;
    > >     unsigned int  carry;
    > >     unsigned int  xcng;
    > >     unsigned int  xs;

    >
    > >     int refill ()
    > >     {
    > >         int i;
    > >         unsigned long long t;

    >
    > BTW, currently there is no 'long long' in C++...  Although it is offered
    > as an extension by some compilers.
    >
    > >         for (i = 0; i < 41790; i++)
    > >         {
    > >             t = 7010176LL * Q + carry;

    >
    > And neither is there the 'LL' suffix...
    >
    >
    >
    > >             carry = (t >> 32);
    > >             Q =(unsigned int) ~(t);
    > >         }
    > >         indx = 1;
    > >         return (Q[0]);
    > >     }

    >
    > > public:
    > >     // Constructor:
    > >     SuperKiss()
    > >     {
    > >         indx  = 41790;
    > >         carry = 362436;
    > >         xcng  = 1236789;
    > >         xs    = 521288629;
    > >         unsigned i;
    > >         for (i = 0; i < 41790; i++)
    > >             Q = (xcng = 69609 * xcng + 123) +
    > >                    (xs ^= xs << 13, xs ^= (unsigned) xs >> 17, xs ^=
    > > xs >> 5);
    > >     }

    >
    > >     // Collect next random number:
    > >     unsigned int SKRand() {
    > >         return (indx < 41790 ? Q[indx++] : refill ()) +
    > >                (xcng = 69609 * xcng + 123) +
    > >                (xs ^= xs << 13, xs ^= (unsigned) xs >> 17, xs ^= xs >>
    > > 5);

    >
    > There seems to be a common subexpression in two of those functions (ctor
    > and 'SKRand'), I'd create a separate function for it.


    And they rely on the same state, I would create a generator class but
    I don't know if that would improve the speed.

    struct SuperKissGenerator
    {
    unsigned long xcng;
    unsigned long xs;

    SuperKissGenerator():xcng(1236789),xs(521288629){}

    unsigned long operator()()const
    {
    xcng = 69609 * xcng + 123;
    xs ^= xs << 13;
    xs ^= (unsigned) xs >> 17;
    xs ^= xs >> 5;
    return xcng + xs;
    }
    };

    And then a member
    SuperKissGenerator generator;

    in constructor:
    std::generate(Q,Q+41790,generator);

    in SKRand:
    return (indx < 41790 ? Q[indx++] : refill ()) + generator();

    --
    Michael
     
    Michael Doubez, Nov 5, 2009
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. geo

    64-bit KISS RNGs

    geo, Feb 28, 2009, in forum: C Programming
    Replies:
    23
    Views:
    3,096
  2. geo

    RNGs: A Super KISS

    geo, Nov 3, 2009, in forum: C Programming
    Replies:
    8
    Views:
    607
    user923005
    Nov 4, 2009
  3. user923005

    Re: RNGs: A Super KISS

    user923005, Nov 3, 2009, in forum: C++
    Replies:
    1
    Views:
    1,456
    user923005
    Nov 3, 2009
  4. geo

    RNGs: A double KISS

    geo, Apr 14, 2010, in forum: C Programming
    Replies:
    10
    Views:
    1,028
    steve
    Apr 17, 2010
  5. Dann Corbit

    Re: RNGs: A double KISS

    Dann Corbit, Apr 14, 2010, in forum: C++
    Replies:
    3
    Views:
    422
    Jonathan Lee
    Apr 14, 2010
Loading...

Share This Page