4 ms·
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 experiment
by jffry 4y ago
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#m_a_power_of_2,_c_=_0 https://en.wikipedia.org/wiki/Linear_congruential_generator#...
- bonzini 4y agoHe means that the constants are chosen so that the multiplication and addition can be done on a signed 32-bit integer without overflow.
- morelisp 4y agoThere's no reason to avoid overflow (nor any reason to make it signed since that would also be a concern these days) though.
- bonzini 4y agoThat 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.
- morelisp 4y agoSuch 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.
- a1369209993 4y ago> 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).
- bonzini 4y agoYou're right, that makes no sense. Also a-1 (9300) should not have factors in common with m (233280) but it has a lot...