Prev: Hey guys, what is this all about? MQQ digital signature scheme?
Next: Skype will be open sourced
From: James Waldby on 4 Nov 2009 13:09
On Wed, 04 Nov 2009 09:18:14 -0800, 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?

That result is like what I mentioned in my posts yesterday;
505478909. == 0x1e20fefd, which is the low 32 bits
of 2904265093743181565. == 0x284e05b71e20fefd .

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

--
jiw
From: user923005 on 4 Nov 2009 16:26
On Nov 4, 9:18 am, David <david.astgt...(a)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.

From: user923005 on 4 Nov 2009 16:31
On Nov 4, 1:26 pm, user923005 <dcor...(a)connx.com> wrote:
> On Nov 4, 9:18 am, David <david.astgt...(a)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?
*/
From: Keith on 23 Nov 2009 06:45
geo wrote:

> For those mesmerized (or Mersenne-ized?) by a RNG
> with period 2^19937-1, I offer one here with period
> 54767*2^1337279---over 10^396564 times as long.
> It is one of my CMWC (Complimentary-Multiply-With-Carry) RNGs,
> and is suggested here as one of the components of a
> super-long-period KISS (Keep-It-Simple-Stupid) RNG.

I've taken a look through this, and it's not clear to me how you 'seed'
this generator to provide a unique 'starting point'. Is it sufficient
to initiallise Q[] with random stuff?
From: geo on 24 Nov 2009 10:51
On Nov 23, 6:45 am, Keith <m...(a)privacy.net> wrote:
> geo wrote:
> > For those mesmerized (or Mersenne-ized?) by a RNG
> > with period 2^19937-1, I offer one here with period
> > 54767*2^1337279---over 10^396564 times as long.
> > It is one of my CMWC (Complimentary-Multiply-With-Carry) RNGs,
> > and is suggested here as one of the components of a
> > super-long-period KISS (Keep-It-Simple-Stupid) RNG.
>
> I've taken a look through this, and it's not clear to me how you 'seed'
> this generator to provide a unique 'starting point'.  Is it sufficient
> to initiallise Q[] with random stuff?

Yes.
As stated in the original posting:

"Users should choose a reasonable number of the 1337280
random bits that a fully-seeded Q array requires."

The degree of reasonableness depends on whether the
application is for simulation or for security.

With b=2^32, the SUPR part of this KISS=SUPR+CNG+XS
produces, in reverse order by the CMWC method, the
base-b expansion of the rational number k/p for
the prime p=7010176*b^41490+1, with k determined
by the seed values in Q and the initial carry.

There are repeating cycles of 54767*2^1337279 base-b
"digits" in that expansion---the order of b for the prime p.
If you have a given set of a few thousand "digits" in
that sequence and you want to know precursors or
successors, you are pretty much stuck if the initial
Q array was fully seeded---there are so many places
where a particular string can appear that finding a
specific one becomes extremely difficult.

If only, say, 64 bits were used to seed the Q array
by means of CNG+XS, then a particular string may appear
at considerably fewer places in that base-b expansion.
The task of locating a particular location, so as to
get precursors or successors, is reduced but may be feasible.

But any one of the many appearances of that particular
string of base-b digits is likely to serve well as a set
of independent random 32-bit integers---just, as, for example,
strings of bits in the binary expansion of pi are could well
run Las Vegas, if chosen from an unknown random location
among the first 10^400000 places, specified each day.

Thus, for simulation purposes, some 60-100 seed bits seem to
serve very well; for security, more of the 1.3 million
seed bits should chosen---the more, the safer.
First  |  Prev  | 
Pages: 1 2 3
Prev: Hey guys, what is this all about? MQQ digital signature scheme?
Next: Skype will be open sourced