Difference between revisions of "Pseudo random number generators"
From ScienceZero
| Line 1: | Line 1: | ||
| − | + | Some [[linear feedback shift registers]] are excellent pseudo random number generators. | |
| + | |||
| + | ==ARM== | ||
| + | The [[ARM]] instruction set makes it simple to make short generators of high quality. | ||
| + | ===Shortest possible=== | ||
| + | A single instruction generator, it was selected after testing all possible instructions of a suitable type: | ||
:RSB R0,R0,R0,ROR #21 | :RSB R0,R0,R0,ROR #21 | ||
| Line 9: | Line 14: | ||
*Monte Carlo value for Pi is 3.143 189 714 (error 0.05 percent). | *Monte Carlo value for Pi is 3.143 189 714 (error 0.05 percent). | ||
*Serial correlation coefficient is -0.000 131 (totally uncorrelated = 0.0). | *Serial correlation coefficient is -0.000 131 (totally uncorrelated = 0.0). | ||
| + | |||
| + | ===High quality, long period=== | ||
| + | :EOR R0,R0,R1 | ||
| + | :ADD R1,R1,R0,ROR #16 | ||
| + | |||
| + | |||
| + | ==PIC== | ||
| + | The [[PIC]] has a limited instruction set and develop platform that makes it difficult to develop good generators. | ||
| + | ===High quality, long period=== | ||
| + | This is the same as the ARM one but using two 8 bit variables instead of two 32 bit variables. | ||
| + | :MOVFW R1 | ||
| + | :XORWF R0 | ||
| + | :SWAPF R0,W | ||
| + | :ADDWF R1 | ||
| + | |||
| − | |||
[[Category:Computing]] | [[Category:Computing]] | ||
Revision as of 12:41, 21 March 2008
Some linear feedback shift registers are excellent pseudo random number generators.
Contents
ARM
The ARM instruction set makes it simple to make short generators of high quality.
Shortest possible
A single instruction generator, it was selected after testing all possible instructions of a suitable type:
- RSB R0,R0,R0,ROR #21
The analysis of 40 000 000 bytes worth of the least significant byte:
- Entropy = 7.999 985 bits per byte.
- Optimum compression would reduce the size of this 40 000 000 byte file by 0 percent.
- Chi square distribution for 40 000 000 samples is 810.80, and randomly would exceed this value 0.01 percent of the times.
- Arithmetic mean value of data bytes is 127.4731 (127.5 = random).
- Monte Carlo value for Pi is 3.143 189 714 (error 0.05 percent).
- Serial correlation coefficient is -0.000 131 (totally uncorrelated = 0.0).
High quality, long period
- EOR R0,R0,R1
- ADD R1,R1,R0,ROR #16
PIC
The PIC has a limited instruction set and develop platform that makes it difficult to develop good generators.
High quality, long period
This is the same as the ARM one but using two 8 bit variables instead of two 32 bit variables.
- MOVFW R1
- XORWF R0
- SWAPF R0,W
- ADDWF R1
