Komputery nie znikąd tworzą losowe liczby bez podstawy, ponieważ najprawdopodobniej czas jest uniwersalną podstawą losowości.

Chcę, abyś utworzył kod, który tworzy losowe liczby według następujących reguł:

• Czas nie może być podstawą w żadnym momencie programu.
• Wstępnie zdefiniowane funkcje losowe / pseudolosowe są niedozwolone.
• Wygenerowane liczby mogą znajdować się w dowolnym zakresie. Co najmniej dwie różne liczby całkowite: D
• Numery są powtarzane.

JavaScript

To było zabawne!

arr = []
index = 0

function init(seed) {
    index = 0
    arr[0] = seed
    for (var i = 1; i < 624; i ++) {
        arr[i] = (1812433253 * (arr[i-1] ^ (arr[i-1] >>> 30)) + i) | 0
    }
 }

function getNumber() {
    if (index == 0) generateNumbers()

    var y = arr[index]
    y ^= (y >>> 11)
    y ^= ((y << 7) & 2636928640)
    y ^= ((y << 15) & 4022730752)
    y ^= (y >>> 18)

    index = (index + 1) % 624
    return y
}

function generateNumbers() {
    for (var i = 0; i < 624; i ++) {
        var y = (arr[i] & 0x80000000) + (arr[(i+1) % 624] & 0x7fffffff)
        arr[i] = arr[(i + 397) % 624] ^ (y >>> 1)
        if (y % 2 != 0) arr[i] ^= 2567483615
    }
}

// let's get our seed now from the SE API
var x = new XMLHttpRequest()
x.open('GET', 'http://api.stackexchange.com/2.2/answers?pagesize=10&order=desc&sort=activity&site=stackoverflow&filter=!Sri2UzKb5mTfr.XgjE', false)
x.send(null)
// we've got the answer data, now just add up all the numbers.
// only 4 digits at a time to prevent too big of a number.
var seed = 0
var numbers = x.responseText.match(/\d{0,4}/g)
for (var i = 0; i < numbers.length; i++) seed += +numbers[i]

init(seed)
for (var i = 0; i < 10; i++) console.log(getNumber())

Napisałem Twister Mersenne w JS. Potem zdałem sobie sprawę, że muszę gdzieś zdobyć ziarno.

Zdecydowałem, że dostanę go z interfejsu API wymiany stosów! (Mógłbym użyć localStoragei zwiększyć licznik, ale to nie jest zabawne.) Więc złapałem 10 ostatnio aktywnych odpowiedzi, a następnie po prostu wziąłem co 4 lub mniej kolejnych cyfr w odpowiedzi i dodałem je.

Te nasiona są zawsze różne, ponieważ Przepełnienie stosu stale się aktualizuje (a mój limit wciąż maleje!) Liczby obejmują identyfikatory odpowiedzi, identyfikatory pytań, wyniki, liczby w górę / w dół głosów, dane właściciela / identyfikatory oraz dane opakowania (limit i inne) ). Na jednym biegu dostałem 256845wtedy 270495, a potem 256048itd.

To rejestruje 10 losowych 32-bitowych liczb uzupełniających dwa do konsoli. Przykładowe dane wyjściowe:

247701962
-601555287
1363363842
-1184801866
1761791937
-163544156
2021774189
2140443959
1764173996
-1176627822

Jawa

import java.util.Random;
import java.util.concurrent.atomic.AtomicLong;

/**
 *
 * @author Quincunx
 */
public class NoTimeRandom extends Random {

    private AtomicLong seed;

    public NoTimeRandom() {
        byte[] ba = (new String[0].toString() + new String[0].toString()
                + new String[0].toString() + new String[0].toString()
                + new String[0].toString() + new String[0].toString()).getBytes();
        int seed1 = 1;
        for (byte b : ba) {
            seed1 += b;
        }

        ba = (new String[0].toString() + new String[0].toString()
                + new String[0].toString() + new String[0].toString()
                + new String[0].toString() + new String[0].toString()).getBytes();
        long seed2 = 1;
        for (byte b : ba) {
            seed2 += b;
        }

        seed = new AtomicLong(seed1 ^ seed2);
    }

    @Override
    protected int next(int bits) {
        long oldseed, newseed;
        AtomicLong seed = this.seed;
        do {
            oldseed = seed.get();
            newseed = (oldseed * 25214903917L + 11) & 281474976710655L;
        } while (!seed.compareAndSet(oldseed, newseed));

        return (int) (newseed >>> (48 - bits));
    }

    public static void main(String[] args) {
        Random r = new NoTimeRandom();

        for (int i = 0; i < 5; i++) {
            System.out.println(r.nextInt());
        }
    }

}

Magia jest w public NoTimeRandom(). Tablice rzutowane na ciągi mogą mylić nowych programistów, ponieważ liczby są losowe. Próbkę (za char[]: [C@4a8e91eb). nextMetoda jest kopiowany z java.util.Random.

Przykładowe dane wyjściowe:

134277366
467041052
-555611140
-1741034686
1420784423

Przetestujmy skuteczność tego rng:

W mojej odpowiedzi na aproksymację krzywej dzwonienia generowane przeze mnie dane zależą od dobrego rng. Uruchommy to z tym jako rng. Wynik:

Dokładnie jak myślałem. To jest dość kiepski rng.

do

Skompiluj z flagą -pthread (lub cokolwiek, czego używa Twój kompilator).

#include <stdio.h>
#include <pthread.h>

#define m (unsigned long)2147483647
#define q (unsigned long)127773
#define a (unsigned int)16807
#define r (unsigned int)2836 

static unsigned long seed;
pthread_t t[20];
int lo, hi, done;

void *pseudorandom(void *id)
{
    while(done)
    {
        int test;
        hi = seed/q;
        lo = seed%q;
        test = a * lo - r * hi;
        if (test > 0) seed = test;
        else seed = test + m;
    }
}

main()
{
     int i;
     seed = 54321;
     done = 1;

     for(i = 0; i < 20; i++) 
     {
          pthread_create(&(t[i]), NULL, &pseudorandom, NULL);
     }

     for (i = 0; i < 10; i++) 
     {
          printf("%lu\n", seed);
     }

     done = 0;
}

Nie jestem pewien, czy to się kwalifikuje, czy też nie w oparciu o standard „czas nie jest dozwolony”, ponieważ w zasadzie używa on harmonogramu jako źródła entropii, celowo ignorując bezpieczeństwo wątków. Działa przy użyciu dość podstawowej funkcji losowo-losowej ( generator liczb losowych Lehmera ) z początkowo zakodowanym początkowo ziarnem. Następnie rozpoczyna 20 wątków, w których wszystkie uruchamiają obliczenia Lehmera ze wspólnym zestawem zmiennych.

Wygląda na to, że działa całkiem dobrze, oto kilka kolejnych przebiegów:

comintern ~ $ ./a.out
821551271
198866223
670412515
4292256
561301260
1256197345
959764614
874838892
1375885882
1788849800
comintern ~ $ ./a.out
2067099631
953349057
1736873858
267798474
941322622
564797842
157852857
1263164394
399068484
2077423336

EDYCJA: Zastanów się trochę i zdaj sobie sprawę, że to wcale nie jest czas. Nawet przy całkowicie deterministycznym harmonogramie entropia nie pochodzi z przedziałów czasowych - pochodzi z ładowania wszystkich uruchomionych procesów w systemie.

EDYCJA 2 Po zainspirowaniu się @Quincunx po opublikowaniu krzywej dzwonowej, zrzuciłem 12 MB losowości do pliku i przesłałem ją do CAcert . Nie przeszedł wszystkich trudnych testów, ale osiągnął szacunek 7.999573 z 8 w teście ENT (tylko potencjalnie deterministyczny). Co ciekawe, podwojenie liczby wątków pogorszyło sytuację.

do

Generuje losową liczbę z zakresu 0-255, pobierając ziarno z https://stackoverflow.com/questions używając wget.

#include <stdio.h>
main()
{
    FILE *file;
    unsigned char c,x;
    system("wget -O - https://stackoverflow.com/questions > quest.html");
    file = fopen ("quest.html", "r");
    while(c=fgetc(file) != EOF) x+=c;
    fclose(file);
    printf("%d",x);
}

Przykładowy przebieg:

C:\Users\izabera>random
--2014-03-02 16:15:28--  https://stackoverflow.com/questions
Resolving stackoverflow.com... 198.252.206.140
Connecting to stackoverflow.com|198.252.206.140|:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 85775 (84K) [text/html]
Saving to: `STDOUT'

100%[======================================>] 85,775      40.3K/s   in 2.1s

2014-03-02 16:15:31 (40.3 KB/s) - `-' saved [85775/85775]

15 /* <=================== THIS IS THE RANDOM NUMBER */
C:\Users\izabera>random
--2014-03-02 16:15:36--  https://stackoverflow.com/questions
Resolving stackoverflow.com... 198.252.206.140
Connecting to stackoverflow.com|198.252.206.140|:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 85836 (84K) [text/html]
Saving to: `STDOUT'

100%[======================================>] 85,836      50.0K/s   in 1.7s

2014-03-02 16:15:38 (50.0 KB/s) - `-' saved [85836/85836]

76
C:\Users\izabera>random
--2014-03-02 16:15:56--  https://stackoverflow.com/questions
Resolving stackoverflow.com... 198.252.206.140
Connecting to stackoverflow.com|198.252.206.140|:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 85244 (83K) [text/html]
Saving to: `STDOUT'

100%[======================================>] 85,244      36.0K/s   in 2.3s

2014-03-02 16:15:59 (36.0 KB/s) - `-' saved [85244/85244]

144

C ++

#include<iostream>
int main()
{
    int *ptr=new int,i=0;
    for(;i<5;i++)
    {
        std::cout<<*(ptr+i)<<'\n';
    }
    return 0;
}  

wynik

dowolne 5 liczb losowych

trzy próbki

perl

Co to za śmiecie z pozyskiwania nasion przez Internet? Brzmi dla mnie jak oszustwo ;-) Wolę zamiast tego dać swoje ziarno kryptograficznej funkcji skrótu i ​​dać wynik w zakresie od 0 do 2 ^ 160-1, tak jak:

use Digest::SHA1 qw(sha1);
use bigint;
sub r {
  $_ = \3;
  /^.*x([0-9a-f]+).$/;
  hex((unpack "H*", sha1 "some_salt".$1.$$)[0])
}
print join " ", r'

Za każdym razem, gdy masz entropię o niepewnej jakości, sposobem na jej regularniejsze rozpowszechnianie (ale nie zwiększanie jej jakości!) Jest podłączenie jej do SHA1 lub MD5 lub mniej więcej, tak jak to zrobiłem tutaj. W przypadku nasion przed hash użyłem pid i adresu losowego odniesienia. Możesz oczywiście dodać inne dane wejściowe dla większej entropii, np. Na x86 możesz użyć TSC - (ale wstawianie kodu asemblera w perlu to trochę niedźwiedź, więc go pominąłem).

Jeśli chcesz mieć inne wyjście niż facet na następnym komputerze, po prostu dostosuj „some_salt”, aby był ciągiem swoich upodobań. Lub całkowicie pomiń, jeśli jesteś minimalistą =)

Jawa

Moje rozwiązanie narusza hashCode()metodę Objectklasy.

class G22640 {
    static class Rand {
        public int nextInt() {
            return new Object().hashCode();
        }
    }

    public static void main(String args[]) {
        Rand r = new Rand();
        for (int i = 0; i < 10; i++) {
            System.out.println(r.nextInt());
        }
    }
}

Przykładowe dane wyjściowe:

31859448
22101035
11593610
4580332
25736626
32157998
3804398
32440180
19905449
2772678

Zmotywowany inną odpowiedzią pokazującą losowość rozwiązania, zmieniłem swoje rozwiązanie, aby zwrócić środkowe 16 bitów intzwróconego przez Object.hashCode().

import java.io.*;

class G22640 {
    static class Rand {
        public short nextShort() {
            return (short) ((new Object().hashCode() >> 8) & 0xFFFF);
        }
    }

    public static void main(String args[]) throws IOException {
        Rand r = new Rand();

        for (int i = 0; i < 10; i++) {
            System.out.println(r.nextShort());
        }

        // generateToFile("random_22640.txt");
    }

    private static void generateToFile(String fileName) throws IOException {
        Rand r = new Rand();
        BufferedOutputStream o = new BufferedOutputStream(new FileOutputStream(fileName));

        for (int i = 0; i < 10000000; i++) {
            int a = r.nextShort();
            for (int j = 0; j < 2; j++) {
                o.write(a & 0xFF);
                a >>= 8;
            }
        }

        o.flush();
        o.close();
    }
}

Wygenerowałem plik 19 MB (składający się z 10 ⁷ short ) i przesłałem go do CACert . Oto zrzut ekranu wyniku (został zredagowany, aby wyglądać ładnie, ale liczby pozostały bez zmian ):

Byłem zaskoczony wynikiem, ponieważ w teście Entropii taktuje 7,999991 i zdaje (?) Wszystkie 7 testów Dieharda.

JavaScript
Generowanie losowe za pomocą ruchu myszy użytkownika

var ranArr=[];
var random=0;
var first=second=0;
function generateR(event) {
ranArr.push(parseFloat(event.clientX+document.body.scrollLeft))
ranArr.push(parseFloat(event.clientY+document.body.scrollTop));
var len=ranArr.length;

for(var i=0;i<len;i++) {
    if(i<len/2) {

    first+=ranArr[i];
    } else {
    second += ranArr[i];
    }
}
third = second/first;
third = third+"";
console.log(third.substr(5));
}
document.onmousemove=function(event){generateR(event)};

Ostatnie pięć skopiowanych danych:
9637090187003
7828470680762
6045869361238
4220720695015
2422653391073

Bash, zakres: ints od 0 do 1

echo -n & echo "$! % 2" | bc

Rubin

Niestety tylko Mac. Używamy soxdo wyciągania bajtów z mikrofonu (jako ciąg, ahem ...), odwracania go, aby uzyskać nagłówek stanu na końcu (* kaszel *), pocięcia go, odcięcia nagłówka, weź MD5 kawałków , porzuć znaki nienumeryczne z mieszania, dodaj pozostałe duże liczby całkowite razem, przyklej 0.z przodu, zamień na zmiennoprzecinkowe, gotowe.

Generuje liczby zmiennoprzecinkowe w przedziale 0..1.

require 'open3'
require 'digest'

class InsecureRandom
  def self.random_number
    n = self.get_bytes
    .map! { |r| Digest::MD5.hexdigest(r) }
    .map! { |r| r.gsub(/[a-z]/, '') }
    .map!(&:to_i)
    .reduce(0,:+)

    "0.#{n}".to_f
  end

  private
  def self.get_bytes
    Open3.popen3('sox -d -q -e unsigned-integer -p') do |_, stdout, _|
      stdout.read(20000).reverse.split('\\').to_a.take(20)
    end
  end
end

randomish = Array.new(20) { InsecureRandom.random_number }
puts randomish
# >> 0.2333530765409607
# >> 0.17754047429753905
# >> 0.936039801228352
# >> 0.2781141892158962
# >> 0.6243140263525706
# >> 0.1583419168189452
# >> 0.2173713056635174
# >> 0.930577106355
# >> 0.11215268787922089
# >> 0.13292311877287152
# >> 0.14791818448435443
# >> 0.4864648362730452
# >> 0.5133193113765809
# >> 0.3076637743531015
# >> 0.16060112015793476
# >> 0.7294970251624926
# >> 0.18945368886946876
# >> 0.9970215825154781
# >> 0.13775531752383308
# >> 0.5794383903900283

do

Generowanie losowe przy użyciu identyfikatora procesu.

#include <unistd.h>
#include <stdio.h>

int     main(void)
{
    int out;
    out *= out *= out = getpid();
    printf("%d\n", out % 1024);
    return (0);
}

Przykładowe dane wyjściowe:

-767
0
769
-1008
337
-768
369
-752
-415
0
-863
784
-463
256
657

OBRACAĆ

Jeśli tak było golf-golfwygrałbym!

byte a
?a@

pyton

Zwięzłość Pythona nigdy nie przestaje zadziwiać. Ponieważ użycie losowego obrazu imgur najwyraźniej nie jest poprawne, skorzystałem z doskonałego źródła losowości: czata stackoverflow!

   import urllib.request

def getrand():
    req = urllib.request.Request("http://chat.stackoverflow.com/")
    response = urllib.request.urlopen(req)
    the_page = str(response.read())

    x = 1
    for char in the_page:
        x = (3*x + ord(char) + 1)%2**32

    print(x)

5 prób:

3258789746
1899058937
3811869909
274739242
1292809118

Niezupełnie losowy, ale z drugiej strony żaden z nich nie jest.

perl

Widziałem wiele odpowiedzi, które wysyłały żądania HTTP, co wydaje mi się marnotrawstwem, ponieważ pod okładkami są przekazywane losowe liczby na drucie. Postanowiłem więc napisać kod, aby przesunąć jeden na niższym poziomie:

use IO::Socket::INET;
print ((sockaddr_in(getsockname(IO::Socket::INET->new(
    PeerAddr => "google.com", PeerPort => 80, Proto => "tcp"
))))[0]);

Teoretycznie podaje losowe porty z zakresu 0..65535. W praktyce istnieje wiele portów, których nigdy nie zobaczysz, więc dystrybucja nie jest idealna. Ale to AFAICT to minimalna ilość pracy, którą możesz zrobić, aby uzyskać entropię ze zdalnego hosta, który ma otwarty port.

PS - Obsługa błędów pozostawia czytelnikowi ćwiczenie ;-)

do

// alternating two pure-RNG inspired by http://xkcd.com/221/
int getRandomNumber()
{
   static int dice_roll = 0;
   dice_roll++;
   if ((dice_roll % 2) == 1)
   {
      return 4;
   } 
   else
   {
      return 5;
   } 
}

int main(int argc, char **argv)
{
    printf("%d\n%d\n", getRandomNumber(), getRandomNumber())
    return 0;
}