[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.

I also intended for RDTSC to change the state of the random number 
generator which would be extremely chaotic over time.   Some 
FastBadRand() generators use the last value returned as the state.

- 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/
>