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(at)gregsmith(dot)com http://www.gregsmith.com Baltimore, MD