32 bit random numbers
-
- Super Gold Card
- Posts: 715
- Joined: Mon Nov 24, 2014 2:03 pm
32 bit random numbers
Hi Folks,
Does anyone know how to generate accurate 32_bit random numbers ?
I have been toying with the idea for decades, and have now come up with a fully tested routine, (in fact for numbers up to 31 bits, as 32 bits imply negative numbers).
Tested statistically, It works fine on QPC2 and my SGC QL, (although the latter runs 124 times slower !)
The worst case for numbers (in a range) is 3 times slower than the best case.
It would be interesting to know how it compares to other routines ?
I will put it on the forum after a little more tweaking of the associated graphical output, (which is not too easy to scale with 31 bit randoms).
Steve.
__________
Does anyone know how to generate accurate 32_bit random numbers ?
I have been toying with the idea for decades, and have now come up with a fully tested routine, (in fact for numbers up to 31 bits, as 32 bits imply negative numbers).
Tested statistically, It works fine on QPC2 and my SGC QL, (although the latter runs 124 times slower !)
The worst case for numbers (in a range) is 3 times slower than the best case.
It would be interesting to know how it compares to other routines ?
I will put it on the forum after a little more tweaking of the associated graphical output, (which is not too easy to scale with 31 bit randoms).
Steve.
__________
Re: 32 bit random numbers
Park-Miller is a 31 bit Linear Congruent Random Number Generator of the form:
s = ( s * p1 + P2 ) % N
where
P1 = 16807 (i.e. 7^5)
P2 = 1
N = 2147483647 (i.e. 2^31 - 1)
Note that % is the modulus operator (don't know what it is in SuperBASIC)
s = ( s * p1 + P2 ) % N
where
P1 = 16807 (i.e. 7^5)
P2 = 1
N = 2147483647 (i.e. 2^31 - 1)
Note that % is the modulus operator (don't know what it is in SuperBASIC)
-
- Super Gold Card
- Posts: 715
- Joined: Mon Nov 24, 2014 2:03 pm
Re: 32 bit random numbers
Hi Bwinkel,
Congruent random number generators are for PSEUDO randoms... We want true random numbers.
The method I have devised could be adopted for ANY number of bits, but not on QPC2. ( But possible in C++ , on 64bit machines or better).
Is the park-Miller routine available for QL systems ?
What are DES & AES ?
Steve.
__________
Congruent random number generators are for PSEUDO randoms... We want true random numbers.
The method I have devised could be adopted for ANY number of bits, but not on QPC2. ( But possible in C++ , on 64bit machines or better).
Is the park-Miller routine available for QL systems ?
What are DES & AES ?
Steve.
__________
- XorA
- Site Admin
- Posts: 1366
- Joined: Thu Jun 02, 2011 11:31 am
- Location: Shotts, North Lanarkshire, Scotland, UK
Re: 32 bit random numbers
Encryption algorithms, you feed a little bit of entry to them, and because of the way they work they must increase the entropy of the output (otherwise they would be too easy to crack).stevepoole wrote:Hi Bwinkel,
Congruent random number generators are for PSEUDO randoms... We want true random numbers.
The method I have devised could be adopted for ANY number of bits, but not on QPC2. ( But possible in C++ , on 64bit machines or better).
Is the park-Miller routine available for QL systems ?
What are DES & AES ?
I've worked on certified security systems where all the randows were generated by this method.
Given that modern CPUs tend to contain true random generators and AES in hardware its a really quick and easy way to generate lots of high entropy data!
Re: 32 bit random numbers
If you have invented a "true random number" generator entirely in software (without an external source of entropy), you might have solved a problem that generations of computer scientists have proven to be unsolvable (a deterministic machine like a CPU can't produce non-deterministic results).stevepoole wrote: Congruent random number generators are for PSEUDO randoms... We want true random numbers.
ʎɐqǝ ɯoɹɟ ǝq oʇ ƃuᴉoƃ ʇou sᴉ pɹɐoqʎǝʞ ʇxǝu ʎɯ 'ɹɐǝp ɥO
-
- Super Gold Card
- Posts: 715
- Joined: Mon Nov 24, 2014 2:03 pm
Re: 32 bit random numbers
Hi,
Here is the QL 31bit random number generator, which does not directly use a congruency method. It is deterministic, but only uses RND(1) in its core.
_______
UNZIP and LOAD, (120 QL=1 or QL=0 for emulators, 210 mn & mx set test rangs, m is number of test cycles. RUN !!
_______
At top_left see the numbers generated, by the lower & upper limits, Bottom_left see number of bits and time per test_cycle.
_______
upper and lower white lines show the mn & mx ranges, horizontal speccles show trace of rank_values, ( I have improved but complicated statistical bar charts).
_______
timings are done to compare ranges and machines relatively, No way yet to optimise loop2 without getting results horribly biased.
_______
It is not as fast as congruency methods, but I cannot detect any biases, and it is available for QL systems NOW.
_______
Steve.
Here is the QL 31bit random number generator, which does not directly use a congruency method. It is deterministic, but only uses RND(1) in its core.
_______
UNZIP and LOAD, (120 QL=1 or QL=0 for emulators, 210 mn & mx set test rangs, m is number of test cycles. RUN !!
_______
At top_left see the numbers generated, by the lower & upper limits, Bottom_left see number of bits and time per test_cycle.
_______
upper and lower white lines show the mn & mx ranges, horizontal speccles show trace of rank_values, ( I have improved but complicated statistical bar charts).
_______
timings are done to compare ranges and machines relatively, No way yet to optimise loop2 without getting results horribly biased.
_______
It is not as fast as congruency methods, but I cannot detect any biases, and it is available for QL systems NOW.
_______
Steve.
Re: 32 bit random numbers
Ah, didn't know you want true randomness. Generally speaking those aren't as useful in computing as pseudo random ones are since there is no repeatability and for cryptography and software engineering you want that. That said, true randomness is pretty intriguing and fun to implement. It will be neat to see your implementation.stevepoole wrote:Hi Bwinkel,
Congruent random number generators are for PSEUDO randoms... We want true random numbers.
The method I have devised could be adopted for ANY number of bits, but not on QPC2. ( But possible in C++ , on 64bit machines or better).
It has not been implemented in any ROM if that's what you are asking. I think I had it briefly in ZXSimulator but went with a 16-bit equivalent that matches what the ZX81 used.stevepoole wrote: Is the park-Miller routine available for QL systems ?
DES stands for Data Encryption Standard and AES stands for Advanced Encryption Standard. They are both block ciphers with AES being the current standard used throughout the internet/web. Neither is a pseudo random number generator and neither directly uses one in their computation but may apply one when encrypting multiple blocks (various techniques for that).stevepoole wrote: What are DES & AES ?
Steve.
__________
Here's a good reference on cryptography (I use it in an introductory cryptography course). It briefly covers random number generators (pseudo, not real) but gives complete description of DES and AES. DES could be implemented on a QL as it is a pretty straightforward bit-twiddling algorithm (bit twiddling with purpose :-/)
These are the relevant chapters that cover the topics in this post (the remaining chapters cover public-key encryption.
- XorA
- Site Admin
- Posts: 1366
- Joined: Thu Jun 02, 2011 11:31 am
- Location: Shotts, North Lanarkshire, Scotland, UK
Re: 32 bit random numbers
Hell no, crypto really likes true random for exactly the opposite of that reason.repeatability and for cryptography and software engineering you want that
Re: 32 bit random numbers
The problem with true randomness is that when you encrypt something you can't decrypt it. What you want is the appearance of true randomness. There are lots of tests in the field of cryptography (mathematics) to address that. But in the end, if you can'f find the needle in the haystack then it's kind of worthless. So you may be conflating the idea o true randomness with the idea of pseudo randomness having all the properties of true randomness, which is what you want.XorA wrote:Hell no, crypto really likes true random for exactly the opposite of that reason.repeatability and for cryptography and software engineering you want that
Remember that cryptography is an algorithmic solution and implemented in software. Hardware implementations are just more efficient implementations of that but AES is implemented in your version of SSH and by that nature they can't be implementing true randomness, just the appearance of it.