Tâche

Étant donné un entier positif ninférieur à celui 2^30spécifié en entrée de la manière que vous choisissez, votre code doit générer un entier aléatoire entre 0et ninclus. Le nombre que vous générez doit être choisi de manière uniforme et aléatoire . C'est-à-dire que chaque valeur de 0à ndoit se produire avec une probabilité égale (voir Règles et mises en garde).

Règles et mises en garde

Votre code peut supposer que tout générateur de nombres aléatoires intégré à votre langue ou bibliothèque standard qui prétend être uniformément aléatoire est en fait uniforme. Vous n'avez donc pas à vous soucier de la qualité de la source aléatoire que vous utilisez. cependant,

• Vous devez établir que si la source aléatoire que vous utilisez est uniforme, votre code génère correctement un entier aléatoire uniforme de 0à n.
• Tout argument lors de l'appel d'une fonction aléatoire intégrée ou de bibliothèque doit être constant. Autrement dit, ils doivent être complètement indépendants de la valeur d'entrée.
• Votre code peut se terminer avec la probabilité 1 plutôt que d'être garanti de se terminer.

Remarques

• randInt(0,n) n'est pas valide car il prend l'entrée comme argument d'une fonction intégrée ou de bibliothèque.
• rand()%nne pas donner un nombre aléatoire uniforme en général. À titre d'exemple donné par betseg, si intmax == 15et n = 10, alors vous aurez beaucoup plus de chances d'obtenir 0-5que 6-10.
• floor(randomfloat()*(n+1)) ne donnera pas non plus un nombre aléatoire uniforme en général en raison du nombre fini de différentes valeurs possibles en virgule flottante entre 0 et 1.

machines x86 avec rdrandinstruction, 10 octets

BITS 64

_try_again:

 rdrand eax
jnc _try_again

 cmp eax, edi
ja _try_again

 ret

langage machine

0FC7F0 73FB 39F8 77F7 C3

L'entrée est dans le registre rdiet la sortie dans rax.
Cela respecte l' ABI SYS V AMD64 afin que le code implémente efficacement une fonction C

unsigned int foo(unsigned int max); 

avec des entiers 32 bits.

L'instruction rdrandest décrite par Intel

RDRANDrenvoie des nombres aléatoires qui sont fournis par un générateur de bits aléatoires déterministe sécurisé cryptographiquement DRBG. Le DRBG est conçu pour répondre à la norme NIST SP 800-90A .

En traitant avec CSRNG, il est implicite que la distribution est uniforme, de toute façon, citant le NIST SP 800-90A:

Un nombre aléatoire est une instance d'une variable aléatoire non biaisée, c'est-à-dire la sortie produite par un processus aléatoire uniformément distribué.

La procédure génère un nombre aléatoire et s'il n'est pas strictement supérieur à l'entrée, il est renvoyé.
Sinon, le processus est réitéré.

Puisque eaxest de 32 bits, rdrandrenvoie un nombre compris entre 0 et 2 ³² -1, donc pour chaque n dans [0, 2 ³² -1] le nombre d'itérations attendues est 2 ³² / (n + 1) qui est défini pour tout n dans [0, 2 ³⁰ ).

Gelée , 7 6 octets

⁴!!X%‘

Merci à @JonathanAllan d'avoir joué au golf sur 1 octet!

Ne peut pas être exécuté sur TIO car (16!)! est un nombre énorme .

Comment ça marche

⁴!!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.

Mathematica, 29 octets

Basé sur la réponse de Dennis Jelly .

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

Je ne recommanderais pas réellement de faire ça. 2e9!est un assez grand nombre ...

Il s'avère être le plus court pour générer un nombre énorme qui est divisible par toutes les entrées possibles et le mapper le résultat à la plage requise avec un simple modulo.

Échantillonnage de rejet, 34 octets

Mon ancienne approche qui a conduit à un code un peu plus intéressant:

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

Échantillonnage de rejet de base. Nous initialisons la sortie à 13! (qui est plus grand que l'entrée maximale 2 ³⁰ ), puis remplacez-le à plusieurs reprises par un entier aléatoire compris entre 0 et 13! tant que la valeur est supérieure à l'entrée.

Brachylog , 9 octets

≥.∧13ḟṙ|↰

Essayez-le en ligne!

Cela utilise 13!comme dans la réponse de Martin Ender ( 13ḟest un octet de moins que 2^₃₀).

ṙest implémenté en utilisant random_between/3, qui, lors du creusement de sa source, utilise random_float/0ce qui est lié à celui random/1qui utilise l'algorithme Mersenne Twister qui est uniforme pour nos besoins.

Explication

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

Prolog (SWI) , 38 octets

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

Fonctionne par échantillonnage de rejet.

Générez un nombre aléatoire compris entre 0 et 2 ^ 31-1 = 2147483647 jusqu'à ce qu'un autre inférieur ou égal à l'entrée soit trouvé.

Je sens que je devrais pouvoir utiliser une coupe au lieu de l’autre, mais je ne vois pas comment.

Labyrinthe , 63 octets

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

(Merci à @MartinEnder pour son aide avec du golf lourd ici.)

Labyrinth est un langage 2D, et sa seule source d'aléatoire est dans une situation comme la suivante:

   x
  "<)
 " "
 " "

Supposons que le pointeur d'instruction se trouve sur xet se déplace vers le bas. Il atterrit ensuite sur le <, qui si le haut de la pile est 0 (ce qui est toujours le cas dans le programme réel ci-dessus) décale la ligne actuelle de 1:

   "
 "<)
 " "
 " "

Le pointeur d'instruction est maintenant sur le < déplace bas. À une jonction, Labyrinth tourne sur la base du haut de la pile - négatif est tourner à gauche, positif est tourner à droite et zéro est aller de l'avant. Si le haut de la pile est toujours nul à ce stade, nous ne pouvons pas avancer ou reculer car il n'y a pas de chemin, donc Labyrinth choisira au hasard entre tourner à gauche ou tourner à droite avec une probabilité égale.

Essentiellement, le programme ci-dessus utilise la fonction aléatoire pour générer des nombres de 100 bits (100 spécifiés par #00 ici) et continuer la boucle jusqu'à ce qu'il génère un nombre <= n.

Pour les tests, il sera probablement utile d'utiliser à la #0"place pour les nombres à 10 bits, le "chemin étant sans opération.Essayez-le en ligne!

Explication grossière:

 ?            <--- ? 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.

Python, 61 octets

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

Modifier: mis à jour pour éviter le formulaire interdit

Edit2: Enregistré 2 octets, merci @ JonathanAllan

Edit3: payé 2 octets pour une solution entièrement fonctionnelle - merci encore @JonathanAllan

Edit4: supprimé f=, économisant 2 octets

Edit5: enregistré 1 octet de plus grâce à @ JonathanAllan

Edit6: enregistré 2 octets de plus grâce à @ JonathanAllan

À ce moment-là, git blame me désignerait les mauvaises choses, et JonathanAllan pour les choses qui aident.

Edit7: Quand il pleut, il déverse - encore 2 octets

Edit8: Et encore 2 octets

Python 2 , 61 octets

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

Pseudo-aléatoirement choisit des entiers entre 0 et k pour toutes les valeurs de k entre 0 et 2 ³¹ - 2 , puis prend l'entier correspondant à k = n .

Lot, 64 octets

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

%random%ne donne que 15 bits de hasard, donc je dois combiner deux nombres aléatoires. Boucles jusqu'à ce que la valeur aléatoire se situe dans la plage souhaitée, donc lente pour faible n; 98 octets pour une version plus rapide:

@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%

MATL , 12 octets

Merci à @AdmBorkBork et à @Suever de m'avoir expliqué comment désactiver le cache TIO.

`30WYrqG>}2M

Essayez-le en ligne! .

Cela utilise une méthode de rejet : générer un entier aléatoire de 0à 2^30-1et répéter tant qu'il dépasse l'entrée n. Il est garanti que cela se terminera avec probabilité 1, mais le nombre moyen d'itérations est 2^30/n, et cela prend donc très longtemps pour nbeaucoup plus petit que 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)

JavaScript (ES6), 55 54 octets

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

Génère des entiers dans la plage [0 ... 2 ^k - 1] , où k est le plus petit entier tel que 2 ^k est supérieur à n . Se répète jusqu'à ce que le résultat tombe [0 ... n] .

Pourquoi?

Ceci est basé sur les hypothèses suivantes:

• En interne, les valeurs entières pseudo-aléatoires générées par le moteur JS à alimenter Math.random()sont uniformes sur n'importe quel intervalle [0 ... 2 ^k -1] (avec k <32 ).

• Une fois multipliées par une puissance exacte de 2, les valeurs flottantes IEEE 754 renvoyées par Math.random()sont toujours uniformes sur de tels intervalles.

Si quelqu'un peut confirmer ou réfuter ces hypothèses, faites-le moi savoir dans les commentaires.

Démo

Génère 1 million de valeurs dans [0 ... 2] et affiche les statistiques de résultat.

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` `)

Bash (+ coreutils), 44 octets

/ dev / urandom based solution

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

Lit les entiers 32 bits non signés /dev/urandomet les filtre awkjusqu'à ce qu'il en trouve un dans une plage donnée, puis sed qabandonne le canal.

Haskell, 70 octets

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

Pas un algorithme très efficace mais ça marche. Il génère une liste infinie d'entiers (ou flotte si nécessaire, en raison du système de type de Haskell) délimité par [0,2 ^ 30] et prend le premier inférieur ou égal à n. Pour les petits n, cela peut prendre beaucoup de temps. Les nombres aléatoires doivent être uniformément répartis, comme spécifié dans la documentation de randomR afin que tous les nombres de l'intervalle [0,2 ^ 30] aient la même probabilité (1 / (2 ^ 30 + 1)) donc tous les nombres de [ 0, n] ont la même probabilité.

Version alternative:

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

Cette version est terrible mais elle enregistre un octet entier. randomsutilise une plage arbitraire définie par le type pour générer une liste infinie de nombres. Cela peut inclure des négatifs, nous devons donc les mapper avec abspour les forcer positifs (ou zéro). C'est extrêmement lent pour toutes les valeurs de n qui ne sont pas absurdement grandes. EDIT : J'ai réalisé plus tard que cette version n'est pas uniformément distribuée car la probabilité d'obtenir 0 est pire que les autres nombres en raison de l'utilisation deabs . Pour produire un certain nombre, mle générateur pourrait produire mou, -mmais dans le cas de 0, seul 0 fonctionnera, donc sa probabilité est la moitié des autres nombres.

Gelée , 9 octets

⁴!Ẋ’>Ðḟ⁸Ṫ

Essayez-le en ligne! - le code ci-dessus ne fonctionnera pas sur TIO depuis une plage de taille 16! doivent être construits en premier (sans parler du fait qu'ils doivent ensuite être mélangés puis filtrés!), c'est donc la même chose à une échelle beaucoup plus petite, répétée 30 fois pour une entrée de 3 avec une limite de 10.

Comment?

⁴!Ẋ’>Ðḟ⁸Ṫ - 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.

Remarque: il serait plus d'un millier de fois plus efficace pour le même nombre d'octets de ȷ⁵faire ce à quoi on s'attendrait naïvement et de retourner de dix à dix, mais ce n'est pas le cas car le ⁵n'est pas évalué comme un dix littéral à utiliser par le nombre littéral, ȷ...mais plutôt deux littéraux distincts sont analysés, ȷavec son exposant par défaut de trois donnant mille et ⁵dix.

JDK 9 sur jshell, 75 59 octets

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 octets: Merci Jakob!
• Suppose que nous considérons jshell comme un environnement d'exécution valide.
• jshell lui-même, en tant qu'environnement d'exécution, ne nécessite pas d'importations explicites pour les bibliothèques principales et ne nécessite pas de points-virgules.
• Renvoie un OptionalInt. Les règles ne spécifient pas que le type de retour doit être une primitive et je considère an OptionalIntcomme une représentation valide du résultat.

PHP, 30 octets

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

Courez avec echo <N> | php -Rn '<code>'.

choisit un nombre aléatoire entre 0 et getrandmax()(2 ** 31-1 sur ma machine 64 bits);
se répète alors que c'est plus grand que l'entrée.

Cela peut prendre un certain temps ... mon AMD C-50 (1 GHz) a nécessité entre 0,3 et 130 secondes N=15.

Un moyen plus rapide pour la moyenne N( 46 octets ):

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

ou

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

prend N+1des entiers aléatoires, les résume et prend le modulo avec N+1.
Le C-50 a besoin d'env. 8 secondes pour 1 million d'exécutions.

Une solution invalide pour 19 octets :

echo rand(0,$argn);

PowerShell , 35 octets

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

Essayez-le en ligne!

Une autre méthode d'échantillonnage de rejet. Il s'agit d'une forboucle infinie , définissant la valeur de $apour être un Randomentier entre 0et 1gb( = 1073741824 = 2^30), et continue de boucler tant que cet entier est -gramené à tl'entrée $args. Une fois la boucle terminée, nous mettons simplement $ale pipeline et la sortie est implicite.

Remarque: cela prendra beaucoup de temps si l'entrée est un petit nombre.

Python 2 , 72 69 octets

-3 octets grâce à xnor (remplacer le idintégré en tant que variable)

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

Essayez-le en ligne!

randrange(2**30)produit un nombre pseudo-uniformément distribué (Mersenne Twister 2 ^19937-1 ) à partir de la plage [0,2 ³⁰ ) . Puisqu'il nest garanti d'être inférieur à 2 ^30, il peut simplement être appelé à plusieurs reprises jusqu'à ce qu'il ne soit pas supérieur à l'entrée. Cela prendra beaucoup de temps pour des valeurs très basses n, mais fonctionne généralement dans la minute même pour des entrées aussi faibles que 50.

Perl 6 , 29 octets

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

Inspiré de la solution Mathematica de Martin Ender .

Génère une séquence infinie paresseuse d'entiers aléatoires entre 0 et 2 ^ 30-1, et prend le premier compris entre 0 et l'entrée.

Essayez-le en ligne!

05AB1E , 11 octets

žIÝ.rDI›_Ϥ

Essayez-le en ligne!

Explication

ž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

Comme la liste [0 ... 2147483648]est trop grande pour TIO, le lien utilise à la 1.000.000place.

Solution alternative (en moyenne) beaucoup plus rapide de 11 octets

[žIÝ.RD¹›_#

Essayez-le en ligne

Explication

[             # 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)

Python 2, 89 octets

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

Explication

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.

C’est très inefficient, as it creates 2^31 integers, shuffles and filters them.

Je ne vois aucun intérêt à partager un lien TIO, où il crée de si grandes listes, alors voici un lien TIO pour n = 100.

Essayez-le en ligne!

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

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.

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));
    }
}

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).

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.

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)

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

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

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))
}