So a couple of months ago, I was going through a whole “random number” phase, reading everything I could about them. I eventually came across clock drift as a legit way of creating random numbers from a probabilistic machine (i.e. a computer). Clock drift is based on the slight fluctuation of quartz crystal oscillations found in both the CPU and Motherboard clocks on most modern computers.
I busily derived a function that should technically work, assuming the fact that rdtsc queries the CPU clock, whilst QueryPerformanceCounter (Windows only) queries the motherboard clock, which is a relatively safe assumption. I wrote this in VC++, so the assembly syntax would have to be changed if anyone ports this to any other OS:
|
1 2 3 4 5 6 7 8 9 |
void QueryRDTSC(__int64* tick) { __asm { xor eax, eax rdtsc mov edi, dword ptr tick mov dword ptr [edi], eax mov dword ptr [edi+4], edx } } |
And the actual RNG:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
__int64 clockDriftRNG() { __int64 CPU_start, CPU_end, OS_start, OS_end; // get CPU ticks QueryRDTSC(&CPU_start); Sleep(1); QueryRDTSC(&CPU_end); // get OS ticks QueryPerformanceCounter((LARGE_INTEGER*)&OS_start); Sleep(1); QueryPerformanceCounter((LARGE_INTEGER*)&OS_end); // due to the low resolution of the mobo clock, // sometimes, there will be zero time between ticks.. // I catch it, return it, and just get another more reliable number if (OS_end – OS_start == 0) return –1; // return 0 or 1 randomly // CPU clock is ~1000x faster than mobo clock return ((CPU_end – CPU_start)/(OS_end – OS_start)%2); } |
Now, the numbers actually looked pretty good, I wrote a C++ program that ouput 512×512 0s and 1s in a text file. And, in the spirit of RANDOM.org and Bo Allen, I plotted the data:
Relatively happy with the results (even if, realistically, I could only use my RNG to seed PRNGs), I just wanted to make sure I didn’t screw anything up so I posted a question on SO. Stephen Nutt had a very good comment, which made me feel slightly uneasy:
The Sleep function is limited by the resolution of the system clock, so Sleep (1) may not be doing what you want.
I actually agreed with him and wanted to figure out a more robust way of testing the clock drift between the motherboard and CPU timers. I decided that instead of Sleep(1), I would use an ASM nop loop:
|
1 2 3 4 5 6 7 8 |
void loop() { __asm { mov ecx, 1000 cylcles: nop loop cylcles } } |
1000 nops seemed like a pretty good equivalent to Sleep(t). I ran the program and got the text file. But when I plotted it, I was stupefied:
Whoa, what’s up with the streaks? Why does using an ASM sleep (independent of the system clock resolution) screw up the actual numbers? I knew I’d maybe have to do some Whitening to fix up the numbers, but I wasn’t expecting streaks.
I tried a superficial fix and changed mov ecx, 1000 to mov ecx, 5000:
Still no dice š The image is darker (I’m getting more 1s than 0s), which is expected (longer wait-time = larger sample = higher chance of %2). To this day I can’t figure out why Sleep(1) gives such a pretty answer, but the ASM solution is just abysmal (from a visual standpoint). With that said, after running some 4 million randomly-generated bytes (via the Sleep(1) method) through DIEHARD, the results are kind of awful. I think I might be able to use this as a PRNG seed, but I still need to run more tests (and maybe fix some implementation details) before I use it as a RNG.
If you’re wondering, I wrote the RNG for a non-deterministic Virtual Machine I’m working on. I just wanted to post this on here because I’ll probably lose the code and hey, I have a blog now.