OpenEuphoria

Re: random numbers

• Posted by Ricardo Forno <ricardoforno at tuto?ia.?om> Nov 22, 2007
• 558 views

c.k.lester wrote:
> 
> Derek Parnell wrote:
> > Hey jiri! I knew I should have left it to the master. Your routine is about
> > 385% faster than my first try.
> 
> Yeah, Jiri's is fast! So, how do you measure randomness?
> I know there are tests for it. I'm wondering if jiri's algorithm allows for
> every possible permutation. I sped up your original first try, Derek. Look
> at shuff3(). But I don't know if that ruins the algorithm or messes with
> the randomness.
> 
> Here's an updated look:
> 
> }}}
<eucode>include misc.e
> include get.e
> 
> constant fittytwo =
> {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52}
> 
> sequence tests
> 	tests = {{},{}}
> 	
> procedure add_test(sequence name, atom id)
> 	tests[1] = append(tests[1],name)
> 	tests[2] &= id
> end procedure
> 
> function shuff1()
> sequence s, n
> integer r
> s = fittytwo
> n = repeat(0,52)
> for t=1 to 52 do
>    r = rand(length(s)) -- grab a random position
>    n[t] = s[r] -- add it to our new sequence
>    s = s[1..r-1] & s[r+1..$] -- remove from available numbers
> end for
> return n
> end function
> 
> function shuff3()
>     sequence s, n
>     integer r
>     s = fittytwo
>     n = repeat(0,52)
>     for t=52 to 2 by -1 do
>      r = rand(t) -- grab a random position
>      n[t] = s[r] -- add it to our new sequence
>      s[r..51] = s[r+1..52]-- remove from available numbers
>     end for
>     n[1] = s[1]
>     return n
>   end function
> 
> function shuff4()
>     sequence s, n
>     integer r
>     s = fittytwo
>     n = repeat(0,52)
>     for t=52 to 2 by -1 do
>      r = rand(t) -- grab a random position
>      n[t] = s[r] -- add it to our new sequence
>      s[r..t-1] = s[r+1..t]-- remove from available numbers -- Derek, this is
>      what I changed
>     end for
>     n[1] = s[1]
>     return n
>   end function
> 
> function shuff5()
>     object temp
>     integer r
>     sequence s
>     s = fittytwo
>     for i = length(s) to 2 by -1 do
>         r = rand(i)
>         temp = s[r]
>         s[r] = s[i]
>         s[i] = temp
>     end for
>     return s
> end function
> 
> procedure run_tests()
> atom c, t
> sequence test
> integer secs
> 
> for x=1 to length( tests[1]) do
> 	c=0
> 	secs = 1
> 	
> 	puts(1,"Starting test " & tests[1][x] & "\n")
> 	
> 	t = time() + secs
> 	while t > time() do
> 		test = call_func(tests[2][x],{})
> 		c += 1
> 	end while
> 	?test
> 	printf(1,"\t%d\n\n",{c})
> end for
> 
> end procedure
> 
> add_test("Baseline",routine_id("shuff1"))
> add_test("Derek's First",routine_id("shuff3"))
> add_test("Derek's First Modified",routine_id("shuff4"))
> add_test("Jiri's Speed Demon",routine_id("shuff5"))
> 
> run_tests()
> 
> puts(1,"\nDone! Press any key to quit.")
> if wait_key() then end if</eucode>
{{{


An almost identical routine is included in my General Functions package.
Here it is:

--/topic STATISTICS / PROBABILITIES ROUTINES
--/func Scramble(sequence s)
--/desc Scrambles, that is, disorders a sequence
--/ret The argument in random order
--Returns sequence 's' scrambled, that is, the resulting sequence contains
-- the elements of 's' in random order.
--Example: Scramble("Mandrake") might give "kadnMare"
global function Scramble(sequence s)
    integer len, k
    object temp
    len = length(s)
    for i = 1 to len do
	k = rand(len)
	temp = s[k]
	s[k] = s[i]
	s[i] = temp
    end for
    return s
end function

I later learnt that Donald Knuth was probably the first one to design this
algorithm, and that he showed it really randomly ordered (or disordered ) a
sequence.

Regards.