Are there any linear congruential generator algorithms that return only positive values?

Question

I am aware of one; the ZX Spectrum apparently used a Lehmer RNG with modulus 65537, and multiplier 75. This only generates numbers greater than zero. However, I'd like to use something with a period of more than 2^16 - 1.

I'm using this in a language with a 32-bit word length for integers (Haxe), so ideally it would be smaller than 2^31. However, I'm not necessarily looking for a Haxe-specific answer.

Answer 1

In machines that use twos complement (which means the x86 and derivatives, and pretty much any other computer you're likely to encounter), the high bit is used to indicate sign. If the high bit is set, then the number is negative.

So you can ensure that a number is positive by clearing the high bit. In the case of a 32-bit number, it's a simple matter of:

result = result & 0x7FFFFFFF;

Answer 2

Okay, this should have been obvious, but I figured it out. Here's my equation:

internalSeed = ( internalSeed * MULTIPLIER + INCREMENT ) % MODULUS + MODULUS;

To prevent exceeding the word length for an integer, while still providing a large period of returns, I went with the Microsoft Visual Basic 6 pseudorandom values:

MULTIPLIER = 1140671485
INCREMENT = 12820163
MODULUS = 16777216

Then the + MODULUS value of course changes the range from ( -16777216, 16777216 ) to ( 0, 33554429 ) which is what I wanted.

Edit: Some of the comments above offer different solutions.

In place of Math.abs(), one could always run a simple check of if ( result < 0 ) and then multiply the result by -1 if true. I'm not sure how much this would impact speed, but I don't think it would be by much.

The most sophisticated answer yet has you run a bitwise AND on the result with 0x7FFFFFFF in order to trim the negative bit. This has no impact on speed, and does indeed ensure a positive value.