How can I find the exact rand() used in a C library?

Question

As a part of my coursework I need to find and re-code a rand() random number generator which outputs the same numbers as the original. The starting sequence is 1804289383 846930886 1681692777 1714636915 1957747793 424238335 719885386 1649760492 596516649 1189641421 1025202362 and can be generated at http://ideone.com/H7tsSI

#include <stdlib.h>     /* rand */
#include <iostream>
using namespace std;

int main ()
{
    for (int i = 0 ; i< 10 ; i++) {
        cout << rand() << " ";
    }
    cout << rand();

    return 0;
}

My issue is that I can't find the original source of this generator, and I don't know how I can figure out the way the generator works from the full sequence of the generator, which is 100 numbers long. Could someone help me either find the original generator or teach me how I can find a generator from its sequence? Thanks!

I'm not sure I understand. Are you just asking how to find out what thd default seed is? — Barmar, Nov 18 '16 at 22:36
The algorithm used by `rand()` is not standardised - it depends on your implementation. If your problem is finding the starting seed, then use `srand()` - then you will know the starting seed, and be able to change it at leisure. (Bear in mind that, usually, it is only ever necessary to call `srand()` once). — Peter, Nov 18 '16 at 22:44
I need to find the RNG algorithm. I've already searched and found the link Eugene Sh. provided, and it did not give me the solution I was looking for. The generator there is not identical to the generator I am looking for. The generator is in gcc 4.9.2, but the source code is confusing me. — Saixoz, Nov 18 '16 at 23:01
I really don't understand the point of such an assignment. It has to include the name of the algorithm at the very least or any other reference to the "original". — Eugene Sh., Nov 18 '16 at 23:03
"_You cannot know which way the train went by looking at the tracks._" That is, you cannot derive the algorithm by looking at the numbers - _unless_ you are to choose from a limited set of algorithms, and then you implement each and hold its output against the sequence you have been given (sounds like NP-complete). — Paul Ogilvie, Nov 18 '16 at 23:16

score 1 · Answer 1 · answered Nov 18 '16 at 22:44

Depending on your specific compiler you may have the source code available. On Visual Studio 12.0, for example, the rand() source code is:

int __cdecl rand (
        void
        )
{
        _ptiddata ptd = _getptd();

        return( ((ptd->_holdrand = ptd->_holdrand * 214013L
            + 2531011L) >> 16) & 0x7fff );
}

If your compiler does not include the source code for its C library, you could try using a disassembler to piece together what its version of the rand() function does. In general, most of them would be along the same lines of the above code: access a state variable that was the result of the last call to rand() (or the seed if it's the first call), perform a permutation on it, and then write that back to the state variable.

score 0 · Answer 2 · edited May 23 '17 at 10:32

You can find the source library implementation used by GNU at http://www.gnu.org/software/libc/ If you're familiar with GIT, you can use the GIT source code management like :

$> git clone git://sourceware.org/git/glibc.git

rand() function essentially calling different functions - first __random which in turn calls __random_r . Click on the function names to refer to the source repository at version 2.15

For more details, refer to answers here - gcc implementation of rand()

How can I find the exact rand() used in a C library?

2 Answers2