How do you guys limit rand() results to a range?


K

Keith Thompson

My point was that we had dices and coins even before the
20th century. There are classical sources of randomness such
as the bean machine (Galton box) or the roulette wheel, that
one really cannot predict and which deliver a certain
distribution of frequencies.

Dices and coins usually are random enough to be deemed
sources of randomness. I will call them »classical sources«
here.

However, today we also have quantum sources of randomness,
and we know that they have different properties than
classical sources.
[...]

Are you saying that, given two streams of "randomish" numbers,
one from a roulette wheel and one from some quantum source, it's
possible to tell which is which just by examining the numbers?
Is that correct? If so, I find it surprising. Can you summarize the
difference in a way that a non-statistician is likely to understand?
 
Ad

Advertisements

K

Keith Thompson

James Kuyper said:
Assume that, knowing the first N numbers, the exact algorithm, and
complete internal state, you could determine upper and lower limits on
the next number - but that it was impossible to determine which number
within that range would be generated - would you consider that a
deterministic system? I sure wouldn't.

Nor would I. Given my ad-hoc definition, deterministic systems cannot
generate "really random" numbers, though they can generate sequences
that meet statistical tests for randomness. The digits of pi are
(probably) an example.
 
K

Keith Thompson

glen herrmannsfeldt said:
How about for really really really large N?

Same thing. The concept I'm trying to describe is a mathematical
abstraction.
More specifically, how much randomness is there in the universe?

I don't know. It may be that "really random" numbers are not physically
possible; I lack sufficient knowledge of math and/or physics to say one
way or the other.
 
K

Keith Thompson

glen herrmannsfeldt said:
(snip, someone wrote)



There is an algorithm to take bits with non-uniform distribution
and generate a (smaller) bit stream with uniform distribution.
I forget the details, but some years ago intel build a hardware
(noise source) random bit generator using it.

Some described in:

https://en.wikipedia.org/wiki/Hardware_random_number_generator

One that I didn't think of: exclusive OR a biased hardware random
source with an unbiased PRNG.

One inefficient approach I've heard of: Generate two numbers x and y.
If x < y, return 0. If x > y, return 1. (If x == y, try again.)
 
M

Martin Shobe

My point was that we had dices and coins even before the
20th century. There are classical sources of randomness such
as the bean machine (Galton box) or the roulette wheel, that
one really cannot predict and which deliver a certain
distribution of frequencies.

Dices and coins usually are random enough to be deemed
sources of randomness. I will call them »classical sources«
here.

However, today we also have quantum sources of randomness,
and we know that they have different properties than
classical sources.
[...]

Are you saying that, given two streams of "randomish" numbers,
one from a roulette wheel and one from some quantum source, it's
possible to tell which is which just by examining the numbers?
Is that correct? If so, I find it surprising. Can you summarize the
difference in a way that a non-statistician is likely to understand?

I've heard that there is a difference in how the events are counted. I
don't know enough about quantum mechanics to know for certain if this is
correct, but here's how I understand the situation.

In the classical case, each event has its own identity. This means that
it matters which event produced which result. For example, if you flip
two identical, fair coins, there are four equally probable outcomes:

HH
HT
TH
TT

In the quantum case, the events don't have an identity. This means that
it doesn't matter which event produced the result. If the two coins
followed the quantum rules, there would only be three equally probable
outcomes:

HH
HT
TT

Martin Shobe
 
J

James Kuyper

On 06/05/2014 12:07 PM, Martin Shobe wrote:
....
I've heard that there is a difference in how the events are counted. I
don't know enough about quantum mechanics to know for certain if this is
correct, but here's how I understand the situation.

In the classical case, each event has its own identity. This means that
it matters which event produced which result. For example, if you flip
two identical, fair coins, there are four equally probable outcomes:

HH
HT
TH
TT

In the quantum case, the events don't have an identity. This means that
it doesn't matter which event produced the result. If the two coins
followed the quantum rules, there would only be three equally probable
outcomes:

HH
HT
TT

I'm fairly certain that's not correct, as you've stated it, though it
might be a garbled version of a true statement. Can you locate a more
authoritative explanation of the issue you're talking about?
 
Ad

Advertisements

M

Martin Shobe

On 06/05/2014 12:07 PM, Martin Shobe wrote:
...

I'm fairly certain that's not correct, as you've stated it, though it
might be a garbled version of a true statement. Can you locate a more
authoritative explanation of the issue you're talking about?

After some quick research, I suspect it's a garbled version of the
difference between Bose-Einstein statistics and Maxwell-Boltzmann
statistics.

Martin Shobe
 
G

glen herrmannsfeldt

Keith Thompson said:
(e-mail address removed)-berlin.de (Stefan Ram) writes:
(snip)
(snip)

Are you saying that, given two streams of "randomish" numbers,
one from a roulette wheel and one from some quantum source, it's
possible to tell which is which just by examining the numbers?
Is that correct? If so, I find it surprising. Can you summarize the
difference in a way that a non-statistician is likely to understand?

Hmm. Seems to me that a roulette wheel might have some bias,
as the little bins aren't all exactly the same. It would take a
large number of rolls to detect that, though.

For a quantum randomness source, one would likely use a debias
algorithm on the bits coming out. The quantum source itself might
be nice and random, but you have to convert the randomness to
some other form to get it out, somewhat equivalent to the ball
falling into the bin on the routlette wheel. (One possibility
is a polarization detector for photons, which isn't quite perfect.)

As mentioned in:

https://en.wikipedia.org/wiki/Hardware_random_number_generator

that algorithm (like so many) traces back to von Neumann.

You take the bits two at a time, if the two are the same, throw
out (ignore) the pair. If they are 01 or 10, output a 0 or 1,
respectively, in the outgoing bit stream.

But you could also use a debias algorithm on the routlette wheel.
That would probably confuse gamblers, though. Seems to me that
the main problem is that the bit generation rate of the roulette
wheel is pretty low.

-- glen
 
G

glen herrmannsfeldt

Martin Shobe said:
(snip)

(snip)
After some quick research, I suspect it's a garbled version of the
difference between Bose-Einstein statistics and Maxwell-Boltzmann
statistics.

Well, there are three-state cases in QM, but you would normally
know about them. That complicates bit extraction, just as it
would getting bits from a roulette wheel.

But consider the coin-flip case. Say you build a coin-flip bit
generator. A box with a coin, flip device, and which side is up
sensor. It is running fine, but the bits aren't coming out fast
enough, so you speed it up. At some point, it will turn out that
the coin isn't flipping enough between bit reads, and correlation
starts to appear.

A similar problem appears in quantum systems if you try to
extract bits too fast. As noted, the exact effects are different
for bosons and fermions.

In the case of coupled two-state systems, the states aren't the
ones indicated, but

HH
TT
(HT+TH)/sqrt(2)
(HT-TH)/sqrt(2)

See, for example: https://en.wikipedia.org/wiki/Kaon#Mixing

and especially the paragraph on regeneration.

-- glen
 
G

glen herrmannsfeldt

Keith Thompson said:
Same thing. The concept I'm trying to describe is a mathematical
abstraction.
I don't know. It may be that "really random" numbers are not physically
possible; I lack sufficient knowledge of math and/or physics to say one
way or the other.

What I am saying is that, for sufficiently large N, you don't care.

The question left is, how large must N be, and how do we find a
system with that large an N?

It isn't so hard to make really large N PRNGs, but they get slower
as N gets larger.

So, one hopes to find a quantum system with a really large N, but
that is also fast at the same time.

-- glen
 
K

Keith Thompson

glen herrmannsfeldt said:
What I am saying is that, for sufficiently large N, you don't care.

I'm sure that's true.

(It's also a different point than the one I was making, which was
abstract rather than practical.)
 
Ad

Advertisements

S

Stefan Ram

Martin Shobe said:
In the quantum case, the events don't have an identity. This means that
it doesn't matter which event produced the result. If the two coins
followed the quantum rules, there would only be three equally probable
outcomes:
HH
HT
TT

This is true, but the arxiv article I have mentioned is
about more subtle differences. However, I cannot explain
it better than the arxiv article itself.

http://arxiv.org/abs/1004.1521
 
S

Stefan Ram

This is true, but the arxiv article I have mentioned is
about more subtle differences. However, I cannot explain
it better than the arxiv article itself.
http://arxiv.org/abs/1004.1521

Ok, I now have actually looked at it again! I see that over
the years I had lost some memory of the contents of that
paper and hope that I have not misrepresented its contents
here before.

The article describes a comparison of statistical properties
of quantum random values with pseudo-random (non-quantum)
values and finds that the Borel normality test was able to
distinguish between the quantum and non-quantum (pseudo-random)
numbers: the quantum sources were /less/ normal! It seems
that there is not yet an explanation for this. (A sequence is
Borel normal if every binary string appears in the sequence
with the right probability of 2^(-n) for a string of length n.)

Before this article, it was know that quantum randomness
cannot be computed, but this measurement showed differences
that were detectable by analyzing the outputs (not the sources).
 
C

Chris M. Thomasson

"DFS" wrote in message news:[email protected]
I've been reading up on rand() for the first
time, and found this article:
[...]

A long time ago, I had to get a range from 0...9

So, IIRC, I did some crazy hack like:
_________________________________________
#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>
#include <assert.h>


unsigned
rand_generate(
unsigned const nmax,
unsigned const nds
){
unsigned r = 0;
unsigned i = 0;
unsigned ds = 0;

int denom = 1;
unsigned const pow = 10;

// hack, and potential infinite loop! ;^/
// find a non-zero random number...
while (! (r = (unsigned)rand() + nds));

for (i = 0; i < nmax && r > 0; ++i)
{
unsigned n = r / denom;
unsigned m = n / pow * pow;
unsigned d = n - m;
ds += d;

printf("%u", d);

r = r - d * denom;

denom *= pow;
}

return ds;
}


int
main(void)
{
unsigned i = 0;
unsigned nds = 0;
unsigned const imax = 113;

srand(74);

for (i = 0; i < imax; ++i)
{
nds = rand_generate(10, nds);
}

return 0;
}
_________________________________________


This generates a sequence of digits where each
digit is 0...9.

lol!

;^)
 
D

DFS

"DFS" wrote in message I've
been reading up on rand() for the first time, and found this
article: [...]

A long time ago, I had to get a range from 0...9

So, IIRC, I did some crazy hack like:
_________________________________________ #include <stdlib.h>
#include <stdint.h> #include <stdio.h> #include <assert.h>


unsigned rand_generate( unsigned const nmax, unsigned const nds ){
unsigned r = 0; unsigned i = 0; unsigned ds = 0;

int denom = 1; unsigned const pow = 10;

// hack, and potential infinite loop! ;^/ // find a non-zero random
number... while (! (r = (unsigned)rand() + nds));

for (i = 0; i < nmax && r > 0; ++i) { unsigned n = r / denom;
unsigned m = n / pow * pow; unsigned d = n - m; ds += d;
printf("%u", d);

r = r - d * denom;

denom *= pow; }

return ds; }


int main(void) { unsigned i = 0; unsigned nds = 0; unsigned const
imax = 113;

srand(74);

for (i = 0; i < imax; ++i) { nds = rand_generate(10, nds); }

return 0; } _________________________________________


This generates a sequence of digits where each digit is 0...9.

lol!

;^)


ha!

I ran it 3x. It spit out the same set of numbers each time:

471371441210092359788123968142812184305707186212696807660766600741796518517104183152211929905651609000124162460704934537682346850821676420697715568000994776507284982399312165110415264434169198821448611078785597205543392112344186259905591693732028121484809243503997223530895166900899213546766802358427495144992159311664158081816648249141071851532971182368592456215209414841065235518915403860889415051777874643527817110139655971122121806212303727100296782579742403581121715528632759741168069545561048331423104543944511308042236669471311252886712411298032197945013916353275181493902383547742078129646926216929338771527872135181672385018062766411066939581725372671485128032729861562129681395823417953712767461161853730178163434460714815420951789082527183588465331919216517216353902160869769338762960187268107218298145639185761931872254452431701385032480574265320834696431521953928583821728091326113415108194198499266029217555515249571285364129793001620924106492346668264466121866747064164013155437021333
7153310348111770904127537067114468902677729750735081889859901518074927458331

471371441210092359788123968142812184305707186212696807660766600741796518517104183152211929905651609000124162460704934537682346850821676420697715568000994776507284982399312165110415264434169198821448611078785597205543392112344186259905591693732028121484809243503997223530895166900899213546766802358427495144992159311664158081816648249141071851532971182368592456215209414841065235518915403860889415051777874643527817110139655971122121806212303727100296782579742403581121715528632759741168069545561048331423104543944511308042236669471311252886712411298032197945013916353275181493902383547742078129646926216929338771527872135181672385018062766411066939581725372671485128032729861562129681395823417953712767461161853730178163434460714815420951789082527183588465331919216517216353902160869769338762960187268107218298145639185761931872254452431701385032480574265320834696431521953928583821728091326113415108194198499266029217555515249571285364129793001620924106492346668264466121866747064164013155437021333
7153310348111770904127537067114468902677729750735081889859901518074927458331

471371441210092359788123968142812184305707186212696807660766600741796518517104183152211929905651609000124162460704934537682346850821676420697715568000994776507284982399312165110415264434169198821448611078785597205543392112344186259905591693732028121484809243503997223530895166900899213546766802358427495144992159311664158081816648249141071851532971182368592456215209414841065235518915403860889415051777874643527817110139655971122121806212303727100296782579742403581121715528632759741168069545561048331423104543944511308042236669471311252886712411298032197945013916353275181493902383547742078129646926216929338771527872135181672385018062766411066939581725372671485128032729861562129681395823417953712767461161853730178163434460714815420951789082527183588465331919216517216353902160869769338762960187268107218298145639185761931872254452431701385032480574265320834696431521953928583821728091326113415108194198499266029217555515249571285364129793001620924106492346668264466121866747064164013155437021333
7153310348111770904127537067114468902677729750735081889859901518074927458331
 
C

Chris M. Thomasson

"DFS" wrote in message news:[email protected]
"DFS" wrote in message I've
been reading up on rand() for the first time, and found this
article: [...]

A long time ago, I had to get a range from 0...9

So, IIRC, I did some crazy hack like:
_________________________________________ [...]
srand(74);
[...]
This generates a sequence of digits where each digit is 0...9.

lol!

;^)
ha!
I ran it 3x. It spit out the same set of numbers each time:

Try changing the seed for the random number generator
to a unique number per run? The posted hack code is hard
coded to `srand(74)'.

;^)
 
Ad

Advertisements

R

Richard Bos

DFS said:
On 06/05/2014 07:45 PM, Chris M. Thomasson wrote:

I ran it 3x. It spit out the same set of numbers each time:

Well, yeah. Consider the above line.

Richard
 
D

DFS

"DFS" wrote in message On
06/05/2014 07:45 PM said:
"DFS" wrote in message I've
been reading up on rand() for the first time, and found this
article: [...]

A long time ago, I had to get a range from 0...9

So, IIRC, I did some crazy hack like:
_________________________________________ [...]
srand(74);
[...]
This generates a sequence of digits where each digit is 0...9.

lol!

;^)
ha!
I ran it 3x. It spit out the same set of numbers each time:

Try changing the seed for the random number generator
to a unique number per run? The posted hack code is hard
coded to `srand(74)'.

;^)


duh! I seeded it with time(NULL) and got different results each time
(unless I ran it again right away and the seed hadn't had time to change).
 
J

James Kuyper

On 06/05/2014 06:54 PM, Stefan Ram wrote:
....
The article describes a comparison of statistical properties
of quantum random values with pseudo-random (non-quantum)
values and finds that the Borel normality test was able to
distinguish between the quantum and non-quantum (pseudo-random)
numbers: the quantum sources were /less/ normal! It seems
that there is not yet an explanation for this. (A sequence is
Borel normal if every binary string appears in the sequence
with the right probability of 2^(-n) for a string of length n.)

If that's what they measured, then I'm far less surprised by that result
than I was by your original statement of it. I'm so unsurprised, that
the fact that they consider it unexplained confuses me. Possibly I'm
missing something that makes that result less obvious than it seems to be.

Quantum randomness is always necessarily derived ultimately from
measurements of a quantum process. It's extremely difficult to ensure an
exactly even distribution when measuring something, even if the thing
you're trying to measure does, in fact, have an exactly uniform
distribution. Even the tiniest contamination of your measurement will
introduce some uneveness. It's far easier to ensure an absolutely even
distribution when generating pseudo-random numbers.

I doubt that it would be difficult to pick an arbitrary possible value
for the Borel normality test, and design a deliberately defective
pseudo-random number generator that would, on average, produce that value.
 
Ad

Advertisements

B

Ben Bacarisse

Chris M. Thomasson said:
"DFS" wrote in message I've been
reading up on rand() for the first
time, and found this article:
[...]

A long time ago, I had to get a range from 0...9

So, IIRC, I did some crazy hack like:
// hack, and potential infinite loop! ;^/

I note all the smileys and LOLs and so on, but what is the point of
posting this? Joke code is rarely funny to anyone but the author, and
there's a chance (slight, I grant you) that someone might use it!
 

Similar threads

B
2 3
Replies
41
Views
1K
Malcolm McLean
M
I
Replies
0
Views
3K
Illumin Arty
I
P
2
Replies
25
Views
963
Ike Naar
I
J
2
Replies
39
Views
1K
Ken Brody
K
D
Replies
13
Views
909
glen herrmannsfeldt
G
L
Replies
0
Views
596
luser- -droog
L
T
Replies
0
Views
343
Tman508
T
D
Replies
7
Views
496
Edward A. Falk
E
Top