0x5DEECE66DL + 0xBL. Why?

[Frank Cisco]

Having a look at random number generation and wondering why they have chosen
such numbers?

 

[blue indigo]

Having a look at random number generation and wondering why they have chosen
such numbers?

Random number generation is one of the black arts. "Magic" numbers abound.
If you think this is bad, mate, you should look at the code for Mersenne
Twister.

 

[Arne Vajhøj]

Having a look at random number generation and wondering why they have chosen
such numbers?

Mathematical analysis and empirical tests.

The old rule is that:

x = (a * x + b) MOD 2^i

has maximal period 2^i if:

a MOD 4 = 1
b MOD 2 = 1

The algorithm you refer to fulfill that.

Arne

 

[Arne Vajhøj]

It's worth noting that these conditions by themselves are
not enough to ensure "good randomness." For example, a=b=1
satisfies both conditions, but the resulting sequence would
not appear very "random" ...

Very true.

It only relates to maximum period.

And maximum periods importance in randomness is only to prevent
repetition.

It was an example that some mathematicians have actually done a
lot of math on this and come up with some results.

Arne

 

[Frank Cisco]

Yes but what is random?

Definition: proceeding, made, or occurring without definite aim, reason, or
pattern

But isn't this contradictory to mathematics as a whole?

 

[Lew]

Yes but what is random?

Definition: proceeding, made, or occurring without definite aim, reason, or
pattern

But isn't this contradictory to mathematics as a whole?

No.

 

[Joshua Cranmer]

Yes but what is random?

In terms of random number generators, the best definition of random is
"Given the internal state of the generator, and the first k bits of
output, the k+1th bit cannot be reliably predicted," or, more succinctly
(but less precisely): "With perfect knowledge, you can't say what the
next bit will be."

For most purposes, we can relax the definition to "Given the kth bit of
output, the k+1th bit cannot be reliably predicted."

Mathematicians much better than you or I have already decided what works
better, and the values here were picked to have a "good" source of
psuedorandomness.

 

[Eric Sosman]

Yes but what is random?

Definition: proceeding, made, or occurring without definite aim, reason, or
pattern

But isn't this contradictory to mathematics as a whole?

TAOCP Volume II devotes an entire section to the question
of "What is a random sequence?" The interested reader will
find it helpful to have understood high-school mathematics.

 

[Arne Vajhøj]

Yes but what is random?

There are different types of randomness.

True randomness need to use something external
like radioactivity as source.

Pseudo random number generators are 100% deterministic,
but the numbers has certain statistical properties that
resembles true random sufficiently for most purposes.

Arne

 

[Frank Cisco]

There are different types of randomness.

True randomness need to use something external
like radioactivity as source.

Pseudo random number generators are 100% deterministic,
but the numbers has certain statistical properties that
resembles true random sufficiently for most purposes.

Arne

I was looking at autonomy in software and by the looks of it, computational
randomness is deterministic therefore not trully random. Put a load of
tickets in a hat and pick from random - that's random - you know why?
Because it's been performed purely naturally. Which leads onto - is
Artificial Intelligence possible? It isn't without, like you said, external
influence.

 

[Joshua Cranmer]

I was looking at autonomy in software and by the looks of it, computational
randomness is deterministic therefore not trully random. Put a load of
tickets in a hat and pick from random - that's random - you know why?

Actually, most physical phenomena that we consider to be random are
typically biased. You probably play card games with
insufficiently-shuffled decks, for example. Putting tickets in a hat is
likely to be extremely heavily biased.

If I don't know the internal state of a deterministic output, I can say
that the output of that algorithm is random. To further your analogy: if
I looked at the people putting tickets into the hat and knew when each
ticket was put in, I could probably guess which one was pulled out with
more accuracy than pure randomness. But if I only knew the tickets that
were put in, not the order, I couldn't tell you better than random.

In the same way, if I knew the seed of a PRNG, I could tell you what its
output was. But if I don't know the seed, the output would appear to be
random.

 

[Arne Vajhøj]

If your PRNG is not cryptographically secure then once you have enough
of the output you could derive the value of the seed. That sort of
security is not a consideration with non-cryptographic PRNGs though is
obviously very important for cryptographic uses.

The hard to predict ability is also a desired quality in other
usages than cryptographic.

Arne