(then repeat)
Above is a simple version of the engine. The engine is currently stopped at the RED bit. The red bit is toggled. ie; it was 0 so it becomes 1. At the same time, the following BLUE bit is transposed (swapped) with whatever bit was last held inside the engine (in the blue circle). In this case they are both 1 bits, that does not matter, they are swapped anyway.
Next the engine rotates to the next "cylinder", which is 5. So the engine moves 5 bits forward to the ORANGE bit. Then the process is repeated; the one (orange) bit will be toggled, and the bit directly after it will be transposed with the bit held inside the engine.
After that, the engine will move 7 bits forward and repeat. etc etc.
The above simple engine actually worked very well in testing. But to completely remove any possibility of backward engineering the random data I added a simple quick system so the engine could also scramble ITSELF;
The Black RNG Engine
Above is the final version of the engine. It is basically the same as the first simple engine. However it now has an extra move value stored inside the engine (in the GREEN circle) as well as the normal 5 move values in the 5 cylinders.
So when a random event occurs the move value in the green circle is swapped with the next move value. So in this case, the next move would be 7 bits instead of 2. As the engine is constantly rotating and shuffling itself, the move values have an equal chance of any move value being in any cylinder at any point in time.
The "random event" that causes an engine shuffle only needs to be infrequent. In fact it is best done infrequently. I tested a value of 1:256 which works very well. It shuffles ONE engine cylinder value, after every 256 bits processed (on average). The random event is produced by comparing the last 8 transposed bits to a "mask" value, and if it matches then a shuffle occurs.
Transposing bits in both space AND time
As these last 8 bits are from the TRANSPOSED bits and not the toggled bits, there is a high probability these 8 bits have not all been affected by the previous pass of the engine. In fact, some of the last 8 transposed bits may have been missed by multiple engine passes. This is an important subtlety; this transposes bits in both position AND time.
This means that of the last 8 bits used to generate the "random event" some of those bits may be from the last pass, some may be from many passes before, from a time when the engine was shuffled wth totally different values...
Implementing the Black RNG Engine
Anybody familiar with writing computer software (especially if you have ever implemented a Lempel-Ziv or DES style rotary algorithm) will see that this engine is very easy to code and will execute quickly.
I have written some Windows Software which uses the Black RNG Engine to produce 1 Mbyte of random data.
If you want to write your own software then that is OK, I have provided enough info on this page to help you along. Please don't expect me to debug your software! This algorithm is released as Hippyware. Please mention "Roman Black" and the "Black RNG Engine" in your work if you use my algorithm.
Fine-tuning the Black RNG Engine
When fine-tuning this algorithm I wrote some software to test the entropy of the random data produced. Here is a brief summary of what I discovered after testing and refining various versions of the engine;
The larger the seed the better, up to = total data size. Obviously.
Larger engine sizes are better, after about 10 cylinders size becomes less relevant.
Forget prime numbers, the best move values are SMALL; 1,2,3,4.
Prime numbers are not optimal as move values, the best move values are small in order to provide processing of more total bits per pass of the engine. Missing too many bits (ie larger move values) is just inefficient, taking more passes to produce the same result. However;
For every few small move values throw in a larger prime, ie 7, 11 or 13.
For a 10 cylinder engine (+1 held value) I suggest values like this; (2) 1, 2, 1, 2, 3, 1, 2, 3, 4, 11.
Good entropy occurs after as few as 10 passes, even from a poor seed!
Obviously you can use as many passes as you like. As the engine is self-shuffling it should not settle into a pattern after too many passes, unless you set it up very badly.
Experiment!
Have some fun with my engine and please let me know if you can get it to fail. Apart from bad setup like; too few cylinders, too few passes, too few variety of move values, I cannot get it to settle out. If you can get the engine to fail, ie settle out into any measurable pattern I would like to know about it. Thanks!
- end -
[Back to Home Page]