27
\$\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\$
6
  • \$\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, 2017 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, 2017 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\$ Mar 1, 2017 at 22:11
  • \$\begingroup\$ This comes to mind: Random Number \$\endgroup\$
    – BgrWorker
    Mar 2, 2017 at 9:05
  • \$\begingroup\$ Why did you accept the x86 answer when there are three shorter ones? \$\endgroup\$
    – Dennis
    Mar 30, 2017 at 16:30

36 Answers 36

1
2
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\$
4
  • 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\$ Mar 1, 2017 at 13:18
  • \$\begingroup\$ Use := syntax for another 3 bytes \$\endgroup\$ Mar 1, 2017 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, 2017 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\$ Mar 2, 2017 at 8:59
1
\$\begingroup\$

Braingolf, 16 bytes

Uv2.# ,-^r[R>v]R

Try it online!

Takes longer than 60 seconds on TIO, but will terminate in a finite amount of time

Explanation

Uv2.# ,-^r[R>v]R  Implicit input from commandline args
U                 Pop top of stack and push range 0...n
 v                Switch to stack 2
  2.              Push two 2s
    #<space>      Push 32 (codepoint of space)
      ,           Swap top 2 items on stack
       -          Subtract top of stack from 2nd to top
        ^         Raise 2nd to top of stack to top of stack
                  This whole bit makes 2^30 on the 2nd stack
         r        Pops top of stack and pushes a random integer <= to popped item
                  This uses Python3's randrange, between 0 and the popped item
          [...]   While loop runs X times where X is the previously generated random number
           R>     Move top of stack1 to bottom of stack1
             v    Switch back to stack2 for loop counting
               R  Switch back to stack1 for implicit output
                  Implicit output of top of stack

So in short, this generates range [0...n], then generates a random number less than or equal (<=) to 2^30, it then rotates the range that number of times, and outputs the top of the stack at the end.

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

MMIX, 36 bytes (9 instrs)

Obvious rejection sampling method (Java version). Assumes TRAP 82,78,71 gets a randomly generated uint64_t from the OS.

(jxd)

00000000: 36010000 f7010000 00524e47 1e02ff00  6¢¡¡ẋ¢¡¡¡RNGœ£”¡
00000010: fe020006 26ffff02 32ffff01 45fffffb  “£¡©&””£2””¢E””»
00000020: f8030000                             ẏ¤¡¡

Disassembly:

rndr    NEGU $1,0,$0        // y = 2^64 - n
        PUT  rD,0
0H      TRAP 82,78,71       // loop: tmp = sysrand()
        DIVU $2,$255,$0
        GET  $2,rR          // z = tmp % n
        SUBU $255,$255,$2   // tmp -= z
        CMPU $255,$255,$1
        BP   $255,0B        // if(tmp > y) goto loop
        POP  3,0            // return n

Bonus: version from https://arxiv.org/pdf/1805.10941.pdf (except that we always calculate the remainder):

00000000: f7010001 e3010000 1e010100 fe010006  ẋ¢¡¢ẉ¢¡¡œ¢¢¡“¢¡©
00000010: 00524e47 1aff00ff 32ffff01 41fffffd  ¡RNGȷ”¡”2””¢A””’
00000020: fe000003 f8010000                    “¡¡¤ẏ¢¡¡
rndr    PUT  rD,1
        SET  $1,0
        DIVU $1,$1,$0
        GET  $1,rR          // r = 2^64 % n
0H      TRAP 82,78,71       // loop: tmp = sysrand()
        MULU $255,$0,$255   // rH:tmp = tmp * n
        CMPU $255,$255,$1
        BN   $255,0B        // if(tmp < r) goto loop
        GET  $0,rH
        POP  1,0            // return rH
\$\endgroup\$
1
\$\begingroup\$

CBL(not COBOL), 4 5 bytes

CBL is a 2d array-based language that I am working on. It has no interpreter (yet), but I plan to make one soon. The code that I have created may not be up to date with the current progress on the language, but I will try. I will also explain the code.

CBL has gone through some major changes recently. This is the updated version.

’0’ſr

A breakdown of this is as follows:

'0'ſr

'0'   «--numeric literal 0
   ſ  «--previous value (not the 0. it is the value from the previous link
    r «--random function takes the first two as input

This should solve the problem with rule no.2

As long as the interpreter uses uniform randomness (which it will), this should count. If you have any questions or suggestions, leave a comment.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Welcome to Code Golf! This looks like a really neat language. I have a bounty for +100 for interesting new languages, so when you finish the interpreter let me know! \$\endgroup\$ Jun 5, 2021 at 14:31
  • \$\begingroup\$ @RedwolfPrograms I may not get started on the interpreter until late June. \$\endgroup\$
    – smarnav
    Jun 6, 2021 at 23:52
  • 1
    \$\begingroup\$ From your explanation, it seems as if the r function is using two arguments, 0 and , (the input), to pick a random number in that range. If so, this unfortunately contravenes rule 2 of the challenge. \$\endgroup\$ Jun 12, 2021 at 11:22
0
\$\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\$
4
  • 6
    \$\begingroup\$ Isn't this giving the input as an argument to your random number generator? \$\endgroup\$ Feb 28, 2017 at 11:46
  • \$\begingroup\$ Even if this is not valid, please submit another bash answer! \$\endgroup\$
    – user9206
    Feb 28, 2017 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, 2017 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\$ Mar 1, 2017 at 21:56
0
\$\begingroup\$

Thunno 2 +, 5 bytes

ƓwwɼŒ

Try it online!

Port of Dennis's Jelly answer. Just like that answer, this won't finish for a very long time since \$(16!)!\$ is so big.

Explanation

ƓwwɼŒ  # Implicit input
       # Increment implicitly
Ɠ      # Push 16 to the stack
 ww    # Take the factorial twice
   ɼ   # Random item from [1..that]
    Π # Modulo by (input + 1)
       # Implicit output
\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.