Random numbers

[andrey_zh]

From Borland C++ 3.1 Help, article rand():

rand uses a multiplicative congruential random number generator with period
232 to return successive pseudo-random numbers in the range 0 to RAND_MAX.

It used to be so in some old C standard (C89 I guess), then it was fixed.

[Lindley]

I think you're loosing some formatting there. I could believe a period of 2^32, not 232.....

[andrey_zh]

This was copied exactly as it is in Borland C++ Help, I believe it was lost before:
Have a look:
(1) http://poli.cs.vsb.cz/c/help/stdlib0.htm#LBL66
(2) http://books.google.lv/books?id=_T-s...%20%22&f=false

[Lindley]

Well, it's wrong. The period is 2^32 according to several other sources, and frankly that makes much more sense.

[andrey_zh]

Just tested it on original Borland C++ 3.1. You're right, the period is longer than 232.
I'm surprised, this typo could survive through years and some printed books.

[monarch_dodra]

Just tested it on original Borland C++ 3.1. You're right, the period is longer than 232.
I'm surprised, this typo could survive through years and some printed books.

It was probably 2³², but the formatting got lost and got transformed into 232.

As far as I know though, from a standards point of view, rand is entirely implementation dependent.

The only requirements are a seed, and for the output to be a linear distribution between 0 and RAND_MAX, RAND_MAX being implementation defined. Anything else is just speculation on the implementation. For all you know, RAND_MAX could be 32, and the implemention could be Mersenne, with a 2^19937 period.

...

On a side note, I wanted to add that in a PRNG using LCG the values in a "cycle" are completely independent of the seed. The seed only defines the starting point in the cycle.

[mary_201091]

Hi again and sorry for being so insistent, but i am very interested in solving this task :

I know that the 1000 numbers have been generated using a function like the rand() of Visual C:

Xn+1=(a*Xn+c) mod 2^32

And after doing this, the numbers that we have access to are formed by extracting the bits 30-16 (length:15 bits- numbers range from 0 to 32767).

There has to be a way to calculate the 'a' and 'c' variables having the first 1000 numbers. I insist: i think that the paper "Inferring sequences produced by a linear congruential generator missing low-order bits" contains the algorithm to do that, but i don't have access to it. So, please, i need urgent help.

Thanks a lot!

[Lindley]

Go ask on a math forum. They're more likely to be able to help, since you're looking for an equation to solve before you can even think about writing code.

Or just buy the paper.

[Chris_F]

Hi again and sorry for being so insistent, but i am very interested in solving this task :

I know that the 1000 numbers have been generated using a function like the rand() of Visual C:

Xn+1=(a*Xn+c) mod 2^32

And after doing this, the numbers that we have access to are formed by extracting the bits 30-16 (length:15 bits- numbers range from 0 to 32767).

There has to be a way to calculate the 'a' and 'c' variables having the first 1000 numbers. I insist: i think that the paper "Inferring sequences produced by a linear congruential generator missing low-order bits" contains the algorithm to do that, but i don't have access to it. So, please, i need urgent help.

Thanks a lot!

Seriously, just because the people here code, doesn't mean they hold advanced degrees in mathematics. You're asking your questions in the wrong place. Your problem may be related to programming, but your actual questions are purely mathematical.

[nuzzle]

Seriously, just because the people here code, doesn't mean they hold advanced degrees in mathematics. You're asking your questions in the wrong place. Your problem may be related to programming, but your actual questions are purely mathematical.

And just because you code doesn't mean you're mathematically challenged. To be a good programmer you should know some concrete math and this is well within the city limits.

[Lindley]

Understanding how to look up the relevant paper and implement it is a reasonable expectation. Even understanding the problem statement in mathematical terms.

Actually working out the solution, however, moves into the realm of research; and thus while many of us no doubt could do it given time, that isn't something we're likely to be spending large amounts of time on for someone else's benefit.

[Chris_F]

And just because you code doesn't mean you're mathematically challenged. To be a good programmer you should now some concrete math and this is well within the city limits.

Or so you say, but I have yet to see your proof.

[nuzzle]

Or so you say, but I have yet to see your proof.

Proof of what?

After the last post of the OP I think I know how to solve this problem but that's not important.

What's important is the discussion itself and who are you trying to curb it?

[Russco]

...... you use the LLL algorithm

[Chris_F]

Proof of what?

I meant proof as in mathematical proof.