How to check the TRUE randomness (of Prop, for example) with BUST in SPIN?
cessnapilot
Posts: 182
Hi All,
There were several threads on this forum relating to the randomness or random numbers. Those, that I have seen, boiled down for me that with SPIN one can only make Pseudo Random Generators (PRNGs) and with Chip Gracey's RealRandom object we can make True Random Number Generators (TRNGs). The behavior of Q_True_Rnd procedure in SPIN_TrigPack object clearly contradicts to this simplification. We can make TRNGs with only SPIN code plus CNT without extra COG for RealRandom. And this is good.
I tried with
··1 DemoBoard
··2 PropSTICK with RS232
··2 PropRPM
··4 Propeller Proto Board
+6 40DIP Propeller chip (plugged in a PropRPM board, only 3 pins folded back, all were repairable.)
and all showed (up till now) true random behavior with the TRNG generator of SPIN_TrigPack object. This behavior of the Propeller may go away in the future with the new batches, but I experienced far too often the truth of the aviation wisdom
"Equipment problems that go away by themselves will come back by themselves."
This true randomness ability of Prop with SPIN only is, however, not a problem at all, but a great feature that we can use· for our advantage. I am searching here for effective statistical tests of true randomness that are also very simple to carry out with Propeller. I propose some test at the end of this post. From these tests and from your suggestions it may evolve a demanding, fast and easy to use randomness check procedure collection. The basic DESIGN REQUIREMENT for this battery of code IS ONLY COMMON SENSE. And that is not easy, since, as you might have noticed, that common sense is not so common in our over-advertised and over-patented world where common sense is always attacked fiercely. And that means, that we have to take extreme care of it.
Evidence based statistical testing
=========================
Advertised test suits for randomness are not easy to program with the Propeller for simple and quick use. They do not even worth of implementing. Many tests in 'official' test suits need much more explanation to understand their results than the non-randomness they might recover. I shall avoid here these artificial mathematical amok in several dimensions. Usually the more complex of a test the more weakest its decision power. Complicated test suits may even contain errors that are not easy to discover. After many years of intensive use by hundreds of professional mathematicians, they recovered errors even in NIST test suit recently. The “"Ferrenberg affair" showed that even a large battery of advertised statistical test suits is a scrap in detecting imperfections, that only an application can reveal. So I shall keep the Propeller test suit as a simple, understandable and robust first line of defense that protects you when 'amateurish' random numbers are proposed or generated for you. Beside outcomes of RNGs you can check numbers that come from everyday's life as company prices, stock exchange data, numbers in reports submitted to you or fish counts in natural waters. As you will see, it is easy to build a DIY true random number generator with real physical source of entropy. With the here proposed Battery of Useful and Simple Tests (BUST) you can verify or bust any PRNG or TRNG generators with a reasonable certainty. But, remember that only the concrete an succesfull application can stamp the· final acceptance mark on any random number sequence.·····
A simple definition to avoid philosophy:
============================
If you keep in mind that (pseudo or real) random numbers are mostly about not being predictable by the user of your application rather than worrying about any deep philosophy of what randomness is then it all becomes much simpler:
A sequence of numbers can be treated as truly random for many purposes for a given user in a given circumstance, if it isn't possible to make a profit on you, or on the program, by the user betting on them!
Relativity (as always):
=================
Randomness is not only uncertain but·a relative idea, too. It never refers to a single number, and for a series of numbers it is not the same for every person. For the programer, the sequence from a congruent random number generator (CRNG) in his application is absolutely predictable. For the user of the program the sequence is random. An average user (like me) with only restricted and slow organic memory, cannot figure out the generator. A determined mathematical analyst, however, can collect a small sample of the output of a PRNG, and by solving some linear equations, can work out the generator, and therefore predict, the entire sequence. The famous Mersenne Twister is pretty easy to break for a bold analyst, 'just' 634 outputs are needed to predict it.
Randomness all around (if you need it you can have it)
=====================================
If you want to use secure pseudo or true random numbers in your application, I think it's a really BAD idea to use known methods. So many programmers treat PRNGs as something to start once and then use to get many random bits out of without care. This is wrong. A PRNG has input also an output. You should be constantly feeding the input with anything even remotely random that you can find. Keystroke timings, bytes received at UART, RF module outcome from an empty channel, CPU cycle counts. Everything. Anything. All the time. Nobody will brake or predict that sequence.
DIY Physical sources of randomness
=========================
You don't need nuclear decay and GM counter, although they are great to play with from a distance. If you do not live in a deep granite cavern, a cheap GM counter and the cosmic radiation will do. My radiation monitor 4/4RC (S.E. Int. Inc) gives about 40-70 counts / minute on my table (0.7 uSv/hr). The mic of the DemoBoard picks it up easily. One can take the CNT difference between cosmic events to XOR with the seed, for example. With BUST we shall be able to test that generator, or we can even test the sequence of those time differencies. If we detect some definite non-randomness in those ticks, than E.T. is probably· using sharp and far penetrating cosmic ray beams, focused by gravitational lenses, instead of weak and diffuse RF waves to message some greetings. If you do not like to hear or know about anything 'nuclear' you can use many other source of randomness around you. Actual random number generators are pretty cheap. Place a microphone close to the power supply fan of a PC, and read the sound coming in with the Prop. Filter out all but the very highest frequency components, and you have a strong source of randomness. Another source that is available to everyone, is environmental RF noise. I mentioned that a signal seeking RF module is a· great generator of random byte streams. Sample this several times, and combine the results into a seed, wherever possible. If there are transmitting stations nearby on the channel, change channel or chop antenna. I tried an RF RxTx modul (RXQ2) with 256 channels from 422.4 MHz. It checks for the presence of the noise on the channel with reading data at high baud rates. From noisy channel (continuous data with a running average close to 127,5 in some randomly selected short intervals) it reads some random bytes from random positions. It mixes the actual seed of a PRNG with these random bytes, and than changes the Rx channel randomly from the results of the generator. This "entropy read" injects fresh blood into the RNG and is repeated in random intervals. That RF module costed only 10$. If the enemy is so close to you that he can silence with a strong RF transmission all of those 256 channels of the properly shielded receiver, look around you and catch him.
True randomness for you in the industry (insert coin first, than you will have fair chances)
=============================================================
All the much ado on how difficult to create truly random numbers seems to me to be smoke in eyes of the masses. The importance of true randomness and the difficulties to have it correctly with quantum effects or nuclear decay, is only snake oil advertising and customer retention. It may not be in the online gaming site's or casino's best interest to have a fair solution always. In the multi-billion dollar gaming industry they might give some bucks to talented programmers to taint the RNG just enough to make play more exciting at their (web)site verses another. As a not regular, but a frequent online player I have seen dealt pairs and suited connectors or quads way to often...
The minimum weak criteria for randomness are the same for TRNGs and PRNGs
======================================================
UNIFORMITY : Basic and trivial criterion.
PATTERNLESS SEQUENCE: To obtain patternless sequence might need many samples. See the attached picture
that shows the random walk of the first 1 million digits of Pi. Chaotic, yes, but not uniform. Believe it or not, the listing of the firmware code for Popeller II. is hiding somewhere in the digits of Pi, not in the first million, though.
Slight difference between True and Pseudo random numbers
=========================================
SUMMATION: The sum of two consecutive numbers is equally likely to be even or odd.
The big difference between True random and all-bit Pseudo random numbers
====================================================
DUPLICATION: If you have ever thrown dice or a coin more than once, then you know what I mean. A truly random number has nothing to do with the previous one, and it can be the same. In a sequence it can be often the same. Consequently, a surprisingly large portion of the numbers will not appear in a finite length truly random sequence. 32-bit pseudorandom outcomes of conventional PRNGs never equals the next one, and the farther the repetition, the more prouder the programer, and the more fishy the PRNG is in respect of true randomness.· PRNGs are constructed and even advertised as having all possible outcomes in the serie and only once. That is ridiculously not random again. It is great for testing, but has nothing to do with randomness. For 32-bit truly random numbers I am trying to figure out how many numbers should not appear in a 2^32 long serie. My first result is so surprisingly large, that I better check my calculations before posting the result. These all-bit PRNGs clearly and badly need some transformation to make that duplications and missing numbers possible. So, I will use only the upper 16- bit of the outcome of SPINs PRNG, because of (not only) this. This 16-bit numbers will be scaled to the integers [noparse][[/noparse]0, 999] for the tests.···
Since with randomness·you can be never sure, there is no known way to prove it 100%. There is a pretty strong argument that randomness can't even be tested properly, and the tests we have are really only useful when applied to very large sets. As a rule of thumb, you need about n-squared data points to achieve a general confidence of (1-1/n) in their overal results of a test set. So I recommend to test at least 10_000 outcomes for the RNGs to achieve 99% general confidence. This overall and conservative confidence shouldn't be confused with the individual confidence figure of the randomness of a generator at the individual tests. It says only, that if a sequence of 10_000 numbers passed all tests, it's only about 0.99 probable that the sequence is random.
All the proposed tests of BUST are easily calculated, fast and use only a small amount of HUB RAM. So we can fire a salvo of the BUST battery when we need.
Very simple tests to begin with
======================
ARITHMETIC MEAN TEST
Should be close to 499.5.
SUMMATION TEST
The sum of two consecutive numbers is equally likely to be even or odd.
REVERSE ARRANGEMENT TESTS
This test is stringent test of randomness. Here the number of reversly arranged pairs is counted. This test is particularly good at detecting monotonic drifts in the data. It is calculated for 100 samples, 100 times. The number of reversly arranged pairs shoud be about 2500 in each set.
DUPLICATION TEST
If 1,000 numbers (0, 1,... 999) are truly randomly generated, some will be duplicated. Roughly 368 numbers will not appear. Large deviation from this is a suspect of non or pseudo randomness. This test will be done ten times in sequence for the 10_000 data.
A bit more complicated tests, that worth of doing
==================================
CHI-SQUARED TEST OF UNIFORMITY
The chi-squared test is a commonly used test for the uniformity of random data, and is extremely sensitive to errors in random sequence generators. I propose this basic statistics for uniformity with ten equally
sized intervals.
BENFORD's LAW TESTS FOR THE SUMS, PRODUCTS AND RATIOS
The sum, product and ratio of truly random numbers in sequence follows Benford's law. This law, also called the first-digit law, says that in lists of numbers from many real-life sources of data, the leading digit is distributed in a specific, non-uniform way. For our random decimal numbers from 0 to 999, according to Benford's law, about 31% of the sums, products or ratios have 1 as the first digit, 19% have 2, and only 5% have 9 as a first digit. Benford's law has been found to apply to many sets of natural (such as river lengths) or human related data, including income tax or stock exchange. This law works on financial figures throughout the world, although the same data are expressed in different currencies. So, it can help the tax office to audit income tax documents, wherever you are.
··
TEST OF RUNS ABOVE AND BELOW THE MEDIAN
1000 numbers of whole sequence is collected in HUB. Median value is determined. Observations in the sequence of numbers greater than or less than the median of the sequence are marked. Data with median value are left out. Smaller ones are marked with - and larger ones are marked with +. A run of length r is r consecutive +, or r consecutive -. Too few runs, too many runs, a run of excessive length, etc., are very rare in truly random sequences, therefore their frequent occurance can serve as statistical criteria for the rejection of true randomness. Also, these criteria are related with each other. Too few runs means that some runs are too long; too many runs results in short runs. So we can be only concerned with the total number of runs. This test is done 10 times to cover the 10_000 random numbers.
TEST OF RUNS-UP AND RUNS-DOWN
Here a run is a series of increasing values or a series of decreasing values. The number of increasing, or decreasing, values is the length of the run. Runs-Up and Runs-Down are far more powerful than they may appear. In contrast to many other randomness tests, Runs-Up and Runs-Down can expose serial correlations, to some extent.
All these test are easy to set up with the Propeller. They do not prove or reject true randomness, as I mentioned, they just increase the credibility of well performing generators and BUSTs of bad ones. You can check with them, for example, the quality of your DIY physical source of entropy. Some of them can be written in PASM to be very fast. With simple and fast tests in COGs you can detect the presence or absence of a weak signal in a very noisy channel. Or, you can verify the correct filtering of your sensor's data. When you remove the filtered data from the original, the remaining values should be as random as possible.
Waiting for your comments, help and ideas for more simple or more effective tests
Cheers,
Istvan
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Intentionally Left Blank
Post Edited (cessnapilot) : 9/10/2009 8:19:19 PM GMT
There were several threads on this forum relating to the randomness or random numbers. Those, that I have seen, boiled down for me that with SPIN one can only make Pseudo Random Generators (PRNGs) and with Chip Gracey's RealRandom object we can make True Random Number Generators (TRNGs). The behavior of Q_True_Rnd procedure in SPIN_TrigPack object clearly contradicts to this simplification. We can make TRNGs with only SPIN code plus CNT without extra COG for RealRandom. And this is good.
I tried with
··1 DemoBoard
··2 PropSTICK with RS232
··2 PropRPM
··4 Propeller Proto Board
+6 40DIP Propeller chip (plugged in a PropRPM board, only 3 pins folded back, all were repairable.)
and all showed (up till now) true random behavior with the TRNG generator of SPIN_TrigPack object. This behavior of the Propeller may go away in the future with the new batches, but I experienced far too often the truth of the aviation wisdom
"Equipment problems that go away by themselves will come back by themselves."
This true randomness ability of Prop with SPIN only is, however, not a problem at all, but a great feature that we can use· for our advantage. I am searching here for effective statistical tests of true randomness that are also very simple to carry out with Propeller. I propose some test at the end of this post. From these tests and from your suggestions it may evolve a demanding, fast and easy to use randomness check procedure collection. The basic DESIGN REQUIREMENT for this battery of code IS ONLY COMMON SENSE. And that is not easy, since, as you might have noticed, that common sense is not so common in our over-advertised and over-patented world where common sense is always attacked fiercely. And that means, that we have to take extreme care of it.
Evidence based statistical testing
=========================
Advertised test suits for randomness are not easy to program with the Propeller for simple and quick use. They do not even worth of implementing. Many tests in 'official' test suits need much more explanation to understand their results than the non-randomness they might recover. I shall avoid here these artificial mathematical amok in several dimensions. Usually the more complex of a test the more weakest its decision power. Complicated test suits may even contain errors that are not easy to discover. After many years of intensive use by hundreds of professional mathematicians, they recovered errors even in NIST test suit recently. The “"Ferrenberg affair" showed that even a large battery of advertised statistical test suits is a scrap in detecting imperfections, that only an application can reveal. So I shall keep the Propeller test suit as a simple, understandable and robust first line of defense that protects you when 'amateurish' random numbers are proposed or generated for you. Beside outcomes of RNGs you can check numbers that come from everyday's life as company prices, stock exchange data, numbers in reports submitted to you or fish counts in natural waters. As you will see, it is easy to build a DIY true random number generator with real physical source of entropy. With the here proposed Battery of Useful and Simple Tests (BUST) you can verify or bust any PRNG or TRNG generators with a reasonable certainty. But, remember that only the concrete an succesfull application can stamp the· final acceptance mark on any random number sequence.·····
A simple definition to avoid philosophy:
============================
If you keep in mind that (pseudo or real) random numbers are mostly about not being predictable by the user of your application rather than worrying about any deep philosophy of what randomness is then it all becomes much simpler:
A sequence of numbers can be treated as truly random for many purposes for a given user in a given circumstance, if it isn't possible to make a profit on you, or on the program, by the user betting on them!
Relativity (as always):
=================
Randomness is not only uncertain but·a relative idea, too. It never refers to a single number, and for a series of numbers it is not the same for every person. For the programer, the sequence from a congruent random number generator (CRNG) in his application is absolutely predictable. For the user of the program the sequence is random. An average user (like me) with only restricted and slow organic memory, cannot figure out the generator. A determined mathematical analyst, however, can collect a small sample of the output of a PRNG, and by solving some linear equations, can work out the generator, and therefore predict, the entire sequence. The famous Mersenne Twister is pretty easy to break for a bold analyst, 'just' 634 outputs are needed to predict it.
Randomness all around (if you need it you can have it)
=====================================
If you want to use secure pseudo or true random numbers in your application, I think it's a really BAD idea to use known methods. So many programmers treat PRNGs as something to start once and then use to get many random bits out of without care. This is wrong. A PRNG has input also an output. You should be constantly feeding the input with anything even remotely random that you can find. Keystroke timings, bytes received at UART, RF module outcome from an empty channel, CPU cycle counts. Everything. Anything. All the time. Nobody will brake or predict that sequence.
DIY Physical sources of randomness
=========================
You don't need nuclear decay and GM counter, although they are great to play with from a distance. If you do not live in a deep granite cavern, a cheap GM counter and the cosmic radiation will do. My radiation monitor 4/4RC (S.E. Int. Inc) gives about 40-70 counts / minute on my table (0.7 uSv/hr). The mic of the DemoBoard picks it up easily. One can take the CNT difference between cosmic events to XOR with the seed, for example. With BUST we shall be able to test that generator, or we can even test the sequence of those time differencies. If we detect some definite non-randomness in those ticks, than E.T. is probably· using sharp and far penetrating cosmic ray beams, focused by gravitational lenses, instead of weak and diffuse RF waves to message some greetings. If you do not like to hear or know about anything 'nuclear' you can use many other source of randomness around you. Actual random number generators are pretty cheap. Place a microphone close to the power supply fan of a PC, and read the sound coming in with the Prop. Filter out all but the very highest frequency components, and you have a strong source of randomness. Another source that is available to everyone, is environmental RF noise. I mentioned that a signal seeking RF module is a· great generator of random byte streams. Sample this several times, and combine the results into a seed, wherever possible. If there are transmitting stations nearby on the channel, change channel or chop antenna. I tried an RF RxTx modul (RXQ2) with 256 channels from 422.4 MHz. It checks for the presence of the noise on the channel with reading data at high baud rates. From noisy channel (continuous data with a running average close to 127,5 in some randomly selected short intervals) it reads some random bytes from random positions. It mixes the actual seed of a PRNG with these random bytes, and than changes the Rx channel randomly from the results of the generator. This "entropy read" injects fresh blood into the RNG and is repeated in random intervals. That RF module costed only 10$. If the enemy is so close to you that he can silence with a strong RF transmission all of those 256 channels of the properly shielded receiver, look around you and catch him.
True randomness for you in the industry (insert coin first, than you will have fair chances)
=============================================================
All the much ado on how difficult to create truly random numbers seems to me to be smoke in eyes of the masses. The importance of true randomness and the difficulties to have it correctly with quantum effects or nuclear decay, is only snake oil advertising and customer retention. It may not be in the online gaming site's or casino's best interest to have a fair solution always. In the multi-billion dollar gaming industry they might give some bucks to talented programmers to taint the RNG just enough to make play more exciting at their (web)site verses another. As a not regular, but a frequent online player I have seen dealt pairs and suited connectors or quads way to often...
The minimum weak criteria for randomness are the same for TRNGs and PRNGs
======================================================
UNIFORMITY : Basic and trivial criterion.
PATTERNLESS SEQUENCE: To obtain patternless sequence might need many samples. See the attached picture
that shows the random walk of the first 1 million digits of Pi. Chaotic, yes, but not uniform. Believe it or not, the listing of the firmware code for Popeller II. is hiding somewhere in the digits of Pi, not in the first million, though.
Slight difference between True and Pseudo random numbers
=========================================
SUMMATION: The sum of two consecutive numbers is equally likely to be even or odd.
The big difference between True random and all-bit Pseudo random numbers
====================================================
DUPLICATION: If you have ever thrown dice or a coin more than once, then you know what I mean. A truly random number has nothing to do with the previous one, and it can be the same. In a sequence it can be often the same. Consequently, a surprisingly large portion of the numbers will not appear in a finite length truly random sequence. 32-bit pseudorandom outcomes of conventional PRNGs never equals the next one, and the farther the repetition, the more prouder the programer, and the more fishy the PRNG is in respect of true randomness.· PRNGs are constructed and even advertised as having all possible outcomes in the serie and only once. That is ridiculously not random again. It is great for testing, but has nothing to do with randomness. For 32-bit truly random numbers I am trying to figure out how many numbers should not appear in a 2^32 long serie. My first result is so surprisingly large, that I better check my calculations before posting the result. These all-bit PRNGs clearly and badly need some transformation to make that duplications and missing numbers possible. So, I will use only the upper 16- bit of the outcome of SPINs PRNG, because of (not only) this. This 16-bit numbers will be scaled to the integers [noparse][[/noparse]0, 999] for the tests.···
Since with randomness·you can be never sure, there is no known way to prove it 100%. There is a pretty strong argument that randomness can't even be tested properly, and the tests we have are really only useful when applied to very large sets. As a rule of thumb, you need about n-squared data points to achieve a general confidence of (1-1/n) in their overal results of a test set. So I recommend to test at least 10_000 outcomes for the RNGs to achieve 99% general confidence. This overall and conservative confidence shouldn't be confused with the individual confidence figure of the randomness of a generator at the individual tests. It says only, that if a sequence of 10_000 numbers passed all tests, it's only about 0.99 probable that the sequence is random.
All the proposed tests of BUST are easily calculated, fast and use only a small amount of HUB RAM. So we can fire a salvo of the BUST battery when we need.
Very simple tests to begin with
======================
ARITHMETIC MEAN TEST
Should be close to 499.5.
SUMMATION TEST
The sum of two consecutive numbers is equally likely to be even or odd.
REVERSE ARRANGEMENT TESTS
This test is stringent test of randomness. Here the number of reversly arranged pairs is counted. This test is particularly good at detecting monotonic drifts in the data. It is calculated for 100 samples, 100 times. The number of reversly arranged pairs shoud be about 2500 in each set.
DUPLICATION TEST
If 1,000 numbers (0, 1,... 999) are truly randomly generated, some will be duplicated. Roughly 368 numbers will not appear. Large deviation from this is a suspect of non or pseudo randomness. This test will be done ten times in sequence for the 10_000 data.
A bit more complicated tests, that worth of doing
==================================
CHI-SQUARED TEST OF UNIFORMITY
The chi-squared test is a commonly used test for the uniformity of random data, and is extremely sensitive to errors in random sequence generators. I propose this basic statistics for uniformity with ten equally
sized intervals.
BENFORD's LAW TESTS FOR THE SUMS, PRODUCTS AND RATIOS
The sum, product and ratio of truly random numbers in sequence follows Benford's law. This law, also called the first-digit law, says that in lists of numbers from many real-life sources of data, the leading digit is distributed in a specific, non-uniform way. For our random decimal numbers from 0 to 999, according to Benford's law, about 31% of the sums, products or ratios have 1 as the first digit, 19% have 2, and only 5% have 9 as a first digit. Benford's law has been found to apply to many sets of natural (such as river lengths) or human related data, including income tax or stock exchange. This law works on financial figures throughout the world, although the same data are expressed in different currencies. So, it can help the tax office to audit income tax documents, wherever you are.
··
TEST OF RUNS ABOVE AND BELOW THE MEDIAN
1000 numbers of whole sequence is collected in HUB. Median value is determined. Observations in the sequence of numbers greater than or less than the median of the sequence are marked. Data with median value are left out. Smaller ones are marked with - and larger ones are marked with +. A run of length r is r consecutive +, or r consecutive -. Too few runs, too many runs, a run of excessive length, etc., are very rare in truly random sequences, therefore their frequent occurance can serve as statistical criteria for the rejection of true randomness. Also, these criteria are related with each other. Too few runs means that some runs are too long; too many runs results in short runs. So we can be only concerned with the total number of runs. This test is done 10 times to cover the 10_000 random numbers.
TEST OF RUNS-UP AND RUNS-DOWN
Here a run is a series of increasing values or a series of decreasing values. The number of increasing, or decreasing, values is the length of the run. Runs-Up and Runs-Down are far more powerful than they may appear. In contrast to many other randomness tests, Runs-Up and Runs-Down can expose serial correlations, to some extent.
All these test are easy to set up with the Propeller. They do not prove or reject true randomness, as I mentioned, they just increase the credibility of well performing generators and BUSTs of bad ones. You can check with them, for example, the quality of your DIY physical source of entropy. Some of them can be written in PASM to be very fast. With simple and fast tests in COGs you can detect the presence or absence of a weak signal in a very noisy channel. Or, you can verify the correct filtering of your sensor's data. When you remove the filtered data from the original, the remaining values should be as random as possible.
Waiting for your comments, help and ideas for more simple or more effective tests
Cheers,
Istvan
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Intentionally Left Blank
Post Edited (cessnapilot) : 9/10/2009 8:19:19 PM GMT
bmp
931K
Comments
Will require getting a nice big batch of numbers out of the Prop into your PC though.
Edit: Now that I have actually read your post it looks like you have already rejected this.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.
Post Edited (heater) : 9/10/2009 8:21:42 PM GMT
And every PRNG fails spectacularly the test put forth by Donald Knuth: If your RNG can't spit out a string of 20 zeroes under any circumstances, it isn't random. That is a perfectly valid and randomly possible result just as likely as any other particular random 20-sample string you might consider important.
TRNG's are notoriously difficult to debug; some of the best use nuclear sources but are prone to "un-errors" from electronic noise. The PLL jitter RNG is actually about as robust as they get, and not likely to go away in a future chip enhancement since it's a behavior of PLL's regardless of how they're implemented. You do need to exercise caution as to just how much randomness is there, just as you can regard a relatively crude PRNG as pretty random if it's 32 bits and you're masking off the lower 8, but it's not so random if you're trying to simulate gigabytes of noise as opposed to data from the SETI.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Nyamekye,
From a practical perspective, I'm putting together a wireless mesh and I want different time delays between boards so they don't all talk at the same time. So a true random seed is needed (even if the delays are then only psueudo random).
A reverse biased transistor junction may be one of the cheaper options www.cryogenius.com/hardware/rng/
Actually, thankyou for posting this thread. I needed some motivation to go searching for hardware random number generators and these transistor circuits only cost a few cents.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
www.smarthome.viviti.com/build
It seems like a paradox that the most random numbers come from precise timing of conscious actions,
and that machines are so deterministic. Unbiased noise is a rare phenomenon.
Here's an idea: Reversi chips rolled in a drum and then funneled into a queue, photoelectrically read as a random number.
But how different is it from a gray code on a fast turntable, read by a strobe as needed? Maybe faster and more durable.
"From a practical perspective, I'm putting together a wireless mesh and I want different time delays between boards so they don't all talk at the same time. So a true random seed is needed (even if the delays are then only psueudo random)."
How about Time Division Multiple Access? (Based on the net address of each board.)
uploads.propmodule.com/mctrivia___OTP00000.BIN
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
propmod_us and propmod_1x1 are in stock. Only $30. PCB available for $5
Want to make projects and have Gadget Gangster sell them for you? propmod-us_ps_sd and propmod-1x1 are now available for use in your Gadget Gangster Projects.
Need to upload large images or movies for use in the forum. you can do so at uploader.propmodule.com for free.
Thanks for the responses, ideas and suggestions. The real question is, however, remained without answer. I quote from the "RealRandom Object" of Chip Gracey
"A real random number is impossible to generate within a closed digital system. This is because there are no·reliably-random states within such a system at power-up, and after power-up, it behaves deterministically.·Random values can only be 'earned' by measuring something outside of the digital system.
In your programming, you might have used 'var?' to generate a pseudo-random sequence, but found the same·pattern playing every time you ran your program. You might have then used 'cnt' to 'randomly' seed the 'var'. As long as you kept downloading to RAM, you saw consistently 'random' results. At some point, you probably·downloaded to EEPROM to set your project free. But what happened nearly every time you powered it up? You were probably dismayed to discover the same sequence playing each time! The problem was that 'cnt' was always·powering-up with the same initial value and you were then sampling it at a constant offset. This can make you wonder, "Where's the end to this madness? And will I ever find true randomness?".············································································································································
The madness is maybe over. That we shall see later, but the un-answered real question is here already:
How is it possible, that within a closed digital system, like Propeller with the SPIN_TrigPack object written in SPIN, we have TRUE RANDOM sequences from the Q_True_Random procedure after each power up or reboot?
·
I may say TRUE RANDOM here, since up till now the random sequences of Q_True_Rnd passed all of the implemented tests (4 up till now) of the BUST's battery with a high level of confidence of being TRUE RANDOM.
After I found out this feature of Propeller I consulted with an expert mathematician and a statistician to ask them about simple and powerful tests of randomness. Both said almost the same. One can do it for 10K-100K samples with simple test (like runs, missing numbers, Bensford, Chi-squared), but the rule of thumb probability of being correct will be about only 0.99 or so. And I shall need many-many millions of samples to be a little bit more certain. I decided that 0.99 certainty (~10K samples) is more than enough for a practical and common sense driven design embedded applications, and I started to look after these tests in the literature. I found beside the proposed ones another simple, strong tests to differentiate between pseudo and true random sequences. I listed all the suggested or found practical tests of randomness in my first post. They can be set up simply with SPIN_TrigPack, using about 2K HUB registers for storage. I am sure that there are some others, let us know if you know one.··
The statistician mentioned one thing that I remember. If two random sequences pass the same set of tests successfully with the preset level of Ho confidences, there is not too much reason to say that this one or that one is more truly random. More he said, that he would make those 10K tests at least 10 times.
The moral of the story:
- We can make very powerful but simple statistical tests of randomness with the Prop itself.
- If a sequence (whatever the source) passes these tests successfully, it can be regarded as practically true random.
So, there is an open question, and there is a probably useful Q_BUSTER object in statu nascendi.
I am sure with 99% confidence that the madness will be over, soon. Until that it would be great if somebody could answer the real question.
Cheers,
istvan·
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Intentionally Left Blank
It's that fundamental unknowableness about it, is it random, is it not, is biased, is it not, that bugs people. The fact that you can never be sure that what you have got is truly random. Or, how random is random enough for a given application?
Fascinating.
WARNING: Under British law you can end up in jail for not handing over the keys to encrypted data the police want to look at on your computer. A file full of 100s of kilo/mega bytes of random numbers could well be assumed to be encrypted data...
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.
CP you're probably aware of this, but there is a class of software for analyzing Blackjack card-counting strategy called "simulators" which work by playing millions or even billions of hands according to the given game rules and strategy, and tabulating the results.· These things will go through many, many cycles of any PRNG in the course of a run, and it's essential that they not settle into any kind of pattern or the results will be screwed up in ways that can cost real money to the people who depend on them.
That said, the people who develop such software made an interesting discovery around 1990, which is that flaws tend to afflict only single methods in a particular way.· If you use two likely flawed PRNG's to do the same analysis and you get the same result, your results are probably OK.· If you get a flier, it's probably a PRNG artifact and you try more PRNG's (or other RNG sources) looking for agreement.
PRNG's have one huge advantage for programmers, which is that they can be rest and re-run through the same sequence of numbers; this can be essential for the debugging of new software.· The only way to do this with TRNG's is to record the random numbers so they can be reused; while this is usually practical with today's technology, in 1990 it involved quantities of RAM and fixed disk storage that were usually not available.
heater : Diehard is OK but it needs millions of samples. To bring down a primitive pseudorandom or false true random sequence you do not need that big anti-aircraft gun, a Desert Eagle Mark XIX with .50 Action Express BUST will do. I wonder how mctrivia will prove for the police that those 126 MBytes did come from RealRandom only. They will·tell him to repeat the sequence or go to jail.
localroger: It is just the frequency test that they found errors in the NIST confidence levels. After that I'm not sure what is the correct value. The proposed battery only needs simple arithmetic and comparisons and use well established and agreed statistical tables. In the first round they will be enough. Actually I propose not to test PRNGs but to detect them to be discarded. If a good PRNG after a proper transformation behaves like a TRNG for the tests, that is OK. PRNGs are good for testing as you mentioned. Testing without them would be a nightmare. I tested the kalman filters first with SPIN's PRMG before proving them with Chip's RealRandom. Donald Knuth has right. The digits of Pi can contain 20 or more zeroes in sequence. That's because it is random. A coin can do it with about 1 ppm probability. I lost last year more than 60 EUR in a Bled Casino, when·6 Rouge came in sequence.
Dr_Acula: The mentioned RSQ2 GFSK multichannel radio transceiver is maybe good for your project. It works from 422.4 up to 448 MHz in 100 kHz steps. I tested it and it really works from 250 m, 100 kbps. It has adjustable transmitter levels and operates in network modes, too. Just an idea.
VIRAND: Those reversi chips are really hard to predict. It's a lottery. This and the gray code on a fast (not in synchron) turntable are great candidates for TRNGs. But, it is not easy to make a hand held device from them. What is time division multiple access? I am getting into more complications with BlueTooth these days. It's my fault, probably.
mctrivia: After BUST v1.0 will be ready, I will check some randomly chosen portions of that sequence. The whole thing would take months, however. The ansi c source code of Diehard can be downloaded, as far as I know. By the way, have you tested those data? I advise you to change the bytes at every multiple 2M position of that sequence into a message like "I love you darling, let us put our love to the test." so as to just avoid jail. That will not spoil randomness tests, I suppose.·
I replaced the PRNG in the PropHold'em with the SPIN-TRNG.·I attached the·dealer code that calculates the table statistics·I·used to·parameter up the·gameplay engines of COGs Alice, Bob and Cecil.
Cheers,
Istvan
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Intentionally Left Blank
The sun controls it all.
http://news.stanford.edu/news/2010/august/sun-082310.html
I think the noisy transistor junction is a pretty good
random source. Wish they could run on 5v though.
The ones I have seen all need 12-18v
Holly
Back in my day, a geranium transistor was noisy enough on it's own. Zener diodes do not go much above 5 Volts, after that they are avalance diodes. I do not know how that would affect the noise action.
What, they retired ERNIE?
Hmm..., seems they have some new model. Do you have a link for your proof because this page refutes it http://www.nsandi.com/products/pb/surprisingfacts
Holly, that is one of my all time favourite electronic circuits. It's so, well, weird. I've built a few of those.
Do not let the facts get in the way of a good story. Thats's the grumps motto.
I suppose it could be just statistics, bless.
These people seem to indicate that a true Zener is better for quantum effects.
http://people.seas.harvard.edu/~jones/es154/lectures/lecture_2/breakdown/breakdown.html
http://en.wikipedia.org/wiki/Premium_Bond
I know that some RF bridges used Gas discharge for a wideband source.