35

If you search for examples of creating a seeded (pseudo)Random number generator, you will run into stuff like this (specific example http://indiegamr.com/generate-repeatable-random-numbers-in-js/):

// the initial seed
Math.seed = 6;

// in order to work 'Math.seed' must NOT be undefined,
// so in any case, you HAVE to provide a Math.seed
Math.seededRandom = function(max, min) {
    max = max || 1;
    min = min || 0;

    Math.seed = (Math.seed * 9301 + 49297) % 233280;
    var rnd = Math.seed / 233280;

    return min + rnd * (max - min);
}

Those specific numbers (9301, 49297, 233280) and algorithm are used over and over, but nobody seems to have a definitive reference for this. Who invented this algorithm and tested the distribution? Is there a paper or something to cite?

chicks
  • 113
  • 6
jlarson
  • 511
  • 1
  • 4
  • 8
  • 13
    it's a [linear congruent generator](http://en.wikipedia.org/wiki/Linear_congruential_generator) but with a fairly small period (only 233k while a 32 bit int allows have a 4 billion period – ratchet freak Oct 26 '14 at 19:22
  • 2
    People often copy code directly from books, so it's probably from an old book somewhere and has been copied several times. It also appears to be a limiting case. Possibly helpful: http://heydari.persiangig.com/Ebooks/Applied_Crypto-Ch11-ch20.pdf/download?b099 http://www.ict.griffith.edu.au/anthony/info/C/RandomNumbers –  Oct 27 '14 at 20:29
  • 2
    Whatever the origin, those are terrible values to use for calculating a seed. –  Oct 27 '14 at 21:22
  • @Snowman can you elaborate? I am completely ignorant in this area... as is, it seems, almost everybody – jlarson Nov 03 '14 at 22:31
  • 6
    @jlarson a comment is not nearly long enough, but there are two issues at hand. First, as ratchet freak alluded to, the modulo is the _maximum_ period: number of unique numbers before the generator repeats itself. The actual period may be smaller. Second, the other two numbers (mostly the multiplicand) should be [relatively prime](http://en.wikipedia.org/wiki/Coprime_integers) to the modulo number to ensure a longer period. Ideally the modulo number is the largest prime less than the maximum positive integer that fits in the data type, and the other two numbers are also large primes. –  Nov 04 '14 at 03:15
  • 1
    That is the short, short version of why those numbers are terrible, given this is a side discussion and adding an actual answer is not appropriate for this question. I recommend bouncing around [Wikipedia](https://www.wikipedia.org/) and maybe [Mathematics](http://math.stackexchange.com/) or [Computer Science](http://cs.stackexchange.com/) for more info, although technically pseudorandom number algorithms are also on-topic at Programmers. –  Nov 04 '14 at 03:21
  • Quite possibly the numbers first appeared in code somewhere, without any research paper to back them up. Then in the most glorious tradition of computing the algorithm was copied ad nauseam. – Mark Ransom Aug 07 '22 at 03:16

1 Answers1

26

A quick search of Google Books shows these numbers (9301, 49297, 233280) have been used in a number of references:

  • Numerical Recipes in FORTRAN 77
  • An Introduction to Numerical Methods in C++
  • CGI Developer's Resource: Web Programming in TCL and PERL
  • Effective Fortran 77 for Engineers & Scientists
  • JavaScript development
  • All on C
  • Java Examples in a Nutshell
  • Seminumerical algorithms
  • An Introduction To Mechanics

The oldest is 1977's Computer methods for mathematical computations by George Elmer Forsythe, Michael A. Malcolm, Cleve B. Moler (Prentice-Hall), although Google doesn't show where the text was used in the book so it cannot be verified.

The earliest showing the text is Numerical Recipes in Pascal (First Edition): The Art of Scientific Computing, Volume 1 by Press, Teukolsky, Vetterling and Flannery in a full-page table of "Constants for Portable Random Number Generators". These particular numbers are given with an overflow at 2^31.

The Numerical Recipes series of books are hugely popular, and have been in print since 1986.

gnat
  • 21,442
  • 29
  • 112
  • 288
Hugo
  • 3,669
  • 2
  • 25
  • 40
  • 6
    Wow, if the answer isn't in here I don't know where it would be. Thanks.. // I was kind of hoping to be able to point to some specific research as to why these numbers are special, but this suffices. 9301 is a product of two primes (71x131), 49297 is a prime -- instinctually I feel like that must be relevant. 233280 is not prime -- it equals 2x2x2x2x2x2x3x3x3x3x3x3x5 (or 2^6 * 3^5 * 5) – jlarson Oct 28 '14 at 18:47
  • Sometimes these types of numbers, along with seeds, have a personal significance to the author. A birthday, a favorite number, a random but meaningful statistic, or some combination along the same lines. For example, I use 42 as a seed as an homage to Hitchhikers Guide to the Galaxy. – Brandon Bertelsen Aug 06 '22 at 15:43
  • Didn't Knuth's Seminumerical Algorithms 1st edition show up in 1969? That seems to predate everything else. I don't have 1st edition to check, but I also cannot find any evidence that this LCG was referenced in at least the 3rd edition I have. I think TAOCP (Seminumerical Algorithms) may be a false positive. – Anders Aug 06 '22 at 16:50
  • Yeah the off-beat title "Seminumerical Algorithms" is solely Knuth's, but these numbers don't appear in it: not the current (1997) 3rd edition, not the 1981 2nd edition, and while I don't have access to it right now, I doubt it appeared in the 1969 1st edition either. I've found Google Books often just shows "related" books in which the searched terms don't appear at all. – ShreevatsaR Aug 06 '22 at 17:08
  • "computer methods for mathematical computations" can be 'borrowed' for free at https://archive.org/details/computermethodsf00fors/page/240/mode/2up but I did not find the values in that book – Willem Hengeveld Aug 06 '22 at 21:55
  • Effective fortran77 can be viewed on google-books: https://books.google.nl/books?id=46pQAAAAMAAJ&q=%22233280%22&dq=%22233280%22&hl=en&sa=X&ved=2ahUKEwjnnoXojrP5AhUR8LsIHVv2BP4Q6AF6BAgiEAI – Willem Hengeveld Aug 06 '22 at 21:58
  • Found it in 1986 in "Numerical recipes : the art of scientific computing" see https://archive.org/details/numericalrecipes00pres/page/198/mode/2up – Willem Hengeveld Aug 06 '22 at 22:10
  • @Anders surely Knuth documented LCG? What numbers did he use? – Mark Ransom Aug 07 '22 at 03:11
  • @MarkRansom yes, certainly section 3.2.1 (14 pages) is devoted just to LCGs. Knuth gives a few toy examples of modulus and multiplier in exercises, but mostly the discussion is devoted to how pick good numbers; suggesting modulus of either 2^n or 2^n +- 1 and theorems for picking multipliers to then give maximum period. Knuth gives ideal values via theorum. In other words this is probably a 1986 NR thing where it's more a cookbook with tables of values. I couldn't find it earlier. It also figures because it's not the first time that NR's recipes turn out 1/2 baked... – Anders Aug 07 '22 at 21:44
  • I think TAOCP showed some constants for a horrible linear congruential pseudo-RNG (together with analysis why it is bad), but not this one. – gnasher729 Sep 05 '22 at 19:42
  • @MarkRansom Knuth described some clever algorithms how to determine the quality (especially for not one, but say four sequentially generated numbers), and showed how to get maximum period, but the rest was left to the reader. – gnasher729 Sep 05 '22 at 19:45