Unix Programming - just how random is this??

Author

just how random is this??

inf

2004-01-23, 5:20 pm

i wasnt sure if this is the best place for this post, plz guide me
elsewhere if its not. while browsing the intel manuals, i found the
rdtsc instruction:
Loads the current value of the processor's time-stamp counter into the
EDX:EAX registers. The
time-stamp counter is contained in a 64-bit MSR. The high-order 32 bits
of the MSR are loaded
into the EDX register, and the low-order 32 bits are loaded into the EAX
register. The processor
monotonically increments the time-stamp counter MSR every clock cycle
and resets it to 0
whenever the processor is reset.

so i wrote this program:

#include <stdio.h>
/*
;//get the processor timestamp
;///eax has low double word, edx high double word
;//edx usually only has the first byte or 2 filled in
rdtsc

;//do the 2 low bytes
xorb %dl, %al
xorb %dl, %ah

;//now rotate around the 2 high bytes
ror $16, %eax

;//now do the high bytes
xorb %dl, %al
xorb %dl, %ah
;//eax now has a VERY random number
*/

unsigned int mrand()
{
unsigned int daret = 0;

asm("rdtsc; xorb %%dl, %%al; xorb %%dl, %%ah; \
ror $16, %%eax; xorb %%dl, %%al; xorb %%dl, %%ah; \
movl %%eax, %0;"
: "=r" (daret)
:
: "%eax", "%edx" );

return daret;
}

int main()
{
unsigned int darand = 0;

darand = mrand();

printf("generated %u(%#08x)\n", darand, darand);

return 0;
}

which generates this output:

generated 486181881(0x1cfa8bf9)
generated 3620637582(0xd7ce8b8e)
generated 3123350429(0xba2a8b9d)
generated 802851771(0x2fda8bbb)
generated 2258930249(0x86a48a49)
generated 3764423261(0xe0608a5d)
generated 4219898476(0xfb868a6c)
generated 3007875587(0xb3488a03)
generated 1779730961(0x6a148a11)
generated 2558167591(0x987a8a27)
generated 206473784(0xc4e8a38)
generated 607029980(0x242e8adc)
generated 2015922930(0x78288af2)
generated 3952380559(0xeb948a8f)
generated 343837352(0x147e8aa8)
generated 2509540031(0x95948abf)
generated 1156483404(0x44ee894c)
generated 1722321254(0x66a88966)
generated 2704968052(0xa13a8974)
generated 3685779722(0xdbb0890a)

it seems pretty good to me, but im by no means an expert on the topic.
so i was wondering how good this approach is? mainly in comparision
to the standard srand(time(0)); or similar things. thanks!

Eric Sosman

2004-01-23, 5:20 pm

inf wrote:

quote:

>
> i wasnt sure if this is the best place for this post, plz guide me
> elsewhere if its not. while browsing the intel manuals, i found the
> rdtsc instruction:
> Loads the current value of the processor's time-stamp counter into the
> EDX:EAX registers. The
> time-stamp counter is contained in a 64-bit MSR. The high-order 32 bits
> of the MSR are loaded
> into the EDX register, and the low-order 32 bits are loaded into the EAX
> register. The processor
> monotonically increments the time-stamp counter MSR every clock cycle
> and resets it to 0
> whenever the processor is reset.
>
> so i wrote this program [code and output snipped]:
>
> it seems pretty good to me, but im by no means an expert on the topic.
> so i was wondering how good this approach is? mainly in comparision
> to the standard srand(time(0)); or similar things. thanks!

Assuming you're not doing cryptography or high-precision
Monte Carlo integration or something of that sort, the counter
makes a reasonable srand() seed: it's a lot like time(), but
less predictable. However, the counter itself would be a very
poor source of pseudo-random numbers: successive values would
tend to differ by small amounts. If you used the counter to
generate X and Y coordinates, most generated points would lie
in a thin triangular wedge just above the Y=X line, which is
not a characteristic one usually thinks of as "random."

True, your XORing of bits and pieces perturbs things a
little and breaks up the nice neat wedge shape -- but it only
breaks it up into a smallish number of splinters, all still
wedge-shaped and lying next to line segments of slope one.
That still doesn't seem "random" to me.

For analytical tests of randomness, see Section 3.3.2 of
Knuth's "The Art of Computer Programming, Volume II: Seminumerical
Algorithms" and/or look for George Marsaglia's "Diehard" battery
of tests. I think you'll find them slightly stronger than "it
seems pretty good to me."

--
Eric.Sosman@sun.com

inf

2004-01-23, 5:20 pm

Eric Sosman wrote:

quote:

> inf wrote:
>
>
>
> Assuming you're not doing cryptography or high-precision
> Monte Carlo integration or something of that sort, the counter
> makes a reasonable srand() seed: it's a lot like time(), but
> less predictable. However, the counter itself would be a very
> poor source of pseudo-random numbers: successive values would
> tend to differ by small amounts. If you used the counter to
> generate X and Y coordinates, most generated points would lie
> in a thin triangular wedge just above the Y=X line, which is
> not a characteristic one usually thinks of as "random."
>
> True, your XORing of bits and pieces perturbs things a
> little and breaks up the nice neat wedge shape -- but it only
> breaks it up into a smallish number of splinters, all still
> wedge-shaped and lying next to line segments of slope one.
> That still doesn't seem "random" to me.
>
> For analytical tests of randomness, see Section 3.3.2 of
> Knuth's "The Art of Computer Programming, Volume II: Seminumerical
> Algorithms" and/or look for George Marsaglia's "Diehard" battery
> of tests. I think you'll find them slightly stronger than "it
> seems pretty good to me."
>

thanks for those references, good stuff. a friend also pointed out to
me the following, the 2nd least significant byte always has 8 as the
upper nibble!