Hacker News Reader

Comment by swayvil | Hacker News Reader

I think it fits the rng period to fit max 32 bit (4 bil). Somebody in the comments said similar so I feel good about this.

View on HN

The person in the comments said the period is only ~233k, which is correct, because you are always taking modulo 233280. But it's also easy to verify experimentally:

  let state = 6, iters = 0;
  do {
    state = (state * 9301 + 49297) % 233280;
    iters++;
  } while(state !== 6);
  console.log("period is", iters, "iters");
  //period is 233280 iters

If you instead took modulo 2^32, I believe the period would indeed be the maximal period, according to this article: https://en.wikipedia.org/wiki/Linear_congruential_generator#...

He means that the constants are chosen so that the multiplication and addition can be done on a signed 32-bit integer without overflow.

There's no reason to avoid overflow (nor any reason to make it signed since that would also be a concern these days) though.

That depends on the language. For example BASIC used to have only 16-bit or 32-bit signed integers (depending on the processor; plus strings and floating point), so this particular RNG can be useful for its portability.

Such dialects of BASIC also offered defined overflow behavior (it's really only C/C++ and other things targeting MCUs that don't - and even three also only relatively recently that "undefined overflow" meant something more practically dangerous than "implementation defined") so it was still not a concern.

Sure but signed and unsigned division are different.

There's no division in the algorithm, is there?

There's modulo which is the remainder of the division.

Oh, true!

> so that the multiplication and addition can be done on a signed 32-bit integer without overflow

Except they can't: any seed in the range 230888 thru 233279 will produce a signed integer overflow when multiplied by 9301 (eg 9301*230888 = 0x80001608).

You're right, that makes no sense. Also a-1 (9300) should not have factors in common with m (233280) but it has a lot...

Reply on news.ycombinator.com