A simple (but effective) random number generator(?!)


S

sebastian

A while back, as I was playing around with some ideas for pseudo-
random number generators, I came up with a deceptively simple one that
seemed to perform remarkably well. I've subjected it to a battery of
tests, including NIST, DIEHARD, Fourmilab's ENT, as well as some of my
own, and in all cases it's performance has been confirmed it to be a
suitable PRNG algorithm. Thing is, tho, I'm not completely convinced -
it's just too damn simple! I keep thinking that there must be some
flaw in the algorithm that has escaped these trials. What I really
need is someone with a really good grasp of mathematics to look it
over, methinks. Any takers?

Here is the code for the PRNG:

*****************************************************************************
#ifndef GARTH_RANDOM_HPP
#define GARTH_RANDOM_HPP

template < typename UnsignedInteger >
class garth_random
{
public:

inline garth_random( UnsignedInteger initial = UnsignedInteger( ) )
{
seed( initial );
}

void seed( UnsignedInteger initial )
{
m_value_ = initial;
m_counter_ = m_scale_ = 0;
}

UnsignedInteger operator ( )( void )
{
static UnsignedInteger const
zero = 0,
one = 1,
mask = ~zero,
msb = ~( mask >> one );
if( m_counter_++ == zero )
++m_scale_;
UnsignedInteger
temp = ( m_value_ * m_scale_++ ) + one;
return m_value_ =
(
( ( ( temp << one ) | ( ( temp & msb ) ? one : zero ) ) ^
m_counter_ ) ^ mask
);
}

inline operator UnsignedInteger( void )
{
return m_value_;
}

protected:

UnsignedInteger
m_value_,
m_scale_,
m_counter_;
};
#endif
*****************************************************************************

The algorithm has some notable properties that I should probably
mention:
(1) It's *definately* not sufficient for crypographic applications -
predicting it's state from one transition to the next is most likely
trivial.
(2) It has a very precise period of 4^N, where N is the number of bits
in the underlying integral type - so for example, using a 32-bit
number, the PRNG will produce a unique sequence of
18,446,744,073,709,551,616 numbers, given some arbitrary seed value.
(3) Unlike most PRNG's, it doesn't have to be taylored for a specific
architecture (that is, it doesn't rely on the fact that a short is 16-
bits, or some such). It's completely generic, working equally well for
integers containing 8 bits, 64 bits, 128 bits, or what have you.
(4) It's extremely fast.
(5) It's memory footprint is essentially negligible.
(6) It produces a good distribution (much to my dismay, actually).

And here a sample of the output from one of the tests (Fourmilab's
ENT):

*****************************************************************************
--- std::rand ---

Value Char Occurrences Fraction
0 17120290 0.531920
1 15065534 0.468080

Total: 32185824 1.000000

Entropy = 0.997058 bits per bit.

Optimum compression would reduce the size
of this 32185824 bit file by 0 percent.

Chi square distribution for 32185824 samples is 131176.45, and
randomly
would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bits is 0.4681 (0.5 = random).
Monte Carlo value for Pi is 3.830697142 (error 21.93 percent).
Serial correlation coefficient is -0.003975 (totally uncorrelated =
0.0).

--- marsenne ---

Value Char Occurrences Fraction
0 16078169 0.500499
1 16046079 0.499501

Total: 32124248 1.000000

Entropy = 0.999999 bits per bit.

Optimum compression would reduce the size
of this 32124248 bit file by 0 percent.

Chi square distribution for 32124248 samples is 32.06, and randomly
would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bits is 0.4995 (0.5 = random).
Monte Carlo value for Pi is 3.148647377 (error 0.22 percent).
Serial correlation coefficient is -0.000144 (totally uncorrelated =
0.0).

--- garth_random ---

Value Char Occurrences Fraction
0 16079544 0.500566
1 16043184 0.499434

Total: 32122728 1.000000

Entropy = 0.999999 bits per bit.

Optimum compression would reduce the size
of this 32122728 bit file by 0 percent.

Chi square distribution for 32122728 samples is 41.16, and randomly
would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bits is 0.4994 (0.5 = random).
Monte Carlo value for Pi is 3.147524816 (error 0.19 percent).
Serial correlation coefficient is -0.000060 (totally uncorrelated =
0.0).
*****************************************************************************

It outperforms my system's std::rand function by a wide margin (and
consistently did so in all other tests), and performs comparably to
the marsenne-twister (in some tests slightly better, others slightly
worse), in all cases.

Anyway, any and all input would be appreciated. Thanks!
 
Ad

Advertisements

J

Juha Nieminen

sebastian said:
Anyway, any and all input would be appreciated. Thanks!

I tested its speed against the isaac rng and std::rand() here by
running each one in a loop 4000000000 times (and adding the result to
a variable and returning that variable from main() so that the compiler
is prohibited from optimizing anything away), and got these results:

IsaacRand: 27 s.
garth_random: 16 s.
std::rand: 120 s.

(I used the gcc compiler options -O3 -march=native)

I haven't tested the quality of your rng, though.
 
J

Jorgen Grahn

A while back, as I was playing around with some ideas for pseudo-
random number generators, I came up with a deceptively simple one that
seemed to perform remarkably well. I've subjected it to a battery of
tests, including NIST, DIEHARD, Fourmilab's ENT, as well as some of my
own, and in all cases it's performance has been confirmed it to be a
suitable PRNG algorithm. Thing is, tho, I'm not completely convinced -
it's just too damn simple! I keep thinking that there must be some
flaw in the algorithm that has escaped these trials. What I really
need is someone with a really good grasp of mathematics to look it
over, methinks. Any takers?

Sorry; not me. You need to remember a bit of your school algebra to be
able to analyze it, and I don't. "Too damn simple" is my gut reaction
too ...

I don't know where you should go for advice. The crypto groups are
out, I guess. How about whoever was involved in Boost::random?

One question though:
Here is the code for the PRNG:
....

What license do you have in mind for the code? If this had been two
years ago when I desperately needed a fast, simple, PRNG with a small
non-global state I would have used it -- but only if the license terms
were clear and permissive (like modified BSD, or MIT).

/Jorgen
 
S

sebastian

I don't know where you should go for advice. The crypto groups are
out, I guess. How about whoever was involved in Boost::random?

Good idea, I'll look into that...
What license do you have in mind for the code? If this had been two
years ago when I desperately needed a fast, simple, PRNG with a small
non-global state I would have used it -- but only if the license terms
were clear and permissive (like modified BSD, or MIT).

Yep, the MIT license.
 
O

orz

I believe that TestU01 Crush and BigCrush are better than any of the
tests you tried. I also have my own suite of tests that I'm
attempting to clean up for release in the near future.

My computer is currently undergoing surgery, so I can't test the code
myself just yet, but I can offer a few comments based upon my reading
of the code:
A. Any time that scale is even, the top bit of value has no effect
upon the next state. Additional bits of value get discarded when
scale is a multiple of larger powers of 2.
B. The low bits of temp are entirely dependent upon the low bits of
the previous output and the low bits of scale.
C. The low bits of each output are entirely dependent upon the low
bits of temp and the single highest bit of temp and the low bits of
counter.
D. Thus, I would expect that if you used only the bottom few bits of
output, the patterns would become much more apparent. Many real world
programs do use only the low bits of output from their RNGs.

The state size and reported speed appear to place this in the general
category of small fast RNGs. For 3 word RNGs of about that speed, I'm
not aware of any that pass all tests I use (TestU01 Crush, BigCrush,
and my own test suite), so if yours does it will be the first known to
me. I do have a few 4 word RNGs about that speed that pass all tests
(one requires 16+ bit words to pass all tests, the other requires 32+
bit words to pass all tests). But I'd expect that RNG to fail tests.
 
O

orz

My main computer is (temporarily) working again, I just tested the
code you posted above.

And, so far as I can tell, you posted the wrong code. The output from
that code, cut and pasted in to my project, doesn't just fail
statistical tests, it fails almost *every* statistical tests. Even on
TestU01 SmallCrush it fails 4 or 5 tests, and likewise my test suite
finds numerous statistical anomalies within the first few seconds.

So either it's somehow sensitive to tiny issues from compiler
differences or something, or you somehow posted the wrong code, or you
incorrectly applied your tests, or something else happened. But the
code as posted should not be used as an RNG.
 
Ad

Advertisements

S

sebastian

My main computer is (temporarily) working again, I just tested the
code you posted above.

And, so far as I can tell, you posted the wrong code.  The output from
that code, cut and pasted in to my project, doesn't just fail
statistical tests, it fails almost *every* statistical tests.  Even on
TestU01 SmallCrush it fails 4 or 5 tests, and likewise my test suite
finds numerous statistical anomalies within the first few seconds.

So either it's somehow sensitive to tiny issues from compiler
differences or something, or you somehow posted the wrong code, or you
incorrectly applied your tests, or something else happened.  But the
code as posted should not be used as an RNG.

Hmm. Are you using an unsigned integral type? Oh, and I tried invoking
the Testu01 executable (tcode.exe) from the command line, but it wrote
nothing to the output file, and the docs didn't give any instructions
for the command line usage, either. Any ideas on how to do that
properly? Anyway, thanks so much for your input. Cheers!
 
O

orz

Hmm. Are you using an unsigned integral type? Oh, and I tried invoking
the Testu01 executable (tcode.exe) from the command line, but it wrote
nothing to the output file, and the docs didn't give any instructions
for the command line usage, either. Any ideas on how to do that
properly? Anyway, thanks so much for your input. Cheers!

I'm instantiating it with:
typedef unsigned int Uint32;//inside some platform detection #ifdefs
garth_random<Uint32> actual;//inside a simple wrapper class that
adapts your code to my interface

and using it with:
return actual();//inside the same wrapper
actual.seed(s);//inside the same wrapper

I cut & pasted all of your code except the preprocessor directives.
If seeded with the decimal value 13, then the first 5 outputs modulo
1000 are:
266, 118, 586, 672, 568
....in that order. Does that match your output?
Your RNG is currently in my list of RNGs as "garth32" (your code
instantiated on 32 bit unsigned integers, plus a wrapper).

For TestU01, I've never tried using the executables it came with.
What I do is link with TestU01 (you're generally intended to link with
it as a .a or .lib file, but I added all its source files to my MSVC
project instead), and then call its test batteries on my RNGs (my RNG
templates atm include an adaptor for compatibility w/ TestU01 RNG
interfaces).

TestU01 SmallCrush output for garth32 essentially said that 5 of 15
tests were failed, and each failure was completely unambiguous, with a
p-value not meaningfully distinguishable from 0. That's better than
libc rand(), but only barely. The exact output was:
========= Summary results of SmallCrush =========

Version: TestU01 1.2.3
Generator: garth32
Number of statistics: 15
Total CPU time: 00:00:09.90
The following tests gave p-values outside [0.001, 0.9990]:
(eps means a value < 1.0e-300):
(eps1 means a value < 1.0e-015):

Test p-value
----------------------------------------------
3 Gap eps
4 SimpPoker eps
5 CouponCollector eps
7 WeightDistrib eps
9 HammingIndep eps
----------------------------------------------
All other tests were passed
 
O

orz

Hmm. Are you using an unsigned integral type? Oh, and I tried invoking
the Testu01 executable (tcode.exe) from the command line, but it wrote
nothing to the output file, and the docs didn't give any instructions
for the command line usage, either. Any ideas on how to do that
properly? Anyway, thanks so much for your input. Cheers!

I'm instantiating it with:
typedef unsigned int Uint32;//inside some platform detection #ifdefs
garth_random<Uint32> actual;//inside a simple wrapper class that
adapts your code to my interface

and using it with:
return actual();//inside the same wrapper
actual.seed(s);//inside the same wrapper

I cut & pasted all of your code except the preprocessor directives.
If seeded with the decimal value 13, then the first 5 outputs modulo
1000 are:
266, 118, 586, 672, 568
....in that order. Does that match your output?
Your RNG is currently in my list of RNGs as "garth32" (your code
instantiated on 32 bit unsigned integers, plus a wrapper).

For TestU01, I've never tried using the executables it came with.
What I do is link with TestU01 (you're generally intended to link with
it as a .a or .lib file, but I added all its source files to my MSVC
project instead), and then call its test batteries on my RNGs (my RNG
templates atm include an adaptor for compatibility w/ TestU01 RNG
interfaces).

TestU01 SmallCrush output for garth32 essentially said that 5 of 15
tests were failed, and each failure was completely unambiguous, with a
p-value not meaningfully distinguishable from 0. That's better than
libc rand(), but only barely. The exact output was:
========= Summary results of SmallCrush =========

Version: TestU01 1.2.3
Generator: garth32
Number of statistics: 15
Total CPU time: 00:00:09.90
The following tests gave p-values outside [0.001, 0.9990]:
(eps means a value < 1.0e-300):
(eps1 means a value < 1.0e-015):

Test p-value
----------------------------------------------
3 Gap eps
4 SimpPoker eps
5 CouponCollector eps
7 WeightDistrib eps
9 HammingIndep eps
----------------------------------------------
All other tests were passed
 
O

orz

Hmm. Are you using an unsigned integral type? Oh, and I tried invoking
the Testu01 executable (tcode.exe) from the command line, but it wrote
nothing to the output file, and the docs didn't give any instructions
for the command line usage, either. Any ideas on how to do that
properly? Anyway, thanks so much for your input. Cheers!

I'm instantiating it with:
typedef unsigned int Uint32;//inside some platform detection #ifdefs
garth_random<Uint32> actual;//inside a simple wrapper class that
adapts your code to my interface

and using it with:
return actual();//inside the same wrapper
actual.seed(s);//inside the same wrapper

I cut & pasted all of your code except the preprocessor directives.
If seeded with the decimal value 13, then the first 5 outputs modulo
1000 are:
266, 118, 586, 672, 568
....in that order. Does that match your output?
Your RNG is currently in my list of RNGs as "garth32" (your code
instantiated on 32 bit unsigned integers, plus a wrapper).

For TestU01, I've never tried using the executables it came with.
What I do is link with TestU01 (you're generally intended to link with
it as a .a or .lib file, but I added all its source files to my MSVC
project instead), and then call its test batteries on my RNGs (my RNG
templates atm include an adaptor for compatibility w/ TestU01 RNG
interfaces).

TestU01 SmallCrush output for garth32 essentially said that 5 of 15
tests were failed, and each failure was completely unambiguous, with a
p-value not meaningfully distinguishable from 0. That's better than
libc rand(), but only barely. The exact output was:
========= Summary results of SmallCrush =========

Version: TestU01 1.2.3
Generator: garth32
Number of statistics: 15
Total CPU time: 00:00:09.90
The following tests gave p-values outside [0.001, 0.9990]:
(eps means a value < 1.0e-300):
(eps1 means a value < 1.0e-015):

Test p-value
----------------------------------------------
3 Gap eps
4 SimpPoker eps
5 CouponCollector eps
7 WeightDistrib eps
9 HammingIndep eps
----------------------------------------------
All other tests were passed
 
J

Jorgen Grahn

.
D. Thus, I would expect that if you used only the bottom few bits of
output, the patterns would become much more apparent. Many real world
programs do use only the low bits of output from their RNGs.

Yes. There are mixed opinions on the wisdom of that -- there have been
heated discussions about it here in the past. To use myself as an
example, I happily do rand() % N, and call implementations old and
broken if this gives bad results. At least Linux and the BSDs are
documented to have PRNG where this is ok.

/Jorgen
 
Ad

Advertisements

O

orz

On Wed, 2010-06-23, orz wrote:

...


Yes. There are mixed opinions on the wisdom of that -- there have been
heated discussions about it here in the past.  To use myself as an
example, I happily do rand() % N, and call implementations old and
broken if this gives bad results. At least Linux and the BSDs are
documented to have PRNG where this is ok.

/Jorgen

Jorgen Grahn:
I think the answer is pretty clear. Any detectable failure of any
bits of output is a major flaw. Using % on an RNG output is never
optimal (though it can be convenient), but it's far from the only way
that the low bits of an RNGs output might be emphasized. Those people
who chose libc / platform RNGs have historically (and to present day
so far as I know) consistently picked bad to mediocre RNGs.

Sebastion:
Assuming that the algorithm I'm working with correctly represents the
one you're working with, possible changes to consider are:
A. Simply forcing scale to always be an odd number fixes the issue
where the top bits of value get thrown away. That change alone
results in an enormous improvement in the RNGs quality.
B. The "( temp << one ) | ( ( temp & msb ) ? one : zero ) )" is an
obfuscated 1 bit barrel shift. Replacing it with a non-obfuscated
barrel shift is less confusing, and makes it possible to add the
amount of the shift as another template parameter. Although...
empirical testing suggests that 1 may be the ideal amount of barrel
shift there, assuming no other details of the algorithm were
changed.
C. The "^ mask" is equivalent to a bitwise not. And since it's done
on a result of an xor anyway, it's equivalent to applying the bitwise
not to one of the terms of the xor. And since one of the terms of the
xor is a simple counter, that's pretty much equivalent to not applying
the bitwise-not at all, and simply decrementing counter instead of
incrementing it.
 
O

orz

On Wed, 2010-06-23, orz wrote:

...


Yes. There are mixed opinions on the wisdom of that -- there have been
heated discussions about it here in the past.  To use myself as an
example, I happily do rand() % N, and call implementations old and
broken if this gives bad results. At least Linux and the BSDs are
documented to have PRNG where this is ok.

/Jorgen

Jorgen:
I think the answer is pretty clear. Any detectable failure of any
bits of output is a major flaw. Using % on an RNG output is never
optimal (though it can be convenient), but it's far from the only way
that the low bits of an RNGs output might be emphasized. Those people
who chose libc / platform RNGs have historically (and to present day
so far as I know) consistently picked bad to mediocre RNGs.

Sebastion:
Assuming that the algorithm I'm working with correctly represents the
one you're working with, possible changes to consider are:
A. Simply forcing scale to always be an odd number fixes the issue
where the top bits of value get thrown away. That change alone
results in an enormous improvement in the RNGs quality.
B. The "( temp << one ) | ( ( temp & msb ) ? one : zero ) )" is an
obfuscated 1 bit barrel shift. Replacing it with a non-obfuscated
barrel shift is less confusing, and makes it possible to add the
amount of the shift as another template parameter. Although...
empirical testing suggests that 1 may be the ideal amount of barrel
shift there, assuming no other details of the algorithm were
changed.
C. The "^ mask" is equivalent to a bitwise not. And since it's done
on a result of an xor anyway, it's equivalent to applying the bitwise
not to one of the terms of the xor. And since one of the terms of the
xor is a simple counter, that's pretty much equivalent to not applying
the bitwise-not at all, and simply decrementing counter instead of
incrementing it.
 
O

orz

On Wed, 2010-06-23, orz wrote:

...


Yes. There are mixed opinions on the wisdom of that -- there have been
heated discussions about it here in the past.  To use myself as an
example, I happily do rand() % N, and call implementations old and
broken if this gives bad results. At least Linux and the BSDs are
documented to have PRNG where this is ok.

/Jorgen

Jorgen:
I think the answer is pretty clear. Any detectable failure of any
bits of output is a major flaw. Using % on an RNG output is never
optimal (though it can be convenient), but it's far from the only way
that the low bits of an RNGs output might be emphasized. Those people
who chose libc / platform RNGs have historically (and to present day
so far as I know) consistently picked bad to mediocre RNGs.

Sebastion:
Assuming that the algorithm I'm working with correctly represents the
one you're working with, possible changes to consider are:
A. Simply forcing scale to always be an odd number fixes the issue
where the top bits of value get thrown away. That change alone
results in an enormous improvement in the RNGs quality.
B. The "( temp << one ) | ( ( temp & msb ) ? one : zero ) )" is an
obfuscated 1 bit barrel shift. Replacing it with a non-obfuscated
barrel shift is less confusing, and makes it possible to add the
amount of the shift as another template parameter. Although...
empirical testing suggests that 1 may be the ideal amount of barrel
shift there, assuming no other details of the algorithm were
changed.
C. The "^ mask" is equivalent to a bitwise not. And since it's done
on a result of an xor anyway, it's equivalent to applying the bitwise
not to one of the terms of the xor. And since one of the terms of the
xor is a simple counter, that's pretty much equivalent to not applying
the bitwise-not at all, and simply decrementing counter instead of
incrementing it.
 
O

orz

On Wed, 2010-06-23, orz wrote:

...


Yes. There are mixed opinions on the wisdom of that -- there have been
heated discussions about it here in the past. To use myself as an
example, I happily do rand() % N, and call implementations old and
broken if this gives bad results. At least Linux and the BSDs are
documented to have PRNG where this is ok.

/Jorgen

Jorgen:
I think the answer is pretty clear. Any detectable failure of any
bits of output is a major flaw. Using % on an RNG output is never
optimal (though it can be convenient), but it's far from the only way
that the low bits of an RNGs output might be emphasized. Those people
who chose libc / platform RNGs have historically (and to present day
so far as I know) consistently picked bad to mediocre RNGs.

Sebastion:
Assuming that the algorithm I'm working with correctly represents the
one you're working with, possible changes to consider are:
A. Simply forcing scale to always be an odd number fixes the issue
where the top bits of value get thrown away. That change alone
results in an enormous improvement in the RNGs quality.
B. The "( temp << one ) | ( ( temp & msb ) ? one : zero ) )" is an
obfuscated 1 bit barrel shift. Replacing it with a non-obfuscated
barrel shift is less confusing, and makes it possible to add the
amount of the shift as another template parameter. Although...
empirical testing suggests that 1 may be the ideal amount of barrel
shift there, assuming no other details of the algorithm were
changed.
C. The "^ mask" is equivalent to a bitwise not. And since it's done
on a result of an xor anyway, it's equivalent to applying the bitwise
not to one of the terms of the xor. And since one of the terms of the
xor is a simple counter, that's pretty much equivalent to not applying
the bitwise-not at all, and simply decrementing counter instead of
incrementing it.
 
O

orz

On Wed, 2010-06-23, orz wrote:

...


Yes. There are mixed opinions on the wisdom of that -- there have been
heated discussions about it here in the past. To use myself as an
example, I happily do rand() % N, and call implementations old and
broken if this gives bad results. At least Linux and the BSDs are
documented to have PRNG where this is ok.

/Jorgen

Jorgen:
I think the answer is pretty clear. Any detectable failure of any
bits of output is a major flaw. Using % on an RNG output is never
optimal (though it can be convenient), but it's far from the only way
that the low bits of an RNGs output might be emphasized. Those people
who chose libc / platform RNGs have historically (and to present day
so far as I know) consistently picked bad to mediocre RNGs.

Sebastion:
Assuming that the algorithm I'm working with correctly represents the
one you're working with, possible changes to consider are:
A. Simply forcing scale to always be an odd number fixes the issue
where the top bits of value get thrown away. That change alone
results in an enormous improvement in the RNGs quality.
B. The shiftleft-then-bitwise-or-a-trinary-operator is an obfuscated
1 bit barrel shift. Replacing it with a non-obfuscated barrel shift
is less confusing, and makes it possible to add the amount of the
shift as another template parameter. Although... empirical testing
suggests that 1 may be the ideal amount of barrel shift there,
assuming no other details of the algorithm were changed.
C. The xor by mask is equivalent to a bitwise not. And since it's
done on a result of an xor anyway, it's equivalent to applying the
bitwise not to one of the terms of the xor. And since one of the
terms of the xor is a simple counter, that's pretty much equivalent to
not applying the bitwise-not at all, and simply decrementing counter
instead of incrementing it.
 
Ad

Advertisements

O

orz

Jorgen:
I think the answer is pretty clear. Any detectable failure of any
bits of output is a major flaw. Using % on an RNG output is never
optimal (though it can be convenient), but it's far from the only way
that the low bits of an RNGs output might be emphasized. Those people
who chose libc / platform RNGs have historically (and to present day
so far as I know) consistently picked bad to mediocre RNGs.

Sebastion:
Assuming that the algorithm I'm working with correctly represents the
one you're working with, possible changes to consider are:
A. Simply forcing scale to always be an odd number fixes the issue
where the top bits of value get thrown away. That change alone
results in an enormous improvement in the RNGs quality.
B. The shiftleft-then-bitwise-or-a-trinary-operator is an obfuscated
1 bit barrel shift. Replacing it with a non-obfuscated barrel shift
is less confusing, and makes it possible to add the amount of the
shift as another template parameter. Although... empirical testing
suggests that 1 may be the ideal amount of barrel shift there,
assuming no other details of the algorithm were changed.
C. The xor by mask is equivalent to a bitwise not. And since it's
done on a result of an xor anyway, it's equivalent to applying the
bitwise not to one of the terms of the xor. And since one of the
terms of the xor is a simple counter, that's pretty much equivalent to
not applying the bitwise-not at all, and simply decrementing counter
instead of incrementing it.
 
O

orz

Jorgen
I think the answer is pretty clear. Any detectable failure of any
bits of output is a major flaw. Using % on an RNG output is never
optimal (though it can be convenient), but it's far from the only way
that the low bits of an RNGs output might be emphasized. Those people
who chose libc or other platform RNGs have historically (and to
present day so far as I know) consistently picked bad to mediocre
RNGs.

Sebastion
Assuming that the algorithm I'm working with correctly represents the
one you're working with, possible changes to consider are:
A. Simply forcing scale to always be an odd number fixes the issue
where the top bits of value get thrown away. That change alone
results in an enormous improvement in the RNGs quality.
B. The leftshift then bitwise or a trinary operator on the most
significant bit thing. It's an obfuscated 1 bit barrel shift.
Replacing it with a non-obfuscated barrel shift seems more
straightforward, and makes it possible to add the amount of the shift
as another template parameter. Although... empirical testing suggests
that 1 may be the ideal amount of barrel shift there, assuming no
other details of the algorithm were changed.
C. The xor by mask is equivalent to a bitwise not. And since it's
done on a result of an xor anyway, it's equivalent to applying the
bitwise not to one of the terms of the xor. And since one of the
terms of the xor is a simple counter, that's pretty much equivalent to
not applying the bitwise-not at all, and simply decrementing counter
instead of incrementing it.
 
Ad

Advertisements

O

orz

Jorgen
I think the answer is pretty clear. Any detectable failure of any
bits of output is a major flaw. Using % on an RNG output is never
optimal (though it can be convenient), but it's far from the only way
that the low bits of an RNGs output might be emphasized. Those people
who chose libc or platform RNGs have historically (and to present day
so far as I know) consistently picked bad to mediocre RNGs.

Sebastion
Assuming that the algorithm I'm working with correctly represents the
one you're working with, possible changes to consider are:
A. Simply forcing scale to always be an odd number fixes the issue
where the top bits of value get thrown away. That change alone
results in an enormous improvement in the RNGs quality.
B. The leftshift then bitwise or a trinary operator on the most
significant bit thing. It's an obfuscated 1 bit barrel shift.
Replacing it with a non-obfuscated barrel shift seems more
straightforward, and makes it possible to add the amount of the shift
as another template parameter. Although... empirical testing suggests
that 1 may be the ideal amount of barrel shift there, assuming no
other details of the algorithm were changed.
C. The xor by mask is equivalent to a bitwise not operation. And
since it's done on a result of an xor anyway, it's equivalent to
applying the bitwise not to one of the terms of the xor. And since
one of the terms of the xor is a simple counter, that's pretty much
equivalent to not applying the bitwise not operation at all, and
simply decrementing counter instead of incrementing it.
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top