4 ms·
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.
by swayvil 4y ago
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.
- jffry 4y agoThe 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...