No. If you re-read your question, I think you'll find that it's
logically impossible.
What are you really trying to do?
The answer to your real quustion, whatever it is, *might* be found in
the comp.lang.c FAQ, <http://www.c-faq.com/>, question 13.15.
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
--
comp.lang.c.moderated - moderation address: cl...@plethora.net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.
You cannot do anything *in C* without using c language.
You cannot generate actual random numbers without some kind of
hardware support, or an externally-supplied source of random numbers.
(Some systems use a CD-ROM filled with pre-generated random numbers,
keystroke timing, radioactive decay measurements, or in one case,
a cryptographic hash of an image from a webcam aimed at a Lava
Lamp).
The best you can generate on a deterministic computer is pseudo-random
numbers, which is what rand() and various other "random number
generators" run on computers do. You might search for "Mersenne
twister" for one of the better ones.
"in C" and "without using C language" seem to be contradictory; could
you explain that in a little more detail?
Mersenne twister is a fairly common PRNG algorithm, and you can find
descriptions of it online. You might also check out volume 2 of
Knuth's Art of Computer Programming. I believe it has a section on
random number generation.
I assume he meant without using the standard library.
I vaguely recall that someone put together a moderately "true" random
number generator by reading from /dev/audio when a microphone wasn't
plugged in, then compressing and/or hashing the raw data to generate a
stream of random bits from the microwave background and other ambient
EM. I don't know how well it worked, but that's a bit less machine
specific than RNGs that depend on a sample of Cesium.
Probably overkill for whatever he's trying to do, but interesting
enough that I thought it was worth mentioning.
BTW radioactive decay isn't a very good source of random numbers. It is far too
predictable. Perhaps the least significant bit is useful, but not much more.
I've always wondered if keystroke timing was random. When asking someone to do
random events, perhaps it is, but I doubt timing typing of text by a typist is
because of the frequency of letter usage in a language and the layout of the
keyboard likely results in a rather uniform set of timings, something I very
much would want to avoid in crypto on the same language!
The Lava Lamp hash may be useful. I'd think the voltage at the mains, from the
hundredth on down to be a good random source. I'd think the same of the wind
speed meter sensitive to 1/1000 of of km/h. Perhaps a measure of the
propagation delay of a radio signal over a couple thousand km path. Another
good source would be a SETI@home work unit.
Getting real random is a lot harder than it seems.
That depends on what the least significant bit represents. If it's
yoctoseconds, you might get quite a few bits out of it. In any
case, you'd need to tinker with the hardware to make it unbiased
and run it through a filter to get *good* random numbers. But even
bad hardware is better than a pseudo-random number generator, which
generates no randomness at all.
One filter that can be used, if the random numbers are biased *but
uncorrelated* between samples (e.g. take the time between two decay
events, and generate a 0 or 1 based on even or odd number of
yoctoseconds between them), is to take a pair of bits at a time.
01 generates a 0 bit output, 10 generates a 1 bit output, and 00
and 11 do not generate anything. About the best you can expect is
bits coming out at about 25% of the rate they go in. If the source
is heavily biased, you might end up with 0.0000001% of the rate
coming in. You can prove that the result is unbiased.
Another technique is to use a cryptographic hash of the input (e.g.
SHA-1. MD5 is out of favor because it's been broken to some degree,
although for this application it may not matter much).
>I've always wondered if keystroke timing was random. When asking someone to do
>random events, perhaps it is, but I doubt timing typing of text by a typist is
>because of the frequency of letter usage in a language and the layout of the
>keyboard likely results in a rather uniform set of timings, something I very
>much would want to avoid in crypto on the same language!
I suspect that if the *MOST* significant bit used was microseconds,
and the least significant bit was considerably tinier than that,
you'd get pretty good results.
Of course, if your (PC) keyboard transmits characters to the computer
via a serial port driven by a synchronous clock at a fixed slow
rate like 10KHz - 16KHz, inter-character arrival rates may be a
multiple of that clock, and you get a lot less resolution.
>The Lava Lamp hash may be useful. I'd think the voltage at the mains, from the
>hundredth on down to be a good random source.
It's not only the voltage at the mains (if it were, you'd have to
deal with the 120Hz (USA power) variation in input power, two zero
crossings per cycle). A Lava Lamp involves two viscous fluids
mixing along with convection currents, with occasional splitting
apart and recombining of blobs of fluid. I think there's a lot
more quantum-mechanical effects than only the amount heat input.
Taking an image of bubbles in boiling water might also work.
The Lava Lamp hash may not be so useful as SGI patented it. They
also took down their page on the web.
>I'd think the same of the wind
>speed meter sensitive to 1/1000 of of km/h.
It depends on how often you sample it. Every nanosecond is probably
way too often, if only because of the inertia of the rotating part
of the wind speed meter.
>Perhaps a measure of the
>propagation delay of a radio signal over a couple thousand km path. Another
>good source would be a SETI@home work unit.
>
>Getting real random is a lot harder than it seems.
Agreed.
One really BAD way to try to generate random numbers with C is to
depend on C undefined behavior. For example, allocate 1K of
uninitialized memory with malloc(), and hash it. It will often
come out all zeroes on an OS that clears memory given to a program.
Looking at garbage left in registers is likely to be somewhat
consistent, depending on the program.
Ten years ago, perhaps; these days, one uses Yarrow or Fortuna.
DES
--
Dag-Erling Smørgrav - d...@des.no
Note that for the word random number to have any useful meaning a range
must be specified (without a range most random numbers would be too
large to represent using the entire resources of the universe.
Now empirically on a modern machine setting a tight loop looping through
the numbers 100 until a key is pressed generates pretty good randomness
in that range (no human can strike a key fast enough to even interrupt
the loop on its first pass -- I tried it. But if that is too much try
looping from 0 to 9. You can build up decimal numbers from repeated
applications.
For example if you want a random number in the range 0 to 32767, use a
loop from 0 to 7 to generate the last digit then use a loop from 0 to 99
to generate the 2 and 3 digits then use a loop from 0 to 32 to
generate the high end digits.
Good thought, possibly bad application. Imagine your surprise when you look on
the circuit board and find that the clock that times the keyboard serial line is
a division of the clock that times the CPU. All that you can hope to generate
are deterministic numbers.
Better, digitize the cosmic microwave background radiation.
But I am not using the clock. The core of the code looks like:
int spinner(int lower, int upper){
keyboard kbrd;
while(true){
for(int chosen(lower); chosen != upper; ++chosen){
if(kbrd.key_pressed()) return chosen;
}
}
}
keyboard is a class that supports a raw keyboard read. But when I wrote
this little function I also tested it and then went on to suggest that
readers of the book for which I wrote it also tested it. Yes, there may
be hardware on which the method would fail but that should show up with
some simple testing.
> For example if you want a random number in the range 0 to 32767, use a
> loop from 0 to 7 to generate the last digit then use a loop from 0 to 99
> to generate the 2 and 3 digits then use a loop from 0 to 32 to
> generate the high end digits.
Bad randomness. This will never produce any number ending in 8 or 9. So
about 20% of the values happen with a probability of 0, about 80% happen
with a probability that is 1.25 times too high.
--
Greetings,
Jens Schmidt
--
Careless of me.
Of course I have to generate values in the range 0 to 32769 and discard
instances of 32768 and 32769.
You own a CPU that will run without a clock input? How can it ever hope to
synchronize with the outside world? I can just imagine the I/O bus expecting to
see an address while the CPU is putting data on the lines.
I'm not talking about a wall clock, but a cycle clock. You know the number like
3.0GHz. That clock.
> The core of the code looks like:
>
> int spinner(int lower, int upper){
> keyboard kbrd;
> while(true){
> for(int chosen(lower); chosen != upper; ++chosen){
> if(kbrd.key_pressed()) return chosen;
> }
> }
> }
>
> keyboard is a class that supports a raw keyboard read. But when I wrote
> this little function I also tested it and then went on to suggest that
> readers of the book for which I wrote it also tested it. Yes, there may
> be hardware on which the method would fail but that should show up with
> some simple testing.
I understand what you think you are doing. You don't understand what the
hardware does when you ask it to do it. Perhaps on a 8080 system the keyboard
will operate the way you expect, but a serial keyboard doesn't.
In the case of a serial line keyboard it can only let the machine know a key has
been pressed in phase with the clock for the serial line transitions. As this
likely is in phase with the CPU clock say by dividing it by 30,000 then only at
exact intervals of 30,000 machine cycles can a key press register. Then your
loop counter can only give values for every 30,000 machine cycles. With the
addition of a NOP your loop could return the same number no matter what! Not
exactly random. And hence the general problem trying to use time based events
to generate random numbers.
Your loop is likely fine to generate a handful of numbers, say for seeding a
PRNG, but I wouldn't trust it to generate several tens of millions without
testing on the hardware it runs on.
Many will not have seen my response as I managed to put it in my
signature :(
Yes I should generate numbers in the range 0 to 32769 and discard any
instances of 32768 and 32769.
--
Note that robinton.demon.co.uk addresses are no longer valid.
the rate is predictable, the timing of the individual nuclear events are not.
> Perhaps the least significant bit is useful, but not much more.
so measure with more precision and get more usable bits.
> I've always wondered if keystroke timing was random.
not really definition.
> When asking someone to do random events, perhaps it is,
> but I doubt timing typing of text by a typist is
> because of the frequency of letter usage in a language and the layout of the
> keyboard likely results in a rather uniform set of timings, something I very
> much would want to avoid in crypto on the same language!
throw out the bits that represent anything larger than a
100 microseconds use what's left, (or hash the value down to fewer
bits in some other way)
> The Lava Lamp hash may be useful. I'd think the voltage at the mains,
> from the hundredth on down to be a good random source.
you'd get 1 usable bit from a 16 bit DAC
you'd do better just using a microphone.
> I'd think the same of the wind
> speed meter sensitive to 1/1000 of of km/h. Perhaps a measure of the
> propagation delay of a radio signal over a couple thousand km path.
possibly hard to measure.
> Another
> good source would be a SETI@home work unit.
a webcam filming a wick flame. or even just filming the thermal noise
events inside the lens cap.
You are aware of the modulo operator, right?
If you want a pseudo-random number in a particular range, you use an
appropriate pseudo-random number generator seeded with whatever you can
find lying around, and return (lcg() % (max - min + 1) + min).
There are many applications (such as statistical simulations, and some
aspects of some games) where you want to use the exact same sequence
every time you run the program, or at least the ability to reproduce a
particular sequence, so unless you need crypto-grade randomness, it is
better to use a good deterministic generator, such as Knuth's version of
the linear congruential generator.
DES
--
Dag-Erling Smørgrav - d...@des.no
> You are aware of the modulo operator, right?
>
> If you want a pseudo-random number in a particular range, you use an
> appropriate pseudo-random number generator seeded with whatever you can
> find lying around, and return (lcg() % (max - min + 1) + min).
Don't do that. It introduces a bias.
Extreme example:
lcg() returns evenly distributed integers in the range 0..2
min is 0, max is 1
so you get from
lcg() == 0 => 0
lcg() == 1 => 1
lcg() == 2 => 0
Unless you really want 2/3 of 0s and 1/3 of 1s that is not even close
to evenly distributed. Other values may make the problem smaller, but
not go away.
--
Greetings,
Jens Schmidt
Yes, individual events are predictable in that they can be influenced. That is
one of the surprises in physics.
However the rate of decay is so stable that it is uniform and not random over a
given period. In other words you will get decay counts almost identical every
time you look at the sample. That is why only the least significant digit might
be random. And you need to test that before you rely on it.
The decay rate itself, for some kinds of decay, has a periodicity of the earth's
orbit around the sun, this due to flavor switching of solar neutrinos, never
mind the half rate decay. Another recent surprise to physics.
But just looking at it another way, if your time slice is very tiny, you will
get piles of zero counts, obviously not random. If your slice is big you get
lots of huge counts, but never a zero so obviously not random. All you can do
is use the low order bits, but is the decay rate so stable that you get the same
or a very close count frequently? Unfortunately the answer is yes. Otherwise
you couldn't state its half life.
>> Perhaps the least significant bit is useful, but not much more.
>
> so measure with more precision and get more usable bits.
>
>> I've always wondered if keystroke timing was random.
>
> not really definition.
>
>> When asking someone to do random events, perhaps it is,
>> but I doubt timing typing of text by a typist is
>> because of the frequency of letter usage in a language and the layout of the
>> keyboard likely results in a rather uniform set of timings, something I very
>> much would want to avoid in crypto on the same language!
>
> throw out the bits that represent anything larger than a
> 100 microseconds use what's left, (or hash the value down to fewer
> bits in some other way)
Assuming the keyboard I/F doesn't take out timing to say 10000 microseconds.
Have you all forgotten the TRS80 keyboard debounce?
> Jasen Betts wrote:
>> the rate is predictable, the timing of the individual nuclear events are
not.
>
> Yes, individual events are predictable in that they can be influenced.
> That is one of the surprises in physics.
Do you have any numbers how big this effect may be, especially in comparison
to the stability of the timing in the measurement equipment?
> However the rate of decay is so stable that it is uniform and not random
> over a given period. In other words you will get decay counts almost
> identical every time you look at the sample. That is why only the least
> significant digit might be random. And you need to test that before you
> rely on it.
Measuring the rate of decay is a big error. Physics tell us this will
deliver an averaged value, so almost all randomness is removed. Measure
the time between two events instead.
> The decay rate itself, for some kinds of decay, has a periodicity of the
> earth's orbit around the sun, this due to flavor switching of solar
> neutrinos, never mind the half rate decay. Another recent surprise to
> physics.
Again, is the decay rate varying enough to be measureable with any
equipment that has a reasonable price tag? And the half rate decay is
well known and can be corrected with a little calculation.
BTW, the dead time (no sensor can separate two events very short after
another) is probably a more relevant problem. But also this can be
corrected.
> But just looking at it another way, if your time slice is very tiny, you
> will get piles of zero counts, obviously not random. If your slice is big
> you get lots of huge counts, but never a zero so obviously not random. All
> you can do is use the low order bits, but is the decay rate so stable that
> you get the same or a very close count frequently? Unfortunately the
> answer is yes. Otherwise you couldn't state its half life.
Again, measure interval times, not counts.
Interval times are normal-distributed, this can be calculated back to
an even distribution if needed.
Side remark: we are currently leaving contact both with the C language
and the thread theme "simple way". So either let's end this or continue
somewhere more appropriate.
--
Greetings,
Jens Schmidt
As I understand it, the influence can be carried out until the end of time.
>> However the rate of decay is so stable that it is uniform and not random
>> over a given period. In other words you will get decay counts almost
>> identical every time you look at the sample. That is why only the least
>> significant digit might be random. And you need to test that before you
>> rely on it.
>
> Measuring the rate of decay is a big error. Physics tell us this will
> deliver an averaged value, so almost all randomness is removed. Measure
> the time between two events instead.
>
>> The decay rate itself, for some kinds of decay, has a periodicity of the
>> earth's orbit around the sun, this due to flavor switching of solar
>> neutrinos, never mind the half rate decay. Another recent surprise to
>> physics.
>
> Again, is the decay rate varying enough to be measureable with any
> equipment that has a reasonable price tag? And the half rate decay is
> well known and can be corrected with a little calculation.
Radioactive sample, Geiger counter GPS clock and a desktop computer to record
the numbers. No special equipment required. It was one of those no one thought
to look for it before discoveries. And answered why different people got
different decay rates for the same stuff.
> BTW, the dead time (no sensor can separate two events very short after
> another) is probably a more relevant problem. But also this can be
> corrected.
>
>> But just looking at it another way, if your time slice is very tiny, you
>> will get piles of zero counts, obviously not random. If your slice is big
>> you get lots of huge counts, but never a zero so obviously not random. All
>> you can do is use the low order bits, but is the decay rate so stable that
>> you get the same or a very close count frequently? Unfortunately the
>> answer is yes. Otherwise you couldn't state its half life.
>
> Again, measure interval times, not counts.
>
> Interval times are normal-distributed, this can be calculated back to
> an even distribution if needed.
>
> Side remark: we are currently leaving contact both with the C language
> and the thread theme "simple way". So either let's end this or continue
> somewhere more appropriate.
--
> You are aware of the modulo operator, right?
I'm quite sure Francis is aware of it. But he knows better than to use
it for this. Modulo is pretty much never the right operator to rescale
random numbers from one integer range to another.
To build a 0..32676 random number from a 0..9 one, a better approach
might well be to use 5 draws to construct a number 0..99999, reject and
retry until the result is below 3*32768, and divide the remaining ones
by three.
> However the rate of decay is so stable that it is uniform and not random over a
> given period.
Which is why nobody in their right mind would use that as the random
number generator. You use the arrival time of an individual event or
the time span from on event to the next instead.
> In other words you will get decay counts almost identical every
> time you look at the sample.
No, you won't. You get counts following a well-known random
distribution. "Almost identical" really does no justice to the result.
> That is why only the least significant digit might be random.
Only if one designed the detector such that each reading is expected to
be less than 100. Which would be utterly foolish.
> But just looking at it another way, if your time slice is very tiny, you will
> get piles of zero counts, obviously not random. If your slice is big you get
> lots of huge counts, but never a zero so obviously not random.
Pardon the French, but that's nonsense. You're mixing up "random" with
"uniformly distributed random".