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


G

glen herrmannsfeldt

James Kuyper said:
On 06/05/2014 06:54 PM, Stefan Ram wrote:
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.

Yes. I had thought for that reason that they were using very low
bit rates, such as 1bit/s (slow enough that you can generate one
photon at a time, and be sure it is gone before the next one).

According to:

https://en.wikipedia.org/wiki/Quantum_key_distribution#Experimental

they now have some up to 1Mbit/s.
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.

As noted before, one way to remove bias from a hardware random
bit generator is to XOR with a cryptographically secure PRNG.

I suppose one could also use two different secure PRNGs and
XOR them together.

-- glen
 
Ad

Advertisements

M

Martin Shobe

Yes. I had thought for that reason that they were using very low
bit rates, such as 1bit/s (slow enough that you can generate one
photon at a time, and be sure it is gone before the next one).

According to:

https://en.wikipedia.org/wiki/Quantum_key_distribution#Experimental

they now have some up to 1Mbit/s.


As noted before, one way to remove bias from a hardware random
bit generator is to XOR with a cryptographically secure PRNG.

I suppose one could also use two different secure PRNGs and
XOR them together.

To remove bias? That probably won't work. If there's some correlation
between the PRNGs, then you'll be adding bias. The fact that they are
different secure PRNGs isn't sufficient to prevent that.

Martin Shobe
 
S

Stefan Ram

Martin Shobe said:
To remove bias? That probably won't work. If there's some correlation
between the PRNGs, then you'll be adding bias. The fact that they are
different secure PRNGs isn't sufficient to prevent that.

The measurement operators indeed did some transformation of
the quantum data to reduce a bias (Neumann-type normalization):

»the even-parity sequences "00" and "11" are discarded,
and only the odd parity ones "01" and "10" are kept.«
... and mapped to 0 and 1, respectively.

It might be possible that some »unbias effort« might have
distorted some statistical properties somehow. Maybe it would
help to apply all »unbias« operations always to /all/ sources
of randomness measured (i.e., also to the classical ones).
 
C

Chris M. Thomasson

"Ben Bacarisse" wrote in message
"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!

Thank you Ben for taking note of the massive hack folly
ingrained within the posted code. I had a massive brain
melt here. I do not need to wait for a non-zero number
from `rand()' added to the digit sum of the previous.

Why I posted that hack shi%. Well, I have no good answer!

Yikes!

;^(
 
B

Ben Bacarisse

Chris M. Thomasson said:
"Ben Bacarisse" wrote in message
"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!

Thank you Ben for taking note of the massive hack folly
ingrained within the posted code. I had a massive brain
melt here. I do not need to wait for a non-zero number
from `rand()' added to the digit sum of the previous.

I would say that is a rather minor point! I take it you've sorted it
out now, and either don't need this or have a better method?
 
C

Chris M. Thomasson

"Ben Bacarisse" wrote in message
I would say that is a rather minor point! I take it you've sorted it
out now, and either don't need this or have a better method?

This was way back when I was learning how to program BASIC.

Are you speaking about the digits being way too similar? ;^)

Basically, you can bet on two, or three numbers being more
probable. Well, I do remember spreading out the high
probability's across the lowest probabilities. Sort of hiding
them within.

BTW, IIRC, I was using this random digit 0..9 because I
had 10 games, and I was renting to my friends. This was
back in BASIC on my IIGS.
 
Ad

Advertisements

B

Ben Bacarisse

Chris M. Thomasson said:
"Ben Bacarisse" wrote in message
news:[email protected]k...
I would say that is a rather minor point! I take it you've sorted it
out now, and either don't need this or have a better method?

This was way back when I was learning how to program BASIC.

Are you speaking about the digits being way too similar? ;^)

Basically, you can bet on two, or three numbers being more
probable. Well, I do remember spreading out the high
probability's across the lowest probabilities. Sort of hiding
them within.

Yes, there's a strong bias in the digits. That and the odd way you
print the digits in a number rather than printing the number! The whole
thing looked very odd to me.
BTW, IIRC, I was using this random digit 0..9 because I
had 10 games, and I was renting to my friends. This was
back in BASIC on my IIGS.

Ah, I would not dare to say what sort of programs I wrote in those
days.
 
T

Tim Rentsch

Ben Bacarisse said:
I don't think this holds for negative arguments.

Why not? I see no reason it shouldn't.
int number( double min, double top )
{ { double step; do
{ step =( top - min )/( RAND_MAX + 1. );
min = min + rand() * step; top = min + step; }
while( min < top ); } return( int )min; }

int main( void )
{ int a[ 51 ];
for( int i = 0; i < 51; ++i )a[ i ]= 0;
for( int i = 0; i < 1e6; ++i )++a[ number( 1, 50 )];
for( int i = 0; i < 51; ++i )
{ printf((( i + 1 )/ 10 * 10 ==( i + 1 ))?"%5d\n" : "%5d ", a[ i ]); }}
 
T

Tim Rentsch

Assume that in the given application it is acceptable to
wait t seconds for the next random number, then the
possibility that the above procedure will need more time
than t seconds is greater than 0.

Yes, but far less than the probability that some register
bits will quantum mechanically flip undetectably even if
they have ECC. So it isn't the sort of thing worth losing
any sleep over.
 
G

glen herrmannsfeldt

(snip)
Yes, but far less than the probability that some register
bits will quantum mechanically flip undetectably even if
they have ECC. So it isn't the sort of thing worth losing
any sleep over.

Or alpha particles, which are much more common.

-- glen
 
Ad

Advertisements

T

Tim Rentsch

Phil Carmody said:
I've looked into this, but I don't think it's possible, at least
not perfectly in the general case. You just get the same problem,
recursive.

It's actually quite simple, and doesn't have to be recursive,
you can simply store the unused entropy and carry it on into
the next calculation in an iterative manner. (A bit's a bit's
a bit.) [snip elaboration]

I expect you mean something like this -

unsigned
uniform_below( unsigned n ){
static uintmax_t w = 1, x = 0;
// check to be sure 1 <= n <= RAND_MAX
unsigned minimum = (RAND_MAX - (n-1)) % n, t;

while( 1 ){
if( n <= w && x >= w%n ){
t = (x-w%n) % n;
w = 1, x = 0;
return t;
}

t = rand();
if( t >= minimum ) return (t-minimum) % n;

// put in some safeguard against w overflow
w *= minimum, x = x*minimum + t;
}
}

Note that this method doesn't always help. For example, if
RAND_MAX is 32767, and what's wanted is a random number less
than but not equal to 32767, then there is only one unusable value,
and getting that value adds no information to the pool of
unused information. In practice though an approach along these
lines will always return quickly, and will make less use of
the underlying RNG than just discarding unusable values.
 
P

Phil Carmody

Tim Rentsch said:
I expect you mean something like this -

Thank you Tim! I don't recognise that exact formulation,
as it had n as a parameter, so was more general than
the situation I last coded (where you created the object
at the start, and then just polled it for new numbers
in an unchanging range, classic base-conversion). but
the general form was spookily similar.

I must see if I can find a machine with a floppy drive,
and before that see if I have any of my old backup
floppies to see what I once used way back in the glory
days.

Cheers,
Phil
 
Ad

Advertisements


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