26
\$\begingroup\$

Task

Given a positive integer n less than 2^30 specified as input in any way you choose, your code should output a random integer between 0 and n, inclusive. The number you generate should be chosen uniformly at random. That is each value from 0 to n must occur with equal probability (see Rules and Caveats).

Rules and Caveats

Your code can assume that any random number generator built into your language or standard library that claims to be uniformly random is in fact uniform. That is you don't have to worry about the quality of the random source you are using. However,

  • You do have to establish that if the random source you are using is uniform then your code correctly outputs a uniform random integer from 0 to n.
  • Any arguments when calling a built in or library random function must be constant. That is they must be completely independent of the input value.
  • Your code may terminate with probability 1 rather than being guaranteed to terminate.

Notes

  • randInt(0,n) is not valid as it takes the input as an argument to a builtin or library function.
  • rand()%n will not give a uniform random number in general. As an example given by betseg, if intmax == 15 and n = 10, then you will be much more likely to get 0-5 than 6-10.
  • floor(randomfloat()*(n+1)) will also not give a uniform random number in general due to the finite number of different possible floating point values between 0 and 1.
\$\endgroup\$
  • \$\begingroup\$ How are you going to confirm that the output is uniformly random? It may be that a given language / library will output uniformly random numbers, but manipulation could result in non-uniform output. (e.g. rng() provides 0-100, if n = 75, and function is rng()%75, then 0-25 will be more common...) \$\endgroup\$ – Baldrickk Mar 1 '17 at 16:12
  • 1
    \$\begingroup\$ @Baldrickk By the wisdom of crowds :) We can only read the code and think about it. \$\endgroup\$ – user9206 Mar 1 '17 at 16:13
  • \$\begingroup\$ The sad conclusion of asking the simplest possible probability-theory question: randomness and probability are very poorly understood. :( (And reading rules is hard, apparently.) \$\endgroup\$ – Martin Ender Mar 1 '17 at 22:11
  • \$\begingroup\$ This comes to mind: Random Number \$\endgroup\$ – BgrWorker Mar 2 '17 at 9:05
  • \$\begingroup\$ Why did you accept the x86 answer when there are three shorter ones? \$\endgroup\$ – Dennis Mar 30 '17 at 16:30

32 Answers 32

25
\$\begingroup\$

x86 machines with rdrand instruction, 10 bytes

BITS 64

_try_again:

 rdrand eax
jnc _try_again

 cmp eax, edi
ja _try_again

 ret

machine code

0FC7F0 73FB 39F8 77F7 C3

The input is in the register rdi and the output in rax.
This respects the SYS V AMD64 ABI so the code effectively implement a C function

unsigned int foo(unsigned int max); 

with 32-bit ints.

The instruction rdrand is described by Intel

RDRAND returns random numbers that are supplied by a cryptographically secure, deterministic random bit generator DRBG. The DRBG is designed to meet the NIST SP 800-90A standard.

Dealing with CSRNG it is implicit that the distribution is uniform, anyway, quoting the NIST SP 800-90A:

A random number is an instance of an unbiased random variable, that is, the output produced by a uniformly distributed random process.


The procedure generates a random number and if it is non-strictly greater than the input it is returned.
Otherwise, the process is reiterated.

Since eax is 32-bit, rdrand returns a number between 0 and 232-1, so for every n in [0, 232-1] the number of expected iterations is 232/(n+1) which is defined for all n in [0, 230).

\$\endgroup\$
  • \$\begingroup\$ Brilliantly low level. Thank you. \$\endgroup\$ – user9206 Feb 28 '17 at 15:22
  • \$\begingroup\$ What's the jnc for? \$\endgroup\$ – l4m2 May 27 '18 at 17:04
  • \$\begingroup\$ @l4m2 rdrand sets the CF iif the data returned is valid. Data may be invalid because too many requests drained the entropy pool. See the manual entry for rdrand and this. \$\endgroup\$ – Margaret Bloom May 27 '18 at 20:30
20
\$\begingroup\$

Jelly, 7 6 bytes

⁴!!X%‘

Thanks to @JonathanAllan for golfing off 1 byte!

Cannot be run on TIO because (16!)! is a huge number.

How it works

⁴!!X%‘  Main link. Argument: n

⁴       Set the return value to 16.
 !!     Compute (16!)!.
   X    Pseudo-randomly choose an integer between 1 and (16!)!.
        Since (16!)! is evenly divisible by any k ≤ 2**30, it is evenly divisible
        by n+1.
    %‘  Take the result modulo n+1.
\$\endgroup\$
  • \$\begingroup\$ This is a fixed version of my deleted answer, same idea. Although I did have an unnecessary exponentiation. \$\endgroup\$ – orlp Feb 28 '17 at 14:10
  • \$\begingroup\$ Sorry, I didn't look at it before posting. \$\endgroup\$ – Dennis Feb 28 '17 at 14:19
  • \$\begingroup\$ Oh it doesn't matter, I wasn't planning fixing it anyway. I'm too uncomfortable with Jelly to really play around with it. \$\endgroup\$ – orlp Feb 28 '17 at 14:26
  • 1
    \$\begingroup\$ "Sir I don't know why you're mad. The algorithm is constant time. That's a good thing, right? Why is security and HR outside the door?" \$\endgroup\$ – corsiKa Mar 2 '17 at 3:31
  • 1
    \$\begingroup\$ Agreed. Bit of a difference between an 8 digit number and a 417 quintillion digit number :p \$\endgroup\$ – Jonathan Allan Mar 2 '17 at 12:37
11
\$\begingroup\$

Mathematica, 29 bytes

Based on Dennis's Jelly answer.

RandomInteger[2*^9!-1]~Mod~#&

I wouldn't recommend actually running this. 2e9! is a pretty big number...

It turns out to be shortest to generate a huge number that is divisible by all possible inputs and the map the result to the required range with a simple modulo.

Rejection Sampling, 34 bytes

My old approach that led to somewhat more interesting code:

13!//.x_/;x>#:>RandomInteger[13!]&

Basic rejection sampling. We initialise the output to 13! (which is larger than the maximum input 230) and then repeatedly replace it with a random integer between 0 and 13! as long as the value is bigger than the input.

\$\endgroup\$
  • 1
    \$\begingroup\$ Do you mean "smaller than or equal to the input" ? \$\endgroup\$ – user9206 Feb 28 '17 at 10:25
  • 1
    \$\begingroup\$ @Lembik No. We want to regenerate the value as long as it doesn't fall into the desired range. \$\endgroup\$ – Martin Ender Feb 28 '17 at 10:26
  • \$\begingroup\$ Oh I see. For some reason I thought we were repeatedly sampling from the desired range. Thanks. \$\endgroup\$ – user9206 Feb 28 '17 at 10:26
  • 1
    \$\begingroup\$ Remind me to add a time limit next time :) \$\endgroup\$ – user9206 Mar 1 '17 at 15:38
9
\$\begingroup\$

Brachylog, 9 bytes

≥.∧13ḟṙ|↰

Try it online!

This uses 13! like in Martin Ender's answer (13ḟ is one byte less than 2^₃₀).

is implemented using random_between/3, which, when digging its source, uses random_float/0 which is linked to random/1 which uses the Mersenne Twister algorithm which is uniform for our purposes.

Explanation

≥.           Input ≥ Output
  ∧          And
   13ḟṙ      Output = rand(0, 13!)
       |     Else
        ↰    Call recursively with the same input
\$\endgroup\$
7
\$\begingroup\$

Prolog (SWI), 38 bytes

X*Y:-Z is 2^31,random(0,Z,Y),Y=<X;X*Y.

Works by rejection sampling.

Generate a random number between 0 and 2^31-1 = 2147483647 until one less than or equal to the input has been found.

I feel as if I should be able to use a cut instead of the else, but I can't see how.

\$\endgroup\$
  • 1
    \$\begingroup\$ You could avoid the else using repeat, but it ends up being 3 bytes longer… I'm not sure if there is a shorter way of having infinite choice points than repeat. \$\endgroup\$ – Fatalize Feb 28 '17 at 14:17
  • \$\begingroup\$ @Fatalize: Yeah I tried repeat as well. I had a memory of using something like ,!. to force a backtrack, but either I'm remembering it wrong or it's not applicable to this solution. \$\endgroup\$ – Emigna Feb 28 '17 at 14:22
7
\$\begingroup\$

Labyrinth, 63 bytes

 ?
 #00}__""*_
 ;    #"  _
{-{=  } "><)
!{ : ;"({ +
@  }}:  >`#

(Thanks to @MartinEnder for help with some heavy golfing here.)

Labyrinth is a 2D language, and its only source of randomness is in a situation like the following:

   x
  "<)
 " "
 " "

Assume the instruction pointer is on the x and moving downwards. It next lands on the <, which if the top of stack is 0 (which is always the case in the actual program above) shifts the current row left by 1:

   "
 "<)
 " "
 " "

The instruction pointer is now on the < moving downwards. At a junction, Labyrinth turns based on the top of stack - negative is turn left, positive is turn right and zero is move forward. If the top of stack is still zero at this point, we can't move forward or backward since there's no path, so Labyrinth will randomise between turning left or turning right with equal probability.

Essentially what the program above does is use the randomness feature to generate 100-bit numbers (100 specified by #00 here) and continue looping until it generates a number <= n.

For testing, it'll probably help to use #0" instead for 10-bit numbers, with the " being a no-op path. Try it online!

Rough explanation:

 ?            <--- ? is input and starting point
 #0"}__""*_   <--- * here: first run is *0, after that is *2 to double
 ;    #"  _
{-{=  } "><)  <--- Randomness section, +0 or +1 depending on path.
!{ : ;"({ +        After <, the >s reset the row for the next inner loop.
@  }}:  >`#

 ^    ^
 |    |
 |    The " junction in this column checks whether the
 |    100-bit number has been generated, and if not then
 |    continue by turning right into }.
 |
 Minus sign junction here checks whether the generated number <= n.
 If so, head into the output area (! is output as num, @ is terminate).
 Otherwise, head up and do the outer loop all over again.
\$\endgroup\$
7
\$\begingroup\$

Python, 61 bytes

from random import*
lambda n,x=2.**30:int(randrange(x)*-~n/x)

Edit: Updated to avoid forbidden form

Edit2: Saved 2 bytes, thanks @JonathanAllan

Edit3: Paid 2 bytes for a fully functional solution - thanks again @JonathanAllan

Edit4: Removed f=, saving 2 bytes

Edit5: Saved 1 more byte thanks to @JonathanAllan

Edit6: Saved 2 more bytes thanks to @JonathanAllan

By now, git blame would point at me for the bad things, and JonathanAllan for the stuff that helps.

Edit7: When it rains, it pours - another 2 bytes

Edit8: And another 2 bytes

\$\endgroup\$
  • 1
    \$\begingroup\$ This wont ever output n, but you can save two bytes when you fix that by using from random import* and dropping the r.. \$\endgroup\$ – Jonathan Allan Feb 28 '17 at 13:28
  • 1
    \$\begingroup\$ Yes, you can use the "tadpole operator" to avoid the otherwise necessary parentheses, so ...*(-~n*1.0/2**30)) rather than ...*((n+1)*1.0/2**30)) \$\endgroup\$ – Jonathan Allan Feb 28 '17 at 13:36
  • 1
    \$\begingroup\$ Really? Sweet! Do you have some long-standing grudge against the number 70? Thanks a lot for your help \$\endgroup\$ – iwaseatenbyagrue Feb 28 '17 at 13:42
  • 1
    \$\begingroup\$ In fact randrange seems to accept a float, so lambda n,x=2.**30:int(randrange(x)*-~n/x) saves another two [edit...] four! \$\endgroup\$ – Jonathan Allan Feb 28 '17 at 14:02
  • 1
    \$\begingroup\$ ^ another two in there with parentheses removal. Just goes to show your multiplication was the way to go! \$\endgroup\$ – Jonathan Allan Feb 28 '17 at 14:08
6
\$\begingroup\$

Python 2, 61 bytes

from random import*
lambda n:map(randrange,range(1,2**31))[n]

Pseudo-randomly chooses integers between 0 and k for all values of k between 0 and 231 - 2, then takes the integer corresponding to k = n.

\$\endgroup\$
5
\$\begingroup\$

Batch, 64 bytes

@set/ar=%random%*32768+%random%
@if %r% gtr %1 %0 %1
@echo %r%

%random% only gives 15 bits of randomness, so I have to combine two random numbers. Loops until the random value lies within the desired range, so slow for low n; 98 bytes for a faster version:

@set/a"n=%1+1,m=~(3<<30)/n*n,r=%random%*32768+%random%
@if %r% geq %m% %0 %1
@cmd/cset/a%r%%%%n%
\$\endgroup\$
  • \$\begingroup\$ The code may be slow but your answer was fast! \$\endgroup\$ – user9206 Feb 28 '17 at 10:22
  • 3
    \$\begingroup\$ @Lembik I had the answer ready to go in your deleted question... \$\endgroup\$ – Neil Feb 28 '17 at 10:25
  • \$\begingroup\$ Won't this echo the desired number first, and then all other numbers which turned to be larger than n? \$\endgroup\$ – Erik the Outgolfer Feb 28 '17 at 12:01
  • \$\begingroup\$ @EriktheOutgolfer No; unless you use call, invoking a batch script terminates the current script. \$\endgroup\$ – Neil Feb 28 '17 at 16:03
5
\$\begingroup\$

MATL, 12 bytes

Thanks to @AdmBorkBork and to @Suever for telling me how to disable TIO cache.

`30WYrqG>}2M

Try it online!.

This uses a rejection method: generate a random integer from 0 to 2^30-1, and repeat while it exceeds the input n. This is guaranteed to terminate with probability 1, but the average number of iterations is 2^30/n, and so it takes very long for n significantly smaller than 2^30.

`         % Do...while
  30W     %   Push 2^30
  Yr      %   Random integer from 1 to 2^30
  q       %   Subtract 1
  G>      %   Does it exceed the input? If so: next iteration. Else: exit
}         % Finally (execute right before exiting the loop)
  2M      %   Push the last generated integer
          % End (implicit). Display (implicit)
\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 55 54 bytes

f=(n,m=1)=>m>n?(x=Math.random()*m|0)>n?f(n):x:f(n,m*2)

Generates integers in the range [0 ... 2k - 1], where k is the smallest integer such that 2k is greater than n. Repeats until the result falls into [0 ... n].

Why?

This is based on the following assumptions:

  • Internally, the pseudo-random integer values generated by the JS engine to feed Math.random() are uniform over any interval [0 ... 2k-1] (with k < 32).

  • Once multiplied by an exact power of 2, the IEEE 754 float values returned by Math.random() are still uniform over such intervals.

If anyone can confirm or refute these hypotheses, please let me know in the comments.

Demo

Generates 1 million values in [0 ... 2] and displays the outcome statistics.

f=(n,m=1)=>m>n?(x=Math.random()*m|0)>n?f(n):x:f(n,m*2)

for(i = 0, stat = []; i < 1000000; i++) {
  r = f(2);
  stat[r] = (stat[r] || 0) + 1;
}
console.log(stat.join` `)

\$\endgroup\$
  • \$\begingroup\$ Math.floor(Math.random()*(n+1)) produces a no less uniformly distributed results for me, so it would be nice to see if there is any realistic N < 2^30, which will produce any distribution anomalies at all. \$\endgroup\$ – zeppelin Mar 1 '17 at 16:23
  • 1
    \$\begingroup\$ @zeppelin you'd need way too many trial runs to pinpoint any anomalies since a random float in that range will have one of 2^53 values which will be distributed as evenly as possible over the 2^30 outcomes. So even for large numbers in the range, the error will be something like 1 in 2^23 which means you'd need a ridiculous number of trials. You'll probably want a few more orders of magnitude than the number of initial samples (2^53). Nevertheless, it can't be perfectly uniform if the multiplier doesn't evenly divide the number of samples which is why Arnauld uses a power of two. \$\endgroup\$ – Martin Ender Mar 1 '17 at 21:52
4
\$\begingroup\$

Bash (+coreutils), 44 bytes

/dev/urandom based solution

od -w4 -vtu4</d*/ur*|awk '($0=$2)<='$1|sed q

Will read unsigned 32 bit integers from /dev/urandom, and filter them out with awk until it finds one within a given range, then sed q will abort the pipe.

\$\endgroup\$
  • \$\begingroup\$ Hooray for bash :) \$\endgroup\$ – user9206 Feb 28 '17 at 15:22
4
\$\begingroup\$

Haskell, 70 bytes

import System.Random
g n=head.filter(<=n).randomRs(0,2^30)<$>getStdGen

Not a very efficient algorithm but it works. It generates an infinite list of integers (or floats if needed, because of Haskell's type system) bounded by [0,2^30] and takes the first one less than or equal to n. For small n this can take a long time. The random numbers should be uniformly distributed, as specified in the documentation for randomR so all numbers in the interval [0,2^30] should have the same probability (1/(2^30+1)) therefore all the numbers in [0,n] have the same probability.

Alternate Version:

import System.Random
g n=head.filter(<=n).map abs.randoms<$>getStdGen

This version is terrible but it saves a whole byte. randoms uses an arbitrary range defined by the type to generate an infinite list of numbers. This may include negatives so we need to map it with abs to force them positive (or zero). This is extremely slow for any values of n that aren't absurdly large. EDIT: I realized later that this version isn't uniformly distributed because the probability of getting 0 is worse than the other numbers due to the use of abs. To produce some number m the generator could produce m or -m but in the case of 0 only 0 itself will work, therefore its probability is half of the other numbers.

\$\endgroup\$
  • \$\begingroup\$ Hooray for Haskell (too)! \$\endgroup\$ – user9206 Feb 28 '17 at 15:34
4
\$\begingroup\$

Jelly, 9 bytes

⁴!Ẋ’>Ðḟ⁸Ṫ

Try it online! - code above wont run on TIO since a range of size 16! must be built first (not to mention the fact that they then need to be shuffled and then filtered!), so this is the same thing on a much smaller scale, repeated 30 times for an input of 3 with a bound of 10.

How?

⁴!Ẋ’>Ðḟ⁸Ṫ - Main link: n
⁴         - 16
 !        - factorial: 20922789888000
  Ẋ       - shuffle random: builds a list of the integers 1 through to 16! inclusive and
          - returns a random permutation via Python's random.shuffle (pretty resource hungry)
   ’      - decrement (vectorises - a whole pass of this huge list!)
     Ðḟ   - filter out if: (yep, yet another pass of this huge list!)
    >     -     greater than
       ⁸  -     left argument, n
        Ṫ - tail: return the rightmost remaining entry.

Note: it would be over a thousand time more efficient for the same byte-count if ȷ⁵ would do what one would naively expect and return ten to the ten, but that is not the case since the is not evaluated as a literal ten to be used by the number literal ȷ... but rather two separate literals are parsed, ȷ with it's default exponent of three yielding one thousand, and yielding ten.

\$\endgroup\$
  • \$\begingroup\$ Huh, thats 9 characters, but 22 bytes \$\endgroup\$ – Kristoffer Sall-Storgaard Mar 2 '17 at 15:17
  • \$\begingroup\$ @KristofferSall-Storgaard Each character is one of the 256 bytes in Jelly's code page, I forgot to make the word bytes a link like I usually do. \$\endgroup\$ – Jonathan Allan Mar 2 '17 at 15:22
  • 1
    \$\begingroup\$ year, I looked it up and found out the same \$\endgroup\$ – Kristoffer Sall-Storgaard Mar 2 '17 at 15:29
4
\$\begingroup\$

JDK 9 on jshell, 75 59 bytes

n->(new Random()).ints(0,1<<30).dropWhile(x->x>n).findAny()

Usage

((IntFunction)(n->(new Random()).ints(0,1<<30).dropWhile(x->x>n).findAny())).apply(<n>)
  • -16 bytes: Thanks Jakob!
  • Assumes that we consider jshell to be a valid runtime environment.
  • jshell itself, as a runtime environment, doesn't require explicit imports for core libraries and doesn't require semicolons.
  • Returns an OptionalInt. Rules don't specify that return type must be a primitive and I'm considering an OptionalInt to be a valid representation of the result.
\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks to @kevin-cruijssen for the inspiration. My first code golf! \$\endgroup\$ – Pete Terlep Mar 1 '17 at 23:37
  • \$\begingroup\$ Whether or not boxed output is accepted is different from whether an Optional is accepted. I would confirm with the poster if I were you. Also, no need to count the whole assignment; just the lambda expression is sufficient. \$\endgroup\$ – Jakob Aug 9 '17 at 13:48
  • 1
    \$\begingroup\$ You can save 4 bytes by removing parentheses around lambda parameter n and new Random(). \$\endgroup\$ – Jakob Aug 9 '17 at 13:49
3
\$\begingroup\$

PHP, 30 bytes

    while($argn<$n=rand());echo$n;

Run with echo <N> | php -Rn '<code>'.

picks a random number between 0 and getrandmax() (2**31-1 on my 64 bit machine);
repeats while that is larger than the input.

This may take a while ... my AMD C-50 (1 GHz) needed between 0.3 and 130 seconds for N=15.

A faster way for average N (46 bytes):

for(;++$i<$x=1+$argn;)$n+=rand()%$x;echo$n%$x;

or

for(;++$i<$x=1+$argn;$n%=$x)$n+=rand();echo$n;

takes N+1 random integers, sums them up and takes the modulo with N+1.
The C-50 needs approx. 8 seconds for 1 million runs.

An invalid solution for 19 bytes:

echo rand(0,$argn);
\$\endgroup\$
3
\$\begingroup\$

PowerShell, 35 bytes

for(;($a=Random 1gb)-gt"$args"){}$a

Try it online!

Another rejection sampling method. This is an infinite for loop, setting the value of $a to be a Random integer between 0 and 1gb (= 1073741824 = 2^30), and keeps looping so long as that integer is -greaterthan the input $args. Once the loop is complete, we just put $a on the pipeline and output is implicit.

Note: This will take a long time if the input is a small number.

\$\endgroup\$
3
\$\begingroup\$

Python 2, 72 69 bytes

-3 bytes thanks to xnor (override the id built-in as a variable)

from random import*
n=input()
while id>n:id=randrange(2**30)
print id

Try it online!

randrange(2**30) produces a pseudo-uniformly distributed number (Mersenne Twister 219937-1) from the range [0,230). Since n is guaranteed to be below 230 this can simply be called repeatedly until it is not greater than the input. It will take a long expected time for very low values of n, but usually works within the a minute even for inputs as low as 50.

\$\endgroup\$
  • 2
    \$\begingroup\$ You can initialize r='' as "infinity". Or, better yet, don't initialize r and instead use id everywhere for r. \$\endgroup\$ – xnor Feb 28 '17 at 17:10
2
\$\begingroup\$

Perl 6, 29 bytes

{first 0..$_,^2**30 .roll(*)}

Inspired by Martin Ender's Mathematica solution.

Generates a lazy infinite sequence of random integers between 0 and 2^30-1, and takes the first one that is between 0 and the input.

Try it online!

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 11 bytes

žIÝ.rDI›_Ϥ

Try it online!

Explanation

žIÝ          # push the inclusive range [0 ... 2^31]
   .r        # get a random permutation (pythons random.shuffle)
     D       # duplicate this list
      I      # push input
       ›_Ï   # keep only elements from the list not greater than input
          ¤  # take the last one

As the list [0 ... 2147483648] is too large for TIO, the link uses 1.000.000 instead.

Alternate (on average) much faster 11 byte solution

[žIÝ.RD¹›_#

Try it online

Explanation

[             # start loop
 žIÝ          # push the inclusive range [0 ... 2^31]
    .R        # pick a random integer (pythons random.chiose)
      D       # duplicate
       ¹      # push input
        ›_#   # break if random number is not greater than input
              # implicitly output top of stack (the random number)
\$\endgroup\$
  • \$\begingroup\$ žJL.R% for 6 unless I'm missing something huge. Push 2^32, list from 0 to 2^32, random pick. Modulo input. Will absolutely screw the efficiency that you have. \$\endgroup\$ – Magic Octopus Urn Mar 1 '17 at 14:33
  • \$\begingroup\$ @carusocomputing.You'd need an I in there for 7 bytes to get the arguments for modulus in the right order (and maybe Ý instead of L), but otherwise that's certainly a shorter solution. I saw Dennis doing that in his Jelly answer, but as this was my first idea I kept this. As that approach is different from this you could post it as a separate answer. \$\endgroup\$ – Emigna Mar 1 '17 at 14:43
  • \$\begingroup\$ DI‹Ï would avoid the loop. \$\endgroup\$ – Magic Octopus Urn Mar 1 '17 at 19:35
  • \$\begingroup\$ Also, as-is, this is not guaranteed to terminate; if I'm not mistaken, an input of 0 would almost always result in a near-infinite loop, making it hard to terminate. Though the solution does allow for the possibility to terminate in all scenarios it isn't guaranteed due to randomness. \$\endgroup\$ – Magic Octopus Urn Mar 1 '17 at 19:41
  • \$\begingroup\$ @carusocomputing: For very small input the second version would on average take a very long time to finish yes, but given enough time it would. \$\endgroup\$ – Emigna Mar 1 '17 at 21:23
2
\$\begingroup\$

Python 2, 89 bytes

l=range(2**31)
import random
random.shuffle(l)
n=input()
print filter(lambda x:x<=n,l)[0]

Explanation

L=range(2**31)      # Create a list from 0 to 2^31 exclusive. Call it <L>.
import random       # Import the module <random>.
random.shuffle(L)   # Use 'shuffle' function from <random> module,
                    # to shuffle the list <L>.
n=input()           # Take the input -> <n>.

print
    filter(         # Create a new sequence,
    lambda x:x<=n   # where each element is less than or equal to <n>.
    ,L)             # from the list <L>.
    [0]             # Take the first element.

This is very inefficient, as it creates 2^31 integers, shuffles and filters them.

I see no point in sharing a TIO link, where it's creating such large lists, so here is a TIO link for n = 100.

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Java 8, 84 83 80 71 62 bytes

n->{int r;for(;(r=(int)(Math.random()*(1<<30)))>n;);return r;}

-1 byte thanks to @OliverGrégoire.
-3 bytes thanks to @Jakob.
-9 bytes converting Java 7 to Java 8.
-9 bytes by changing java.util.Random().nextInt(1<<30) to (int)(Math.random()*(1<<30)).

Explanation:

Try it here.

n->{        // Method with integer parameter and integer return-type
  int r;    //  Result-integer
  for(;(r=(int)(Math.random()*(1<<30)))>n;);
            //  Loop as long as the random integer is larger than the input
            //  (the random integer is in the range of 0 - 1,073,741,824 (2^30))
  return r; //  Return the random integer that is within specified range
}           // End method

NOTE: May obviously take very long for small inputs.

Example output:

407594936
\$\endgroup\$
  • 2
    \$\begingroup\$ @Aaron I questioned this as well but see the second bullet point: "Any arguments when calling a built in or library random function must be constant. That is they must be completely independent of the input value." This is the reason max int is used. \$\endgroup\$ – Poke Feb 28 '17 at 14:11
  • 1
    \$\begingroup\$ 2^30 = 1073741824. You preferred to use -1>>>1 (= 2147483647). But this exists: 1<<30 which is exactly equals to 2^30; and is 1 byte shorter. \$\endgroup\$ – Olivier Grégoire Mar 1 '17 at 16:16
  • 1
    \$\begingroup\$ How about int c(int n){int r;for(;(r=new java.util.Random().nextInt(1<<30))>n;);return r;}? \$\endgroup\$ – Jakob Aug 9 '17 at 14:09
  • \$\begingroup\$ @Jakob Thanks. I even shortened it by 18 more bytes by using Java 8 instead of 7, and using Math.random() instead of java.util.Random().nextInt. \$\endgroup\$ – Kevin Cruijssen Aug 9 '17 at 14:54
2
\$\begingroup\$

Python 3, 51 bytes

Here is a python solution with an unorthodox random source.

print(list(set(map(str,range(int(input())+1))))[0])

Try it online!

So to break this down.

int(input())+1

Gets the input number, and adds 1 to it.

set(range(...))

Creates the set {0, 1, 2, 3, 4, ... n} for all possible results.

print(list(...)[0])

Takes the set, converts it to list, and grabs the first item.

This works because in Python 3, the order of set() is established by PYTHONHASHSEED (can't be obtained but is established on script execution).

Admittedly, I am guessing that this is a uniform distribution, as the hash() value is randomly assigned and I am looking at randomly picking the value with a specific hash(), rather then just returning the hash(input()) itself.

If anyone knows whether this is a uniform distribution, or how I could test that, please comment.

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

C#, 57 bytes

n=>{int x=n+1;while(x>n)x=new Random().Next();return x;};

Anonymous function which returns an integer between 0 and n inclusive.

The smaller the input number, the longer the time to return a random value.

Full program:

using System;

class RandomNumber
{
    static void Main()
    {
        Func<int, int> f =
        n=>{int x=n+1;while(x>n)x=new Random().Next();return x;};

        // example
        Console.WriteLine(f(100000));
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ "Any arguments when calling a built in or library random function must be constant. That is they must be completely independent of the input value." The argument to Next is not static. \$\endgroup\$ – Yytsi Feb 28 '17 at 12:21
1
\$\begingroup\$

Bash + coreutils, 20 bytes

Golfed

seq 0 $1|shuf|sed 1q

shuf - generate random permutations

Shuf will use the following code: to generate permutations:

permutation = randperm_new (randint_source, head_lines, n_lines);

which ends up in randint_genmax

/* Consume random data from *S to generate a random number in the range
0 .. GENMAX.  */

randint
randint_genmax (struct randint_source *s, randint genmax) 
{
      ...

      randread (source, buf, i);

      /* Increase RANDMAX by appending random bytes to RANDNUM and
         UCHAR_MAX to RANDMAX until RANDMAX is no less than
         GENMAX.  This may lose up to CHAR_BIT bits of information
         if shift_right (RANDINT_MAX) < GENMAX, but it is not
         worth the programming hassle of saving these bits since
         GENMAX is rarely that large in practice.  */
      ...
}

which, in turn, will read a few bytes of the random data from the low-level source of randomness:

/* Consume random data from *S to generate a random buffer BUF of size
   SIZE.  */

void
randread (struct randread_source *s, void *buf, size_t size)
{
  if (s->source)
    readsource (s, buf, size);
  else
    readisaac (&s->buf.isaac, buf, size);
}

i.e. at the low-level, there is no direct dependency between the shuf input value and the data read from the source of randomness (aside from computing the required byte buffer capacity).

\$\endgroup\$
  • 6
    \$\begingroup\$ Isn't this giving the input as an argument to your random number generator? \$\endgroup\$ – Martin Ender Feb 28 '17 at 11:46
  • \$\begingroup\$ Even if this is not valid, please submit another bash answer! \$\endgroup\$ – user9206 Feb 28 '17 at 11:48
  • \$\begingroup\$ @MartinEnder well, not directly, it just uses the input to define the upper limit for the generated integer range and jot will arrange for all the values in the range to appear in the output with an equal probability (that's probably borderline, but still). \$\endgroup\$ – zeppelin Feb 28 '17 at 11:52
  • 2
    \$\begingroup\$ If I dig deep enough into any random number generator I'm sure I'll find a call into a lower-level RNG that doesn't directly use the original argument. The point of the challenge is to obtain an arbitrary-size uniform distribution from a fixed -size distribution, which you're still not doing. \$\endgroup\$ – Martin Ender Mar 1 '17 at 21:56
1
\$\begingroup\$

SmileBASIC, 38 bytes

INPUT N@L
R=RND(1<<30)ON N<=R GOTO@L?R

Generates random numbers until it gets one that is smaller than the input.

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

Ruby, 23 15 23 32 29 bytes

->n{1while n<q=rand(2**30);q}

How it works:

  • 1while [...]; executes the statement at least once: 1 before while acts as a nop
  • Get a random number in the range 0..2^30-1 (lower than 2^30, as specified)
  • Repeat if the number is higher than the input parameter (Could take some time when n is small)
\$\endgroup\$
1
\$\begingroup\$

Ohm, 26 bytes

IΩ
D31º#╬D0[>?D-+∞;,

Explanation:

IΩ                 ■Main wire
IΩ                 ■Call wire below

D31º#╬D0[>?D-+∞;,  ■"Real main" wire
D                  ■Duplicate input
 31º#╬D            ■Push random_int in [0..2^31] twice
       0[          ■Push input again
         >?    ;   ■If(random_int > input){
           D-+     ■  remove the random_int
              ∞    ■  recursion
               ;   ■}
                ,  ■Print random_int
\$\endgroup\$
  • \$\begingroup\$ Is there an interpreter for this language? And what about Code-page? \$\endgroup\$ – ATaco Mar 1 '17 at 22:18
  • \$\begingroup\$ @ATaco: Interpreter, Code-page: CP-437 \$\endgroup\$ – Emigna Mar 2 '17 at 7:08
1
\$\begingroup\$

Go, 63 61 bytes

import."math/rand"
var n=0;func R(){q:=n;for;q<n+1;n=Int(){}}

Use it like this:

func main() {
    n = 5000
    R()
    print(n)
}

Test it live at the go playground

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

Golang, 84 78 71 bytes

import."math/rand"
func R(n int)int{q:=n+1;for;q>=n;q=Int(){};return q}

Simple rejection sampling.

Note: since the math/rand seed is a constant 1, the caller must seed unless a constant result is desired.

Test: https://play.golang.org/p/FBB4LKXo1r No longer practically testable on a 64-bit system, since it's returning 64-bit randomness and using rejection testing.

package main

import "fmt"
import "time"

/* solution here *//* end solution */

func main() {
    Seed(time.Now().Unix())
    fmt.Println(R(1073741823))
}
\$\endgroup\$
  • 1
    \$\begingroup\$ if you use import."math/rand" then Int31 is available in the global namespace and you can save 4 bytes, also intis guaranteed to be at least 32 bits, saving you another 6 bytes \$\endgroup\$ – Kristoffer Sall-Storgaard Mar 1 '17 at 13:18
  • \$\begingroup\$ Use := syntax for another 3 bytes \$\endgroup\$ – Kristoffer Sall-Storgaard Mar 1 '17 at 13:30
  • \$\begingroup\$ Using int instead of int32 doesn't save any bytes since we need to cast the result of Int31() - 3*int + () = 11 bytes versus 2*int32 = 10 bytes. \$\endgroup\$ – Riking Mar 1 '17 at 21:53
  • 1
    \$\begingroup\$ No need to cast, there is an Int() function in the rand package, also, you can remove the space after import \$\endgroup\$ – Kristoffer Sall-Storgaard Mar 2 '17 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy