[computer-go] Random

[Don Dailey]

Michael Williams wrote:
> I don't think Don was saying to use many calls to RDTSC to generate a 
> single random number.
> I think he meant do something like (FastBadRand() XOR RDTSC).
> The first part has low quality low-order bits and the second part has 
> low quality high-order bits.
That was my exact idea,  to xor or add RDTSC to the results.    If that 
really is a slow operation then it basically kills the idea.   The cycle 
time should be published somewhere though.

- Don


>
> Also, I can't imagine why executing a RDTSC would take 50 cycles.  But 
> I couldn't find any docs on that aspect of the instruction.
>
>
>
> steve uurtamo wrote:
>> the only thing to watch is that you'll likely need
>> 30+ bits from these guys to seed a prng, and
>> getting those bits in any organized way is likely
>> going to happen on a regular schedule (i.e. if
>> you get them in a loop, you're likely going to
>> space them out in an organized way).
>>
>> s.
>>
>>
>> On 5/15/08, Don Dailey <drdailey at cox.net> wrote:
>>> For a long time I have pondered whether you could build a very high 
>>> quality
>>> random number generator that was extremely fast using the pentium RDTSC
>>> instruction as a low order bit entropy source.     The idea would be 
>>> to use
>>> an extremely fast (but low quality) pseudo random number generator,  
>>> but
>>> modify the output (or the internal state of the generator) with the 
>>> time
>>> stamp register at each call.
>>>
>>> RDTSC reads the pentiums internal clock and is basically just a 64 bit
>>> counter.    However it increments very quickly and could be viewed 
>>> as an
>>> entropy source in the lowest bits as it would introduce at least a 
>>> little
>>> bit of non-determinism, and I think a little is all you would need to
>>> transform a horrible generator into a good practical one for many
>>> applications.   I  think the lowest 2 or 3 (or more)  bits would 
>>> appear to
>>> modern processors as almost unpredictable since there is so much 
>>> going on
>>> inside modern computers that are unpredictable.
>>> I don't know if the call to RDTSC is fast or how it would affect the
>>> parallelism of todays modern machines.   I'm not particularly 
>>> interested in
>>> non-deterministic generators as I sometimes depend on this for 
>>> testing and
>>> debugging,  but it's an idea I thought I would throw out there.
>>> - Don
>>>
>>>
>>>
>>>
>>>
>>> Don Dailey wrote:
>>>> If you are looking for a cheap fast and simple random number 
>>>> generator,  A
>>> post by George Marsaglia, an expert/guru on random number generation 
>>> has
>>> several and a C implemention.
>>>> These are one line generators,  coded as macros.    He also 
>>>> discusses the
>>> period and quality of each of them. This is a gem of a post  on
>>> sci.stat.math,sci.math  if you are interested in RNG:
>>>>       http://www.math.niu.edu/~rusin/known-math/99/RNG
>>>>
>>>> - Don
>>>>
>>>>
>>>>
>>>> Heikki Levanto wrote:
>>>>
>>>>>> In addition, xor_shift is better than builtin rand() and faster and
>>>>>> much smaller than MT.
>>>>>>
>>>>> I don't know that much about random numbers, so excuse my 
>>>>> ignorance. But
>>> a
>>>>> bit of googling got me to the Park - Miller Minimal Standard random
>>> number
>>>>> generator
>>> http://www.firstpr.com.au/dsp/rand31/p1192-park.pdf
>>>>> >From what I read, it should be quite sufficient for go programs. 
>>>>> It is
>>>>> dead simple and fast:
>>>>>
>>>>> long int pmrand() {
>>>>>    const long int a=16807;
>>>>>    const long int m= ( 1 << 31 ) -1;
>>>>>    pmrandseed = ( pmrandseed * a ) % m ;
>>>>>    return pmrandseed;
>>>>> } /* pmrand */
>>>>>
>>>>>
>>>>> Should I worry about this not being good enough?
>>>>>  - Heikki
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>> _______________________________________________
>>>> computer-go mailing list
>>>> computer-go at computer-go.org
>>>> http://www.computer-go.org/mailman/listinfo/computer-go/
>>>>
>>>>
>>> _______________________________________________
>>> computer-go mailing list
>>> computer-go at computer-go.org
>>> http://www.computer-go.org/mailman/listinfo/computer-go/
>>>
>> _______________________________________________
>> computer-go mailing list
>> computer-go at computer-go.org
>> http://www.computer-go.org/mailman/listinfo/computer-go/
>>
>
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>