StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POHow can I randomly iterate through a large Range?
text
Body
copied!<p>I would like to randomly iterate through a range. Each value will be visited only once and all values will eventually be visited. For example:</p> <pre><code>class Array def shuffle ret = dup j = length i = 0 while j > 1 r = i + rand(j) ret[i], ret[r] = ret[r], ret[i] i += 1 j -= 1 end ret end end (0..9).to_a.shuffle.each{|x| f(x)} </code></pre> <p>where <code>f(x)</code> is some function that operates on each value. A <a href="http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle" rel="noreferrer">Fisher-Yates shuffle</a> is used to efficiently provide random ordering.</p> <p>My problem is that <code>shuffle</code> needs to operate on an array, which is not cool because I am working with <strong>astronomically</strong> large numbers. Ruby will quickly consume a large amount of RAM trying to create a monstrous array. Imagine replacing <code>(0..9)</code> with <code>(0..99**99)</code>. This is also why the following code will not work:</p> <pre><code>tried = {} # store previous attempts bigint = 99**99 bigint.times { x = rand(bigint) redo if tried[x] tried[x] = true f(x) # some function } </code></pre> <p>This code is very naive and quickly runs out of memory as <code>tried</code> obtains more entries.</p> <p>What sort of algorithm can accomplish what I am trying to do?</p> <p><strong>[Edit1]</strong>: Why do I want to do this? I'm trying to exhaust the search space of a hash algorithm for a N-length input string looking for partial collisions. Each number I generate is equivalent to a unique input string, entropy and all. Basically, I'm "counting" using a <a href="http://thebaconoflife.com/b/2009/08/15/base-64-url-encodingcounting/" rel="noreferrer">custom alphabet</a>.</p> <p><strong>[Edit2]</strong>: This means that <code>f(x)</code> in the above examples is a method that generates a hash and compares it to a constant, target hash for partial collisions. I do not need to store the value of <code>x</code> after I call <code>f(x)</code> so memory should remain constant over time.</p> <p><strong>[Edit3/4/5/6]</strong>: Further clarification/fixes.</p> <p><strong>[Solution]</strong>: The following code is based on @bta's solution. For the sake of conciseness, <code>next_prime</code> is not shown. It produces acceptable randomness and only visits each number once. See the actual post for more details.</p> <pre><code>N = size_of_range Q = ( 2 * N / (1 + Math.sqrt(5)) ).to_i.next_prime START = rand(N) x = START nil until f( x = (x + Q) % N ) == START # assuming f(x) returns x </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload