3

I need a very simple pseudo random generator (no any specific quality requirements) and I found Microsoft's variant of LCG algorithm used for rand() C runtime library function fit my needs (gcc's one seems too complex).

I found the algorithm here:

http://rosettacode.org/wiki/Linear_congruential_generator#C

However, I worry the algorithm (including its "magic numbers" i.e coefficients) may by patented or restricted for use in some another way.

Is it allowed to use this algorithm without any licence or patent restrictions or not?

I can't use library rand() because I need my results to be exactly reproducible on different platforms

Improve this question
0

3 Answers 3

Reset to default
3

The Mersenne twister prng is well known and implemented.

For an even simpler approach, Project Euler has used a pseudo random number generator:

S0 = seed

Sn+1 = Sn2 mod 50515093

If you want something close to 2^32, change the mod to 0xFFFFFFFB (the number 4,294,967,291 - the largest 32 bit prime)

The man page for rand has the following implementation from the POSIX.1-2001 specification:

static unsigned long next = 1;

/* RAND_MAX assumed to be 32767 */
int myrand(void) {
    next = next * 1103515245 + 12345;
    return((unsigned)(next/65536) % 32768);
}

void mysrand(unsigned seed) {
    next = seed;
}

Look at the Art of Computer programming, volume 2 - it has a section dedicated to random number generation.

Improve this answer
1
  • Thank you, almost all your suggestions are helpful. I don't need very long periods, even 2^31 is enough. I use random generator for program testing (to emulate thread switching with some probability, not for Monte Carlo probability calculation) so I don't even need presize uniformity, but I need to avoid visible correlations of discrete events generated with the generator. So, I hope, even posix algorithm may be acceptable, although Mersenne twister implementations (as almost all of them are covered by unrestrictive licences) are also interesting.
    – user396672
    Commented Dec 19, 2012 at 10:30
2

The code you reference is Free to use, but not necessarily free. At the bottom of the page, you'll see:

    This page was last modified on 5 November 2012, at 23:58.
    Content is available under GNU Free Documentation License 1.2.

And it includes a link to the GNU Free Documentation License 1.2

Read the GNU documentation license to see what you need to do with attributing the code and providing any changes you may make.

In the US, design patents are only valid for 14 years after granting. See this USPTO link.

The Wikipedia article on Linear congruential generator indicates a number of implementations and their coefficients. It also includes a reference to Microsoft's implementation within Microsoft Visual/Quick C/C++.

Those compilers had their origins in 1983 or 1993, depending upon which you look at. Either way, both are well past the 14 year limit for patents.

You also don't know that MS performed the research in order to discover those coefficients, nor that changing the coefficients would be sufficiently novel as to merit patent protection. The LCG algorithm has been around for a long time. Given that there are a number of sets of published coefficients, it's pretty safe to assume that they aren't protected through patents.

Improve this answer
5
  • 2
    That's the license for the wiki page as a whole. IANAL but I wouldn't be surprised if there were a bazillion ways content included in the text might be patented or otherwise restricted (e.g. a trademark being mentioned in the text doesn't mean you can use the trademark by the terms of the FDL).
    – user7043
    Commented Dec 18, 2012 at 17:05
  • As I understand, GNU Free Documentation License covers the licence for this algorithm description (I may reproduce the document under the GNU licence), but don't cover the algorithm itself. Patent or invention usually may be explained freely (in a book, for example), but patent use is restricted
    – user396672
    Commented Dec 18, 2012 at 17:12
  • @delnan - the content in this case isn't sufficiently novel to be patented or otherwise restricted. See the Wikipedia link providing a number of sets of coefficients.
    – user53019
    Commented Dec 18, 2012 at 17:37
  • @GlenH7 I wouldn't know. Patent law seems crazy, especially in the US. (There's a patent application for the IsNot operator in VB.)
    – user7043
    Commented Dec 18, 2012 at 17:39
  • @delnan - I would know (to a certain degree) since I have 12 (+/-) registered in my name in the US. I never kept track of the non-US filings. IANAL, but I'm very familiar with the process from discovery to filing.
    – user53019
    Commented Dec 18, 2012 at 17:45
1

if you are really worried you can find your own parameters for the LCG using the constrainst mentioned at http://en.wikipedia.org/wiki/Linear_congruential_generator#Period_length

or use one of the other examples given right below it (the a=1103515245 c=12345 varient is used by multiple open source projects so should (IANAL) be free to use)

Improve this answer
2
  • the period is only one of random generator quality parameters (x(n+1)=x(n)+1 has 2^32 period for 32bit integers but this formula is totaly unacceptable as random generator). So I need to run some staistical tests for my own values (uniformity, corellation between values, etc.). It's an extensible work that I'd prefer to avoid :). However, thanks for suggestion of another well-known magic numbers, so +1.
    – user396672
    Commented Dec 19, 2012 at 10:31
  • @user396672 there is a easy method for seeing how good a LCG which it generating 3D points with it and seeing in how many planes they fall, the more planes the better
    – ratchet freak
    Commented Dec 19, 2012 at 11:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.