Velocity Reviews > Truly random?

# Truly random?

Walter Roberson
Guest
Posts: n/a

 12-06-2005
In article <(E-Mail Removed)>,
Gordon Burditt <(E-Mail Removed)> wrote:
>True, but he asked for truly random numbers. Perhaps he's betting
>large amounts on the outcome (anyone for Tetris machines next to
>the video poker machines and the slots?), enough to make organized
>efforts to cheat worth the time and trouble. If you're building
>gambling machines which will take bets of real money, you *DO* need
>crypto-quality random numbers or you're going to go broke.

[OT]

My recollection is somewhat vague, as I just skimmed the material
some time ago, but if I recall what I have read correctly, the
professional casinos in places like Los Vegas do -not- use
crypto-quality random numbers, at least for some kinds of machines
such as slot machines. I seem to recall reading that they use a PRNG
but with algorithm parameters modified by a central computer.

The PNRG use has partly to do with managable auditing -- recording each
individual truly random number would take too much storage. The
ability to modify the parameters is used to adjust the payout rate
based upon the payin rate -- essentially once the intake has reached a
trigger value, the central computer adjusts the payout probabilities
upwards to make it more likely that someone will win a large prize. For
one thing, a slot machine that shows exactly the same losing line of
symbol 100 times in a row might be truly random, but it won't be
-perceived- to be random...

PNRG are losing propositions in gambling to the extent that someone
can effectively analyze the past history to predict the future outcomes.
A simple linear congruence PNRG is very risky in that respect, but
there are PRNG with large internal states, and if those states are
reseeded at intervals shorter than would be needed to extract useful
state information, then PRNG can become practical.
--
"It is important to remember that when it comes to law, computers
never make copies, only human beings make copies. Computers are given
commands, not permission. Only people can be given permission."

Kenny McCormack
Guest
Posts: n/a

 12-06-2005
In article <(E-Mail Removed). com>,
Alvin <(E-Mail Removed)> wrote:
>Well, it works like a charm for large numbers, but for small numbers
>(say, 0 to 7), it often repeats them 3 or so times before changing. I
>guess I could determine on how big the number is, so if it's > 100 and
>< 200, select an right sided L block or something. Thanks very much,
>though.

(Obviously, what follows is off-topic, not portable, and blah, blah, blah,
but anyway...)

Long ago and far away, using a compiler/development environment that need
not be mentioned here, I discovered that the higher order bits seemed to
be more random than the lower ordered ones. So, that the usual method (get
the number between, say, 0 and 32767, then divide it by the top of your
range, to get a random number between 0 and your range) tended to give less
good random results. So, I would take the result of random and bit shift
it left 5 (<< 5) to get the lower ordered bits more random. Seems to work.

mensanator@aol.com
Guest
Posts: n/a

 12-06-2005

Kenny McCormack wrote:
> In article <(E-Mail Removed). com>,
> Alvin <(E-Mail Removed)> wrote:
> >Well, it works like a charm for large numbers, but for small numbers
> >(say, 0 to 7), it often repeats them 3 or so times before changing. I
> >guess I could determine on how big the number is, so if it's > 100 and
> >< 200, select an right sided L block or something. Thanks very much,
> >though.

>
> (Obviously, what follows is off-topic, not portable, and blah, blah, blah,
> but anyway...)
>
> Long ago and far away, using a compiler/development environment that need
> not be mentioned here, I discovered that the higher order bits seemed to
> be more random than the lower ordered ones. So, that the usual method (get
> the number between, say, 0 and 32767, then divide it by the top of your
> range, to get a random number between 0 and your range) tended to give less
> good random results. So, I would take the result of random and bit shift
> it left 5 (<< 5) to get the lower ordered bits more random. Seems to work.

Gee, I got a new asshole reamed for suggesting that very thing
a couple months ago despite it being in the FAQ.

Michael Mair
Guest
Posts: n/a

 12-06-2005
Kenny McCormack wrote:
> In article <(E-Mail Removed). com>,
> Alvin <(E-Mail Removed)> wrote:
>
>>Well, it works like a charm for large numbers, but for small numbers
>>(say, 0 to 7), it often repeats them 3 or so times before changing. I
>>guess I could determine on how big the number is, so if it's > 100 and
>>< 200, select an right sided L block or something. Thanks very much,
>>though.

>
>
> (Obviously, what follows is off-topic, not portable, and blah, blah, blah,
> but anyway...)
>
> Long ago and far away, using a compiler/development environment that need
> not be mentioned here, I discovered that the higher order bits seemed to
> be more random than the lower ordered ones. So, that the usual method (get
> the number between, say, 0 and 32767, then divide it by the top of your

You probably are talking about talking the remainder modulo the top
of the range. "Divide" was the other thingy, the one which worked
better than plain modulo.

> range, to get a random number between 0 and your range) tended to give less
> good random results. So, I would take the result of random and bit shift
> it left 5 (<< 5) to get the lower ordered bits more random. Seems to work.

You probably mean the other left. The one most people call "right".
rand() << 5 certainly will give you five quite unrandom lower bits.

-Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

Jordan Abel
Guest
Posts: n/a

 12-06-2005
On 2005-12-06, Kenny McCormack <(E-Mail Removed)> wrote:
> In article <(E-Mail Removed). com>,
> Alvin <(E-Mail Removed)> wrote:
>>Well, it works like a charm for large numbers, but for small numbers
>>(say, 0 to 7), it often repeats them 3 or so times before changing. I
>>guess I could determine on how big the number is, so if it's > 100 and
>>< 200, select an right sided L block or something. Thanks very much,
>>though.

>
> (Obviously, what follows is off-topic, not portable, and blah, blah, blah,
> but anyway...)
>
> Long ago and far away, using a compiler/development environment that
> need not be mentioned here, I discovered that the higher order bits
> seemed to be more random than the lower ordered ones. So, that the
> usual method (get the number between, say, 0 and 32767, then divide it
> by the top of your range, to get a random number between 0 and your
> range) tended to give less good random results. So, I would take the
> result of random and bit shift it left 5 (<< 5) to get the lower
> ordered bits more random. Seems to work.

I assume you mean to the right.

And it is marginally on-topic, because the code of a PRNG with IIRC
characteristics like those you describe appears in the text of the C
standard.

Simon Biber
Guest
Posts: n/a

 12-06-2005
Walter Roberson wrote:
> PNRG are losing propositions in gambling to the extent that someone
> can effectively analyze the past history to predict the future outcomes.
> A simple linear congruence PNRG is very risky in that respect, but
> there are PRNG with large internal states, and if those states are
> reseeded at intervals shorter than would be needed to extract useful
> state information, then PRNG can become practical.

Given a PRNG of the form

#include <stdint.h>

uint32_t foo(void)
{
static uint32_t s = /* unknown */;
const uint32_t n = /* unknown */;
const uint32_t m = /* unknown */;

s = s * n + m;
return s;
}

How many calls would it take to guess what the values of s, n and m were?

--
Simon.

Richard Heathfield
Guest
Posts: n/a

 12-07-2005
Simon Biber said:

> Given a PRNG of the form
>
> #include <stdint.h>
>
> uint32_t foo(void)
> {
> static uint32_t s = /* unknown */;
> const uint32_t n = /* unknown */;
> const uint32_t m = /* unknown */;
>
> s = s * n + m;
> return s;
> }
>
> How many calls would it take to guess what the values of s, n and m were?

None.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

Walter Roberson
Guest
Posts: n/a

 12-07-2005
In article <43962341\$0\$18203\$(E-Mail Removed)> ,
Simon Biber <(E-Mail Removed)> wrote:
>Given a PRNG of the form

>#include <stdint.h>

>uint32_t foo(void)
>{
> static uint32_t s = /* unknown */;
> const uint32_t n = /* unknown */;
> const uint32_t m = /* unknown */;
>
> s = s * n + m;
> return s;
>}

>How many calls would it take to guess what the values of s, n and m were?

As few as 3.

If you have 3 consequative values (x,y,z) that do not involve integer
overflow, then

s = (x*(y+z)-(x^2+y^2))/(z-y)
n = (z-y)/(y-x)
m = (y^2-x*z)/(y-x)

--
I was very young in those days, but I was also rather dim.
-- Christopher Priest

Simon Biber
Guest
Posts: n/a

 12-07-2005
Walter Roberson wrote:
> In article <43962341\$0\$18203\$(E-Mail Removed)> ,
> Simon Biber <(E-Mail Removed)> wrote:
>
>>Given a PRNG of the form

>
>
>>#include <stdint.h>

>
>
>>uint32_t foo(void)
>>{
>> static uint32_t s = /* unknown */;
>> const uint32_t n = /* unknown */;
>> const uint32_t m = /* unknown */;
>>
>> s = s * n + m;
>> return s;
>>}

>
>
>>How many calls would it take to guess what the values of s, n and m were?

>
>
> As few as 3.
>
> If you have 3 consequative values (x,y,z) that do not involve integer
> overflow, then

However, as is always the case for PRNGs, n can easily be chosen large
enough that there will always be integer overflow within three
consecutive values. It wouldn't produce anything resembling random
output if there wasn't integer overflow.

> s = (x*(y+z)-(x^2+y^2))/(z-y)
> n = (z-y)/(y-x)
> m = (y^2-x*z)/(y-x)

Thanks for the formulas; they can be got by just typing

Solve[{x == s * n + m, y == x * n + m, z == y * n + m}, {s, n, m}]

into Mathematica. Unfortunately it doesn't work so well with

Solve[{x == Mod[s * n + m, 2^32],
y == Mod[x * n + m, 2^32],
z == Mod[y * n + m, 2^32]}, {s, n, m}]

--
Simon.

Guest
Posts: n/a

 12-07-2005
Simon Biber wrote:

> Given a PRNG of the form
>
> #include <stdint.h>
>
> uint32_t foo(void)
> {
> static uint32_t s = /* unknown */;
> const uint32_t n = /* unknown */;
> const uint32_t m = /* unknown */;
>
> s = s * n + m;
> return s;
> }
>
> How many calls would it take to guess what the values of s, n and m were?

Three calls plus a few seconds of compute time via brute force. There
may be a faster way.

Of course, if I can only see something like s/100000000, rather than s,
it will take many more samples.

--