Re: RNGs: A Super KISS

On Nov 4, 1:26*pm, user923005 <dcor...@connx.com> wrote:
> On Nov 4, 9:18*am, David <david.astgt...@gmail.com> 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[i] + carry;
carry = (t >> 32);
Q[i] =(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[i] = (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

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[i] + carry;

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

> carry = (t >> 32);
> Q[i] =(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[i] = (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

On 4 nov, 22:51, Victor Bazarov <v.Abaza...@comAcast.net> 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[i] + carry;
>
> And neither is there the 'LL' suffix...
>
>
>
> > * * * * * * carry = (t >> 32);
> > * * * * * * Q[i] =(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[i] = (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()cng(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