Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer
    
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 Dec 19 '12 at 10:30
add comment

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.

share|improve this answer
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). –  delnan Dec 18 '12 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 Dec 18 '12 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. –  GlenH7 Dec 18 '12 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.) –  delnan Dec 18 '12 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. –  GlenH7 Dec 18 '12 at 17:45
add comment

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)

share|improve this answer
    
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 Dec 19 '12 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 Dec 19 '12 at 11:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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