Hi all, again, I have discovered how the rand() function in C/C++ works, well in the GNU C/C++ anyway (I use DJGPP) Its function is

  
int rand(void)
{
	randSeed = (69069 * randSeed+1);
	return randSeed & 0x7fff;
}

// the srand function is defined as:


void srand(unsigned seed)
{
	randSeed = seed;
}
  

what I want to know from yesturdays post about random numbers is that from this formula used in rand can it be reversed to give you the last version of randSeed? I''ll try to make this more clear because I am kinda confusing myself here. Say for example if randSeed was 356456 before the line in rand() return randSeed & 0x7fff; and that maybe gave 563464 (made up value!) could I reverse the statement randSeed & 0x7fff; to give me the value of randSeed before it hit that line so that I can rearrange this formula randSeed=(69069 * randSeed + 1); so that I can get the value of randSeed before it hit this line too. I know this all sounds weird and I can''t really go into why I wanna play around with random numbers but it is a secret project I am working on to some how revolutionise something in computing. (One clue, Winzip''s job, don''t ask how cos I dont fully know, but I kinda found a link between a new file format for compressed files and random numbers) Can you also tell me if the rand() function given its definition that I have researched and written for you can produce any set of random numbers in the world or is it only good for producing deterministic numbers that never repeat so often, you see I would like numbers as realistic as for example picking 12 numbers out of a hat (numbers from 1 to 12 and on every pick its put back and the hat is shuffled) and managing to some how pick a sequence maybe like: 1,4,4,4,4,4,5,2,6,12,5,4,2,7,9 what I mean is can rand() function ever produce something like this because in reality, someone may pick out the number 4, from a hat 5 times in a row. Are there any random functions or algorithms that can produce random numbers as real as the set above. This is really important to me because once I can find a function that produces life like random numbers not deterministic numbers that will never look like the number set above then I can work on how to derive the seed back from the last random number all the way to the beginning so that I can derive the initial seed that sparked the entire random sequence. This is a windful, I know and some how doubt this can ever work, but if it can believe me, it would revolutionise something big time !!!!!! Any Help is good help Dark Star

Only one to one functions have inverses. That is a basic mathematical truth. A one to one function is one for which f(x) != f(y) for any y != x. That function is not one to one because for any given output there are 2^17 inputs that will produce that output. The values of randSeed may be one to one so given a value for randSeed you may be able to reverse the sequence. You cannot simply say randSeed = (randSeed / 69069) - 1 though unless randSeed is between 69069 and 2^32-1. That is because of overflow. It also may not be one to one.

After a bit of thought the calculation of randSeed does have an inverse. The actual function would be the one Grib gives which as long as (prevrand*b+c)/m is less than two for all cases you can calculate prevrand from rand. If prevrand=(rand-c)/b if the result would be >=0. Otherwise it would be prevrand=((rand+m)-c)/b.

I have to agree with Grib that you cannot compress a file using a pseudo-random number generator. I''ll give a differant arguement though much the same. If you have a repeating sequence then the minimum length that sequence can be is range^2 to have all sequences of two numbers present. With a range of 2 that would be 0,1,1,0. Since it is repeating there really isn''t a start or end so any rotation is still the same sequence. A reversal will also generate all pairs, but with just two digits it looks the same forwards and backwards. With three digits it becomes 0,1,2,0,2,2,1,1,0 and with four 0,1,2,3,0,2,2,0,3,3,1,1,3,2,1,0. These are not the only possible sequences, but there are no sequences shorter that generate all pairs. Rand generates 2^15 distinct numbers so it takes a list 2^30 long to have all pairs. It takes a list 2^45 to have all triplets, but you only have at best a sequence 2^32 long so you are missing 2^13 triplets. I believe you can pick up at best half of those running the sequence in reverse. Even if you could you are still missing 4,096 triplets. So the longest sequence you can be guaranteed of being able to replace with an index and direction in the sequence is two numbers.

That index and direction is 33 bits to replace 30 bits of data. Those numbers are not nice powers of two so lets say you have a sequence 2^32 long of 2^16 numbers and you only go in one direction. You still are taking 32 bits to encode 32 bits. You could try arguing that you would use 32 bit numbers instead and then replace 64 bits with 32 bits, but you can only at best encode half of the pairs. Even if you got lucky enough that they are all there you would get at best 2 to 1 compression. That is without regard to the computational intensity. You are going to have to compare 64 bits 2^31 times on average to find a pair that is there. Even if you could do 100 million per second which is wildly optimistic it is going to take you over 20 seconds per 64 bits on average. A 1MB file is going to take you roughly 260 days to compress and that is being wildly optimistic. More likely it would be measured in years just to get a two to one compression in the best of circumstances.

So you have a fundamental problem of the compressed format taking as much space as what you compressed and it taking far to long to do it. I won''t say that you can''t do it, but I will say that you have to overcome both of those problems to do it. I would suggest looking at something like the compression used in JPEG files. The idea is much the same. That being to come up with a function that will regenerate an image or at least one reasonably close to the original. In general chaos theory and fractals might point you in a productive direction. Overall you need to think of the file being compressed as an ordered set of data rather than a random set. It is more productive to try to identify the pattern than to try to fit it to some arbitrarily selected pattern.