[Guest]

the challenge is to generate the most random sequence of integers you can given some maximum, n.

the primary restricion: no modulus function! (that's just too easy.)

since most built in RNG functions use this, this means no built in ones either.

your program will be evaluated on 3 things.

length (how long your program goes before it repeats. (note: every submmited alrogithm should repeat eventually. it's okay if it doesn't repeat within the alloted number of runs, but it should repeat.))

distribution (how evenly it gets to all or most numbers. (a score of 1 to n))

space (the average distance between the next showing of a particualar value)

the score will be: length/n *distribution *space.

for the purposes of this contest, n will be 100, 1,000, and 10,000. each generator will be run 10,000, 1,000,000 and 100,000,000 times respectively. questions/ comments?

[unreality]

I'm in! There's a loophole in the scoring system though. If I just list the numbers 1 through n, I'll get the maximum score. My length/n factor will be 1.00, my distribution score will be n, and my space will also be n so I'll get n^2 which I think is the maximum score if I have read correctly

[Guest]

no you can get a higher score. length in particular can be the up to the number of runs.

but perhaps your right and i should add a predictability, a score based on the inversion number bushido posted about. (basically how long does it take to sort?)

[unreality]

'Length' can't possibly be longer than n without shortening 'space'.

[Guest]

right but you wouldn't necessarily meed to shorten it by much.

i mean you could have the following sequence, 1 - 100 in order then 2-99 followed by 1, then 3 -98 followed by 1,2 etc. while a slight lowering of space, there is no repeated sequence for a while.

thinking on it, i should replace length with unpredictability.

[unreality]

why not have the whole score be based on unpredictability? Because isn't that the point of PRNGs? Or, hmmm, it seems a distribution factor of some kind is still necessary. Were you thinking (if the range is 1 to n, and the generator produces N such random numbers), each number should have a 1/n chance of coming up on average. There could be an error score equal to the sum of the absolute values of the differings from this 1/n mean, divided by N. Or use a standard deviation formula instead, with the squares and square root. Or were you thinking of taking a bunch of cross sections of size n and calculating how many of the numbers between 1 and n were represented in that chunk, then taking the average over all chunks? Or something. I think the most fair is the standard deviation or the MAD deviation... for example if n=100 and N=10000. Then for k = 1 to n, find the number of times k occurs and divide by N, and compare to the mean of 1/n... so for standard dev, subtract f(k)/N - 1/n, square it, add em all together, divide by n, square root. I think that's the formula (or is there something about dividing by n-1?) Or MAD would just be take the absolute value of f(k)/N - 1/n, then averaging these.

Anyway the distribution is the easy part to calculate. The hard one is how to calculate unpredictability? I like the idea of length & space but as we've just seen I think it'd mostly be people trying to break the system by finding nonrandom patterns that could maximize the score. Which might be fun in and of itself but still defeats the original point

whatever you decide I'm in, but I hesitate to start designing my algorithm before I know exactly how it's being graded. Also should n maybe be fixed? With three different n's, that's three different algorithms maybe, depending on whether the algorithm is scalable. Or maybe scalability is desired? ahh so many factors haha

[Guest]

your function should be scalable at least up to 10000.

basically what i'll do is take 10, 100, and 1000, randomly selected chunks of size n.

from this, i'll do the following:

for distribution, right, the total number of times each number appears, divided by the total chunk size, -1/n, and average.

for unpredictability, i'll run a shell sort on each chunk, and count the total number of swaps.

the average of these will be your unpredictability score. (so in other words unpredictability will be your biggest score. being up to n *log 2 n)

for spacing, that's pretty simple and straight-forward.

Edited December 29, 2010 by phillip1882