Re: Spinlock backoff algorithm

On Wed, 14 Nov 2007, Mark Mielke wrote:

>> The other problem with using modulo is that it makes the result depend
>> mostly on the low-order bits of the random() result, rather than mostly
>> on the high-order bits; with lower-grade implementations of random(),
>> the lower bits are materially less random than the higher.

> If this was a serious problem, there is the >> operator. I see it as a poor 
> coding practice to make assumptions about which bits are most "random" in a 
> call to random().

There are many types of pseudo-random number generators where the 
low-order bits are not so random, and the assumption Tom has described is 
pretty likely to be true.  See http://www.fourmilab.ch/random/ as one 
comment about the badness of the standard UNIX random generator for 
example.

There is an interesting discussion of this issue along with code showing a 
way to improve things while only using integer math (which in some cases 
uses >> as you suggest) as part of the Java standard library:

http://java.sun.com/j2se/1.4.2/docs/api/java/util/Random.html#nextInt(int)

--
* Greg Smith gsmith@gregsmith.com http://www.gregsmith.com Baltimore, MD