Randomness is too important to be left to chance.
BabyNous
there was a tread awhile ago on randomness, along with an address for a www
site that was supposed to feature a 'litimus' test for randomality...
but unfortunately, i either couldn't find the list of tests that were supposed
to be there, or i couldn't figure it out, or i think that they might have
listed source code for assemblers that i didn't have...
what i think might be fun...
would be if some smart person were to post a list of theoretical approaches or
actual 48 programs to test the randomality of a given psuedorandom generator...
like:
a graphical test...???
i've written little do-dad programs before using the 48 random generator and
been struck by the 'orderliness' of the patterns that emerge...!!!
sometimes, the patterns are strikingly orderly...!!!
so something like that, only with more rigour...???
eh?
John H Meyers
In article <34CC9EB7...@echip.com>,
Bob Wheeler <bwhe...@echip.com> writes:
> Let a = 7 and m =10, starting with X(1) = 3 one has
> 3, 1, 7, 9, 3, 1, 7, 9, 3, 1, 7, 9, 3, etc,
> This is not as well mixed, in fact all values are odd,
> and every fourth iterate repeats.
Right, the maximal possible period of 1E15 was reduced to 5E13
(i.e. by a factor of 20) by not using an additive constant,
but it still has about 3 more internal state digits than
the number of digits actually output each time,
so this is affordable, is it not?
[More later about the impossibility of the state being
divisible by 2 or by 5]
As we keep saying, the *remainders* MOD 1E-15 repeat, while the
complete real number output by RAND repeats its whole cycle only
every 5E13 outputs (long enough to put you to sleep for fifteen
centuries, if you count one random sheep per millisecond :)
The HP48 RAND is not for making integers, nor for separating its output
values into separate digits; RAND is for delivering real numbers
between zero and one, one real number per invocation of RAND,
which is then for mapping to any other desired interval by
multiplication. To get a series of random *bits* using RAND,
the use of RAND 2 * CEIL 1 - (once per *bit*) would be the best
we could do using RAND; short-cuts like multiplying by 256 to
obtain one byte (8 bits) at a time might not be quite as good,
for reasons hinted at below; for some purposes,
the results are still good enough, anyway.
The above will still not do everything one might ever like; e.g.
any generator having fewer than the equivalent of N bits of
internal state could not possibly ever output every possible
binary sequence of N bits; this will be true of any other
kind of generator as well, not only the simple LCRNG type.
Solving for the current state, given somewhat in excess of
N consecutive bits of known output, is more readily done
from simpler generators (such as LCRNG) than with more
clever ones; this factor is crucial for cryptography and
casino machines, but less so for less demanding simulations.
To get a sequence of random *decimal* digits using RAND,
RAND 10 * IP (once per digit) is feasible, or perhaps
RAND DUP 2 * CEIL 1 - 5 * SWAP 5 * CEIL 1 - 6 * + 10 MOD
The latter approach uses the "Chinese Remainder Theorem"
(determines a number uniquely from its remainders, modulo its
relatively prime factors, all repeating factors having been removed).
It appears that the latter method is ultimately better, I think;
for example, for N = 1E12, you would take 12 different remainders
mod 2 (e.g. RAND 2 * CEIL 1 - ) and the same twelve RAND's mod 5,
to get remainders mod 2^12 and 5^12, from which the final
value mod 10^12 would be determined. If I'm not mistaken,
this might remove even the "cycle of 50,000" from the
last three digits. What do you think about this, Bob?
This will not repeat in any simple pattern at all,
since it has a period of 5E13 before the complete cycle repeats.
Once again, any generator having fewer than N decimal digits of internal
state can not ever output every possible sequence of N decimal digits,
whether it is an LCRNG or any other kind; in fact, the HP48 RNG has
the equivalent of about 13.5 decimal digits of internal state,
because the very last three digits of the internal 15-digit state
are constrained to fewer than all possible values, as Bob noted.
As you move leftward, however, the twelve leading digits will in fact
assume every one of the 10^12 possible values, equally often, for whatever
that's worth; in fact the first 12 digits following the decimal point
is usually all you ever get as an output. It's perfectly true that
the twelfth digit will go through its full cycle in only 500
consecutive outputs. However, you will never see the "every four
outputs" repetition that Bob mentions, because it is a repetition of
a digit within the *internal*state*, not within the output you get
as a real number. Even the repetition you do see (the tenth
thru twelfth digits repeating their cycle every 50000 outputs,
for example) does not mean that any values you get by multiplying
RAND outputs by small integers will contain any such patterns;
if you use RAND to obtain sequences of integers via RAND N * CEIL,
then patterns like that do not appear unless N is very large;
I suggest that the effect is somewhat proportional to log N, in fact.
If you have a large composite N, you can break it into factors,
handle repeating factors as we did above in the case of powers of 2,
and apply the Chinese Remainder Theorem to the rest
(determine a value uniquely from its set of remainders,
modulo various relatively prime factors); will this help?
> The reason for this behavior is due to the choice of m = 10 = 2*5.
> The sequence must repeat every k-1 iterates if k is a divisor of m,
> thus it repeats (mod 2) and (mod 5).
What is it that repeats? The ( *internal*state*integer* mod 2or5 ),
which you can not even see in the output of RAND. If you use the
output values of RAND, one whole output value at a time, as a
real number (fraction) somewhere between 0 and 1, where does
the effect of potential repetition, even of hidden digits that
were lopped off at the end, begin to affect the results of
what you actually do with those decimal fractions, which in turn
contain 12 or more significant digits each?
To try another angle on you, let me propose that you give me
your most ideal 12-digit decimal RAND substitute. Suppose I
tack onto the end of every one of these decimal real numbers
the digits 000, creating 15-digit mantissas (e.g. "long real" in HP48).
Now, look what I've done -- why, every one of my 15-digit mantissas is
now exactly divisible by 2, by 4, by 5, by 8, by 10, by 20, by 25, etc.
Have I now destroyed the "randomness" of the 12-digit real values you
gave me, just by converting them to "long real," but without actually
changing any of their values at all? This is surely the worst imaginable
repetition of [identical] trailing digits, is it not? However, if the
digits to their left are non-repetitive and better distributed, do
any appended trailing digits worsen the distribution of real
number fractions on (0,1) with which you originally provided me?
If you insist on wanting to be able to consider every digit generated
by RAND as an independent random variable, then you need to change the
modulus away from 10^N, as you say; at the very same time, you'll also
be changing the real number output range a little bit away from
corresponding exactly with the interval (0,1), will you not?
So, how do you "catch both fish with just one hook" ?
Okay, you can use an essentially different kind of generator,
if you like, but it will have to take a long leap to grow from
being useful for everyday small-scale statistical simulation
to heavy-duty cryptography or extremely demanding statistical
discrimination, no? To be able to output longer and longer
sequences of bits or digits which could range over all possible
values, it would take a correspondingly longer and longer amount
of internal state, would it not, and "you have to stop sometime."
There could also be a complete open-endedness, with, say, the
use of RC4 (cryptosystem) as an RNG, with the user able to supply
as long a "key" as (s)he wishes -- thousands of bytes, perhaps :)
OTOH, as limited and simplistic thing as an LCRNG, with a hefty
extra portion of internal state length over returned output length
(as the HP48 just begins to have) is not the worst thing that a
manufacturer of "just a calculator" might elect to do; after all,
"life is short, and ROM is full" (Bill Wickes).
> Even worse, if X(1) = 2 or X(1) = 5 ...
> I guess it is OK to use RAND for a few values, always being careful
> to start with a seed that cannot be divided by 2 or 5.
Help is on the way from HP; if you retrieve the posts which go into
extreme detail about how a user argument is turned into a seed by
the RDZ command (the only user command which sets a starting seed),
you will find that (for x > 1 anyway) the 12 significant digits of
the mantissa and last two digits of the exponent determine the first
14 digits of the internal state; the final digit is *always*
set to 1, which I believe takes care of your caution.
We also had to caution about 0 RDZ (clock randomizer), which shrunk
the approximately 1E14 user-settable initial states down to just
2^20 clock-settable states; Steve VanDevender then showed how
to get around that shrinkage by computing a better argument
for RDZ from the current TICKS value.
What is "a few" values? What percent of the total cycle would be
few enough? how about the square root of the total cycle?
(that would be still 7E7 outputs, good enough for my everyday use).
> The upshot of this is that there are lots and lots of patterns in the
> RAND output. If the output is taken (mod k) where k is a product of
> powers of 2 and 5, then the output sequences will repeat (mod k).
The "output" is not and has never been an integer; it is and has
always been a decimal fraction, with a decimal point in front of
the very first digit. It represents a point in space between
zero and one on the real number line. To map this into other ranges,
you multiply this by the length of the range it is to be mapped into.
This fraction does not repeat until after 5E13 outputs. The tenth
thru twelfth digit following the decimal point do repeat after only
50,000 outputs, etc., in case this begins to cause concern.
I agree that there are "patterns," but not quite as overt as the
above dire descriptions make them seem. One pattern is caused
by the graininess of any digital representation, in any given number
base, to a finite number of digits; the number base itself introduces
a pattern (2^N has factors as well, including 2; doesn't Knuth say that
there exist *more* suitable LCRNG multipliers when the modulus *does*
have many factors?) When simple LCRNG output is multiplied by larger
integers to produce integer results, it produces regularity "sooner"
than some other RNG's might.
Another "defect" is its solvability from known outputs; this is
important for cryptography and the like -- but did HP fail us
by not considering such esoteric applications for its HP48?
After all, users can always readily write their own substitute for
anything they want, to extend the basic scientific instrument,
as they have well done thus far.
> Such patterns can foul up statistical studies which assume independence,
> since the sequences used for different test conditions may be
> linear shifts of each other.
Every sequence of the HP15C type of LCRNG was a linear shift, since
there was only one "ring" of outputs, but it's a long ring :)
The HP48 may have two (or more) possible rings, I believe, thanks to
its very same "non-maximal-sequence" nature.
> There is no need to say more on this subject.
"See Knuth for more," I guess :)
> You now have the gist of the problem, and a feel for RAND's deficiencies.
Perhaps also a feel for how to use it properly, so that
deficiencies are not created out of simple misuse.
> in case you want a generator that does not suffer from any such defects,
> you can use:
%%HP: T(3); @ [re-formatted, but not altered, I think]
\<< seed\Gd #65535d AND #36969d * seed\Gd SRB SRB SRB SRB + 'seed\Gd' STO
seed\Gd #65535d AND \>>
I hope I didn't mess up what you posted; it doesn't work so well for me.
Starting with #0 as input, every output is zero. Starting with odd
output, every output is odd, etc.
I know that you can change something to fix this (or use what
you posted last time, having modulus 2^31-1), but in any event,
does this essentially binary integer generator easily translate
into a decimal generator of fractions between 0 and 1 ?
How many possible output values are there?
How many internal state bits?
How about a Lecuyer generator instead (in decimal?)
[Ok, I looked at your voluminous erudite posts on all sorts of
subjects, but I can hardly even focus on them, even tilted backwards :]
"And so it goes"
-----------------------------------------------------------
With best wishes from: John H Meyers <jhme...@mum.edu>
Bob Wheeler
Let's take this private. I'm sure most members of the group are not interested.
On second thought, I suggest the following functions. The first produces
integers, and the second floating point numbers. Their periods are 2^63 -1. The
floating point output has about 9 and a half significant digits. Generators with
more significant digits can be obtained, but they will be considerably slower --
it doesn't seem worth it for a few trailing digits. Any positive integer may be
used as a starting seed which is stored in the variable "seed\Gd".
%%HP: T(3)A(D)F(.);
\<< seed\Gd
# 4294967295d AND
# 268434834d *
seed\Gd SRB SRB SRB
SRB + 'seed\Gd' STO
seed\Gd # 4294967295d
AND
\>>
%%HP: T(3)A(D)F(.);
\<< seed\Gd
# 4294967295d AND
# 268434834d *
seed\Gd SRB SRB SRB
SRB + 'seed\Gd' STO
seed\Gd # 4294967295d
AND B\->R 2 -32 ^ *
\>>
John H Meyers wrote:
> In article <34CC9EB7...@echip.com>,
> Bob Wheeler <bwhe...@echip.com> writes:
>
> > Let a = 7 and m =10, starting with X(1) = 3 one has
> > 3, 1, 7, 9, 3, 1, 7, 9, 3, 1, 7, 9, 3, etc,
> > This is not as well mixed, in fact all values are odd,
> > and every fourth iterate repeats.
>
<snip>
> "And so it goes"
>
> -----------------------------------------------------------
> With best wishes from: John H Meyers <jhme...@mum.edu>
--
Bob Wheeler --- (Reply to: bwhe...@echip.com)
ECHIP, Inc.
Jonathan M. Katz
Bob Wheeler wrote:
>
> Let's take this private. I'm sure most members of the group are not interested.
I like reading this discussion. I find it very informative. Do what
you wish, but I don't mind the long posts at all. Not that I have
anything to add, since (up to now) I don't know much about the RNG.
One question of a very "grammatical" nature:
I thought the HP15C and 48 RNG's produced real values in the interval
[0,1) (i.e. 0 <= x < 1). From all of my mathematics courses, (0,1) is
suggestive of the interval 0 < x < 1, which is not the same (nor quite
as desireable, AFAIK). I'm probably being picky, yes? :)
[katz)
--
In order to e-mail me a reply to this message, you will have
to edit the address shown in the header. You know what to do.
Bob Wheeler
Jonathan M. Katz wrote:
> Bob Wheeler wrote:
> >
> > Let's take this private. I'm sure most members of the group are not interested.
>
> I like reading this discussion. I find it very informative. Do what
> you wish, but I don't mind the long posts at all. Not that I have
> anything to add, since (up to now) I don't know much about the RNG.
If we come to agreement someday, it may be worth posting.
>
>
> One question of a very "grammatical" nature:
>
> I thought the HP15C and 48 RNG's produced real values in the interval
> [0,1) (i.e. 0 <= x < 1). From all of my mathematics courses, (0,1) is
> suggestive of the interval 0 < x < 1, which is not the same (nor quite
> as desireable, AFAIK). I'm probably being picky, yes? :)
The interval is (0,1]. Zero is excluded by the generators discussed. Both 0 and 1
are valid probabilities however. A probability of 1 measures a sure event; however,
events of probability zero can occur. In fact randomly selecting a single point in an
interval has probability zero. Probability on the real line or the complex plane is
a set concept, and only certain dense sets are assigned probabilities. You will
learn more than you want about this if you take a measure theory course.
>
>
> [katz)
> --
> In order to e-mail me a reply to this message, you will have
> to edit the address shown in the header. You know what to do.
--
Bob Wheeler --- (Reply to: bwhe...@echip.com)
ECHIP, Inc. --- (302) 239-6620, voice and FAX
724 Yorklyn Rd., Hockessin, DE 19707
Randomness comes in bunches
Jonathan M. Katz
Bob Wheeler wrote:
> [snip]
> The interval is (0,1]. Zero is excluded by the generators discussed. Both 0 and 1
> are valid probabilities however. A probability of 1 measures a sure event; however,
> events of probability zero can occur. In fact randomly selecting a single point in an
> interval has probability zero. Probability on the real line or the complex plane is
> a set concept, and only certain dense sets are assigned probabilities. You will
> learn more than you want about this if you take a measure theory course.
I've taken plenty of engineering statistics classes, certainly enough to
understand the concepts of general probability and random variables. The
issue of a "zero probability event" versus a "unity probability event"
is no mystery to me, and it wasn't the focus of my question. I'll cut to
the quick and cite the user manuals of my 15C and my 48SX:
15C, page 48: "Pressing [f] [RAN#] (random number) will generate a
random
number (part of a uniformly distributed pseudo-random number sequence)
in
the range 0 <= r < 1."
48SX, page 147: {Table Entry} RAND | Returns the next real number
n
(0 <= n < 1) in a psuedo-random number sequence. Each random number
becomes
the seed for the next random number."
So, from these two descriptions (which could possibly be inexact or mis-
printed), it appears that the interval is indeed [0,1), at least in
theory.
I have never seen either RNG return a full-precision value of "exactly"
zero. I think my memory is correct when I use the "[" to indicate a
closed
point and the ")" to indicate an open point of a real-valued interval.
Of
course, I've been wrong before, and it's a distinct possibility in this
case.
katz
John H Meyers
In article <6al2pv$c...@bgtnsc03.worldnet.att.net>,
Jonathan M. Katz <27-z...@worldnet.att.net> writes:
> I thought the HP15C and 48 RNG's produced real values in the interval
> [0,1) (i.e. 0 <= x < 1). From all of my mathematics courses, (0,1) is
> suggestive of the interval 0 < x < 1, which is not the same (nor quite
> as desireable, AFAIK). I'm probably being picky, yes? :)
Theory aside, turning to what the calc's actually do, the HP15C
generates values consisting of up to ten fixed digits following
a decimal point; it uses an LCRNG with a modulus of 10^10 which
really does produce a sequence of length 10^10, covering every
possible set of ten digits following the decimal point (with all
ten internal state digits being visible at any time via RCL RAND#),
from .0000000000 (exactly zero) through .9999999999 [ten nines],
the highest it can go; somewhere I may have the "reverse" constants
written down, which will produce the sequence in reverse order,
which will enable you to figure out a seed which will produce
any desired .xxxxxxxxxx as the next output value. If you have
the built-in constants at hand, it's easy enough to figure
out the reverse constants anyway. If you store the seed
.0000000000 and get the next RAND# value, it is the
built-in additive constant; if you then store .0000000001
and get the next value, then subtract the additive constant,
you now have the 10-digit multiplier, the inverting of which
is an easy exercise (post the values if you want help).
Purists may note that the *exact* mean of *all* possible output
values for HP15C RAND# is .49999999995, rather than .5;
that's the breaks of digital quantization :)
The HP48, as has been discussed more thoroughly, also "wakes up"
after a memory reset (ON+A+F) with its internal "seed" zeroed out;
however, it has a "one time only" trap to detect this, so that
if you have not yourself performed any RDZ (setting a seed)
before the very first time you ever use RAND after a memory reset,
then a default initial seed is set for you. The HP48 uses an
additive constant of zero (i.e. it only does multiplication),
so an initial seed of zero would not have been a good thing;
RDZ also precludes inappropriate seeds (divisible by 2 or 5) by
forcing the 15th internal state digit digit to be a "1", after obtaining
the leading 14 digits from all or part of your argument to RDZ
(for profusely illustrated details, see "Random thoughts on
HP48 random functions", posted on 1997/05/28).
If the first internal state digit is non-zero after each computation,
then only the first twelve state digits fit into a standard floating-
point mantissa (real number), and the trailing three digits of internal
state are not even seen (BTW, there is *no* rounding of any sort;
excess "state" digits are merely dropped, even if they are "999"),
resulting in a maximum output value of .999999999999 [twelve nines].
If one, two, or three leading "state" digits
happen to be zero, then as many more of the trailing state digits
are picked up and stuffed into the normalized floating mantissa,
the "bottom line" of all this being that since the resulting internal
state, produced by multiplying two odd integers modulo 10^15,
can never be all zeros, then the value returned can also never be
exactly zero; in fact, the minimum possible return value is 1E-15.
This may philosophically correspond more with quantum physics,
where even the "vacuum state" has a bit of energy in its ledger,
like the contestants on Groucho Marx' historic "You Bet Your Life"
quiz show, who never walked away without winning some money
for correctly answering such "consolation" questions as
"What color is orange juice?" or "Who was buried in Grant's Tomb?"
Joseph K. Horn
Bob Wheeler wrote:
> Even worse, if X(1) is k as just defined, then all elements of the
> original (mod 10^15) series will be divisible by k.
Joey jumps up and down excitedly. "But Roo-man, what if you take a
*real* list of random numbers, generated by some random physical
process, and multiply them all by 10? Now they all end in 0, so
by your criterion they're no longer random! But they are clearly
exactly as random as they were originally! Huh, Roo-man? Huh?
Huh?"
Roo-man, attempting to understand one of Knuth's proofs, does not
hear Joey.
"And furthermore," Joey continues undaunted, "consider random coin
tosses. Let's call a PENNY landing heads-up a ONE and tails-up a
ZERO. We could generate a random sequence of ONEs and ZEROs by
flipping pennies, yes? But if you flip a DIME, you get a TEN or a
ZERO, so it's *impossible* to flip a dime randomly!!! Huh? Huh?"
Roo-man increases the volume on his Walkman and continues reading.
> I guess it is OK to use RAND for a few values, always being careful to
> start with a seed that cannot be divided by 2 or 5.
"But Roo-man, it's *impossible* to start with a seed divisible by 2 or
5! The RDZ command takes care of this internally! Part of its code is:
A=B X
ASL X
A=A+1 A
This in effect makes the last digit of the seed to be a "1"! No need
to worry, especially if you stop considering RAND's output to be an
integer! It was never intended to be used as an integer, but to be
multipled by a scalar to produce integers within some desired range!
When used *this* way, RAND is statistically sufficiently random!"
Roo-man flips a dime into the air. It vanishes without a trace.
"You could be right, Joey."
-Joe-
joe...@usa.net
-------------------==== Posted via Deja News ====-----------------------
http://www.dejanews.com/ Search, Read, Post to Usenet
Steve VanDevender
The biggest problem with making a cryptographic random number
generator is actually the problem of coming up with enough random
state information to seed the generator properly; the actual
algorithms for cryptographic random number generation are
relatively simple by comparison. In an HP 48 there is very
little truly random and unpredictable information. For example,
TICKS changes by only 13 bits per second; knowing even the
approximate time that a random number generator was seeded using
TICKS alone makes it fairly easy to do a brute-force search to
replicate the random sequence generated. If you've ever used
PGP, you might note that when generating a new key pair, it asks
you to type for some amount of time; what it's doing is precisely
timing the interval between keystrokes, and using the natural
random variations in timing to obtain additional "entropy".
By "cryptographic random number generation" I mean a random
number generator whose successive outputs are not feasibly
predictable, even by someone who knows the algorithm in use.
This is a very specialized application.
Calling the HP 48 RAND function "not random enough" is really not
fair, when the primary use of random number generation in most
mathematical applications is for statistical purposes. In such a
case a simpler algorithm that is easily provable to have the
right statistical properties (uniform distribution, sufficient
period, etc.) is preferable.
--
Steve VanDevender "I ride the big iron" http://jcomm.uoregon.edu/~stevev
ste...@efn.org PGP key fingerprint=929FB79734DF8CC0 210DA447510FF93B
"bash awk grep perl sed df du, du-du du-du,
vi troff su fsck rm * halt LART LART LART!" -- the Swedish BOFH
Steve VanDevender
Examination of the algorithm used in RAND (previously posted, or
easily deduced by disassembling the calculator ROM) shows that it
really cannot produce a value of exactly 0, so it is more
accurate to say that its interval is 0 < RAND < 1. The minimum
possible value that could be returned is 1E-15.
Bob Wheeler
Interesting discussion. Let me state if it is not already obvious, that I
have not looked at the HP48 internals, and am relying on your posts as to
its nature. However, ignorance has never stopped the determined poster :)
Joseph K. Horn wrote:
> Joey jumps up and down excitedly. "But Roo-man, what if you take a
> *real* list of random numbers, generated by some random physical
> process, and multiply them all by 10? Now they all end in 0, so
> by your criterion they're no longer random! But they are clearly
> exactly as random as they were originally! Huh, Roo-man? Huh?
> Huh?"
Now that is a problem, because "random" is a mathematical (philosophical)
idea which can never be achieved. It is like a point on the real line; a
concept that is useful, but recognized as a convenient fiction. There is
probably more to it than this since I don't recall hearing about anyone
creating a physical device to make a point, but have heard lots of things
about physical devices producing random output.
Series of physically obtained values have been tested for randomness --
Tippet was among the first with weather readings, and if I recall correctly,
he used the chi-squared test. Rather often such series fail randomization
tests. There has been some discussion recently about a buried electrical 60
cycle signal in supposed physically derived random values.
With a pseudo random generator, all one can do is test the series of values
it produces. The tests look for patterns, runs, correlations, etc., and
simply multiplying or adding by a constant should not effect any test. If it
did, one would have to say "this series is random if multiplied X by not by
Y."
Steve VanDevender wrote
>Calling the HP 48 RAND function "not random enough" is really not
>fair, when the primary use of random number generation in most
>mathematical applications is for statistical purposes. In such a
>case a simpler algorithm that is easily provable to have the
>right statistical properties (uniform distribution, sufficient
>period, etc.) is preferable.
Statistical purposes always assume a random input which means that there are
no predictable patterns. This is not the case with RAND, since its output
mod k, where k is a divisor of 10^15, repeats. This means that if one
multiplies such a series by a constant, one will obtain the second series.
If one series is used to calculate a statistic A, and a second differing by
a constant multiple is used to calculate a second statistic B, then the A-B
comparison, among others, will be distorted.