How can I randomly iterate through a large Range?

I just remembered a similar problem from a class I took years ago; that is, iterating (relatively) randomly through a set (completely exhausting it) given extremely tight memory constraints. If I'm remembering this correctly, our solution algorithm was something like this:

1. Define the range to be from 0 tosome number N
2. Generate a random starting point x[0] inside N
3. Generate an iterator Q less than N
4. Generate successive points x[n] by adding Q tothe previous point and wrapping around if needed. Thatis, x[n+1] = (x[n] + Q) % N
5. Repeat until you generate a new point equal to the starting point.

The trick is to find an iterator that will let you traverse the entire range without generating the same value twice. If I'm remembering correctly, any relatively prime N and Q will work (the closer the number to the bounds of the range the less 'random' the input). In that case, a prime number that is not a factor of N should work. You can also swap bytes/nibbles in the resulting number to change the pattern with which the generated points "jump around" in N.

This algorithm only requires the starting point (x[0]), the current point (x[n]), the iterator value (Q), and the range limit (N) to be stored.

Perhaps someone else remembers this algorithm and can verify if I'm remembering it correctly?

As @Turtle answered, you problem doesn't have a solution. @KandadaBoggu and @bta solution gives you random numbers is some ranges which are or are not random. You get clusters of numbers.

But I don't know why you care about double occurence of the same number. If (0..99**99) is your range, then if you could generate 10^10 random numbers per second (if you have a 3 GHz processor and about 4 cores on which you generate one random number per CPU cycle - which is imposible, and ruby will even slow it down a lot), then it would take about 10^180 years to exhaust all the numbers. You have also probability about 10^-180 that two identical numbers will be generated during a whole year. Our universe has probably about 10^9 years, so if your computer could start calculation when the time began, then you would have probability about 10^-170 that two identical numbers were generated. In the other words - practicaly it is imposible and you don't have to care about it.

Even if you would use Jaguar (top 1 from www.top500.org supercomputers) with only this one task, you still need 10^174 years to get all numbers.

If you don't belive me, try

tried = {} # store previous attemptsbigint = 99**99bigint.times {  x = rand(bigint)  puts "Oh, no!" if tried[x]  tried[x] = true}

I'll buy you a beer if you will even once see "Oh, no!" on your screen during your life time :)

I could be wrong, but I don't think this is doable without storing some state. At the very least, you're going to need some state.

Even if you only use one bit per value (has this value been tried yes or no) then you will need X/8 bytes of memory to store the result (where X is the largest number). Assuming that you have 2GB of free memory, this would leave you with more than 16 million numbers.