2
\$\begingroup\$

Task

Develop some code to generate a psuedo-random number between X and Y (taken as input). Explain why or how it works.

Conditions

  • Do not use any random generating seeds, pre-written randoms, or external source to generate the random number.
  • Make something as close to random as you can get. No hard coding of values.

Whoever gets the most upvotes for a new, innovative, out of the box, idea, wins.

\$\endgroup\$

closed as not a real question by dmckee Aug 2 '12 at 15:38

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ Are we supposed to generate a seemingly random number (or sequence of numbers) that can still be the same every time run, or do we need to get different numbers for each run. For the latter we positively need some source of an external seed that differs for each time run, which might be time or a file we've written to on our last run. \$\endgroup\$ – shiona Jul 31 '12 at 20:04
  • 2
    \$\begingroup\$ Is this a golf or a challenge ? The question says golf but the tag says challenge ? \$\endgroup\$ – Paul R Jul 31 '12 at 22:07
  • 3
    \$\begingroup\$ "Most votes" is not an objective winning criterion in the meaning of the FAQ. The winner should be obvious to a person examining the entries. Otherwise we have a simple popularity contest. \$\endgroup\$ – dmckee Aug 2 '12 at 15:40
  • 4
    \$\begingroup\$ 7 answers to a question that is apparently "not a real question". This site has so many negative people on it. Why does everything have to be objective? Photography competitions are subjective; is there not some art to solving many of these problems? \$\endgroup\$ – Griffin Aug 2 '12 at 15:42
  • 6
    \$\begingroup\$ The SO asked the readers to judge submitted routines for a pseudo random number generator, taking into account the degree to which the proposals demonstrate original, "out of the box" thinking. This is admittedly subjective, but fully reasonable as a code challenge. The question is real. It is not ambiguous, vague, incomplete or rhetorical. It can be reasonably answered, as several submissions already made clear. It should not have been closed. \$\endgroup\$ – DavidC Aug 2 '12 at 16:39
4
\$\begingroup\$

C

not sure if the volatile keyword is needed (or what other OS dependencies are assumed here)

simply takes the address of a variable, and maps it to [min, max]:

int rand(int min, int max)
{
  volatile int order = max - min + 1;
  return min + (int)&order % order;
}
\$\endgroup\$
  • \$\begingroup\$ this uses rand( generally the goal of this was to avoid using such tools \$\endgroup\$ – NRGdallas Aug 1 '12 at 18:28
  • 9
    \$\begingroup\$ @NRGdallas uses rand? are you talking about what i named the subroutine? this solution uses no library routines. \$\endgroup\$ – ardnew Aug 1 '12 at 18:46
  • 1
    \$\begingroup\$ This is a relatively clever way of getting one random number, so I hardly call it an rng. Due to data alignment the code (at least on my machine) will output only even numbers. I get almost only negative numbers, since the address of order is high enough to be seen as a negative in and in C(++) the %-operator takes its sign from the dividend. Still the most innovative. +1 \$\endgroup\$ – shiona Aug 2 '12 at 14:10
1
\$\begingroup\$

Mathematica

Rationale

Pi is an irrational number. It decimal representation does not repeat.

I strongly suspect that it does not "favor" any of the base ten digits, 0...9, nor any numbers of length when one partitions the decimal into strings of d digits. This suspicion can later be informally checked using the code below.

Code

The following will select integers between the integers x and y, where x is less than y.
y need not have the same number digits as x. The routine will begin at the cth digit of Pi. At the end of the procedure, the counter will be at c + n.

ClearAll[f]
f[x_,y_,c_,n_]:=
  Module[{diff=y-x,d},
  d=Length[IntegerDigits[diff]];
  Cases[FromDigits/@Most[IntegerDigits[Round[N[Pi,c+n+1]10^(c+n-1)]]][[c;;c+n1]]~Partition~d,
  i_/; i>x-1 && i<y+1]]

Suppose we want to generate a large (> 3000000), pseudo-random list of integers between 7 and 78. Here is how to request it. I've estimated that we'll need to use about 10^7 digits of Pi. We'll begin from position 1, that is, c=1.

(results= f[7,78,1, 10^7])//Timing

results

Note how the unsorted and untallied results maintain the order of Pi's digits: 314159... Note also that the result took just under 20 seconds. As we move further along, we'll encounter practical limits to how much we can process in a reasonable amount of time. But since this is merely an exercise in thinking out of the box, we'll ignore this limitation as we proceed.

Examining the results

When we tally and plot the results we see that Pi does not particularly favor any numbers in this range:

SortBy[Tally[results],First]

tally

Notice that the integers between 7 and 78 were chosen more or less with equanimity. Further tests would show this holds up.

ListPlot[%]

listplot

Similar checks should show whether or not Pi plays favorites with any numbers at all, regardless of how many digits it holds. [I checked for 1, 2, and 3 digit numbers over tens of millions of draws and found no bias starting from the beginning of Pi. A rigorous check would require more systematic examination or theoretical insights.]

\$\endgroup\$
1
\$\begingroup\$

Perl

First, here is a solution that was golfed, coming in at 30 characters:

$a=<>;$b=<>;print$$%($b-$a)+$a

This solution uses the process number of the program as the random seed, similar to using the location of the variables as a seed. It works the best when the min and max are small compared to the process number.

Here is a version that uses command line arguments, with 36 chars:

 print$$%($ARGV[1]-$ARGV[0])+$ARGV[0]

And here is a version as a subroutine that returns the random value (without printing to screen), with 29 chars:

 sub a{$$%($_[1]-$_[0])+$_[0]}

Second, I am working on a solution that adheres to the strictest reading of the spec, which is that the program cannot be influenced by anything except the two arguments.

\$\endgroup\$
  • \$\begingroup\$ I don't know Perl syntax very well, but couldn't you declare $ARGV as another, shorter, variable? Or just the value of $ARGV[0] to save a few characters? \$\endgroup\$ – MrZander Aug 2 '12 at 17:09
  • \$\begingroup\$ The array @ARGV is how the command line arguments are read. By removing them, I would have to take the input a different way. \$\endgroup\$ – PhiNotPi Aug 2 '12 at 18:18
  • 1
    \$\begingroup\$ Actually, it appears that by taking input from STDIN, while causing me to add $a=<>;$b=<>;, actually saved me characters. \$\endgroup\$ – PhiNotPi Aug 2 '12 at 18:26
0
\$\begingroup\$

Python

import sha
R=lambda x,y:x+int(sha.new('%d_%d'%(x,y)).hexdigest(),16)%(y-x)
\$\endgroup\$
  • \$\begingroup\$ Gives you the same output if you provide the same x and y. \$\endgroup\$ – MrZander Jul 31 '12 at 22:29
  • \$\begingroup\$ @MrZander: the way I interpret the spec, that is inevitable. \$\endgroup\$ – Keith Randall Jul 31 '12 at 23:38
  • 1
    \$\begingroup\$ Hardly "innovative", why not just multiply it by the time or something like that? \$\endgroup\$ – MrZander Aug 1 '12 at 0:01
  • \$\begingroup\$ @MrZander because time is external source. If you can use time then just take microseconds since boot and map it to the given range. \$\endgroup\$ – shiona Aug 1 '12 at 9:33
  • \$\begingroup\$ Maybe I am interpreting it differently. I see "external source to generate the random" as an external source designed for random number generation. Up for interpretation, I guess. \$\endgroup\$ – MrZander Aug 1 '12 at 16:48
0
\$\begingroup\$

JavaScript

function getRandom(x,y) {
    s=document.createElement("SCRIPT");
    s.src="http://search.twitter.com/search.json?q=%22random%22&&callback=t"
    document.getElementsByTagName("HEAD")[0].appendChild(s);
    var c = 0;
    window.t=function (d) {
        g=d.results;
        for(z=0; z<g.length; z++) {
            c+=g[z].id/0xfff;
        }
        console.log(x+c%(y-x))
    };
}

This is pretty disgusting really. Queries Twitter, via the JASONP API, for recent tweets containing the word "random", then it uses the ID's of each of the returned tweets to calculate the "random" number.

You might want to wait a few seconds in between each call of the function, also it doesn't return a value, it just outputs one to the console. (Told you it was disgusting).

You can try it here.

\$\endgroup\$
  • 3
    \$\begingroup\$ Nice idea, but without using ANY [...] external source. \$\endgroup\$ – kaoD Jul 31 '12 at 23:25
  • \$\begingroup\$ using twitter API, I actually think its pretty creative. Read the above comment on the post for "any external source" it has been clarified to also show this is OK :) \$\endgroup\$ – NRGdallas Aug 1 '12 at 18:31
  • \$\begingroup\$ @NRGdallas, thanks for clarifying. That's what I thought you meant by external source. \$\endgroup\$ – Griffin Aug 1 '12 at 20:43
0
\$\begingroup\$

Python 2.x, 454

z=lambda n,b:int("0b"+(bin(n)[2:][:-b]or'0'),2)
r=range
g=624
def m(s,t):
 a=[s]
 for i in r(1,g): a+=[1812433253*((a[i-1]^(a[i-1]>>30))+i)]
 for i in r(t):
    i%=g
    if not i:
        q=0
        for c,d in zip(a,a[1:]+[a[0]]):
            u=(z(c,1)+z(d%g,31))
            a[q]=a[(q+397)%g]^(u>>1)
            if u%2:a[q]^=2567483615
            q+=1
    y=a[i]^(a[i]>>11)
    y^=(y<<7&2636928640)
    y^=(y<<15&4022730752)
    y^=(y>>18)
    yield y

Mersenne twister algorithm. It can probably be golfed some more.

Usage:

>>> list(m(s, t))

Where s is the seed, and t is the number of numbers to generate.

\$\endgroup\$
  • \$\begingroup\$ Unfortunately your hands are much more tied: without using ANY random generating seeds \$\endgroup\$ – kaoD Aug 1 '12 at 14:45
  • \$\begingroup\$ Do you mean "without using any external seed"? If I set seed to a constant value, for example, would that satisfy the terms of the challenge? \$\endgroup\$ – Joel Cornett Aug 1 '12 at 17:33
  • \$\begingroup\$ I guess that wouldn't be random then, but a constant. That's the challeng (though I'm not the challenge author, so feel free to ask him in comments.) \$\endgroup\$ – kaoD Aug 1 '12 at 21:35
0
\$\begingroup\$

Python, 32

Similar to ardnew's answer:

a,b=input()
print a+id(1)%(b-a)
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.