최상의 답변
대부분의 난수 생성은 복잡한 알고리즘을 사용할 필요는 없지만 신중하게 선택한 숫자 만 사용합니다. 몇 가지 산술 트릭.
C :
static unsigned int next = 1;
int rand\_r(unsigned int *seed){
*seed = *seed * 1103515245 + 12345;
return (*seed \% ((unsigned int)RAND\_MAX + 1));
}
int rand(void){
return (rand\_r(&next));
}
void srand(unsigned int seed) {
next = seed;
}
자바 :
private final AtomicLong seed;
private static final long multiplier = 0x5DEECE66DL;
private static final long addend = 0xBL;
private static final long mask = (1L << 48) - 1;
public Random() {
this(seedUniquifier() ^ System.nanoTime());
}
private static long seedUniquifier() {
for (;;) {
long current = seedUniquifier.get();
long next = current * 181783497276652981L;
if (seedUniquifier.compareAndSet(current, next))
return next;
}
}
private static final AtomicLong seedUniquifier = new AtomicLong(8682522807148012L);
public Random(long seed) {
this.seed = new AtomicLong(initialScramble(seed));
}
private static long initialScramble(long seed) {
return (seed ^ multiplier) & mask;
}
더 느리지 만 고품질의 난수 생성기를 원하는 경우 가능한 생성기는 Mersenne Twister 일 수 있습니다. Mersenne 트위스터는 Python, Ruby, R, PHP, Matlab의 기본 난수 생성기이며 C ++에서도 사용할 수 있습니다. 아래 의사 코드에서 볼 수 있듯이 꽤 멋진 비트 연산자를 사용합니다.
int[0..623] MT
int index = 0
function initialize\_generator(int seed) {
i := 0
MT[0] := seed
for i from 1 to 623 {
MT[i] := last 32 bits of(1812433253 * (MT[i-1] xor (right shift by 30 bits(MT[i-1]))) + i)
}
}
function extract\_number() {
if index == 0 {
generate\_numbers()
}
int y := MT[index]
y := y xor (right shift by 11 bits(y))
y := y xor (left shift by 7 bits(y) and (2636928640))
y := y xor (left shift by 15 bits(y) and (4022730752))
y := y xor (right shift by 18 bits(y))
index := (index + 1) mod 624 return y
}
function generate\_numbers() {
for i from 0 to 623 {
int y := (MT[i] & 0x80000000) + (MT[(i+1) mod 624] & 0x7fffffff)
MT[i] := MT[(i + 397) mod 624] xor (right shift by 1 bit(y))
if (y mod 2) != 0 {
MT[i] := MT[i] xor (2567483615)
}
}
}
Answer
1949 년 연설에서 Von Neumann은 "무작위 숫자를 생성하는 산술적 방법을 고려하는 사람은 물론 죄의 상태에 있습니다."라고 말했습니다.
시작하기 위해 컴퓨터는 자체적으로 진정한 난수를 생성 할 수 없습니다. 컴퓨터가 생성하는 "무작위"숫자는 의사 난수 입니다. 생성 된 시퀀스는 프로그램에 주어진 초기 값에 의해 결정됩니다. 씨앗. 알고리즘은 프로그램의 초기 상태 또는 프로그램에 제공된 키를 사용하여 난수를 생성합니다. 진정한 난수는 무작위로 발생하는 자연 현상 (예 : 빠르게 진행되는 전자를 방출하는 방사성 요소)에서 숫자를 추출하여 생성 할 수 있습니다. 더 나은 아이디어를 얻으려면 다음 동영상을 참조하세요 (채널 구독에 저항하지 마세요. YouTube에서 가장 멋진 동영상이 있습니다).
이제 실제 알고리즘입니다. 가장 쉬운 알고리즘은 중간 제곱 법 . 이것은 13 세기 중반에 Edvin 형제 (아직 확인되지 않음)라는 사람이 제공했습니다. 환경에서 4 자리 시드를 가져와 제곱합니다. 그런 다음 첫 번째와 마지막 숫자를 제외한 정수를 임의의 숫자 시퀀스로 사용합니다. 이제 임의의 숫자에 대한 필요성이 첫 번째 단계에서 충족되면 좋습니다. 그렇지 않은 경우 알고리즘은 숫자의 중간 4 자리 숫자를 가져 와서 사용자가 새로운 임의의 숫자를 필요로하는 한 전체 프로세스를 다시 반복합니다.
1. 무작위 및 난수 소개 2. 중간 제곱 법 3. 난수 생성