JavaScript에서 난수 생성의 기초

(명백하게) 난수를 생성할 수 있다는 것은 수학, 통계, 과학, 기술 및 게임의 많은 영역에서 필수적인 요구 사항입니다.

Katie Mikova Last Updated Feb 26, 2025 12min read

(명백하게) 난수를 생성할 수 있다는 것은 수학, 통계, 과학, 기술 및 게임의 많은 영역에서 필수적인 요구 사항입니다.

예를 들어, 무작위 통제 시험에서 참가자를 그룹에 할당하거나, 컴퓨터 게임의 결과를 결정하거나, 그렇지 않으면 다루기 어려운 문제에 대한 대략적인 해결책을 찾는 데 사용할 수 있습니다. 나는 완벽하게 다루기 쉬운 통계 문제에 대한 해결책을 확인하기 위해 난수를 자주 사용합니다. 여기서는 다루지 않을 암호화 난수 생성기는 보안에 사용할 수 있습니다.

Types of Random Number Generator

적어도 이 기사의 목적을 위해 난수 수집에는 세 가지 범주가 있다고 생각할 수 있습니다.

“True” random numbers;
Pseudorandom numbers;
Quasirandom sequences.

참(또는 하드웨어) 난수 생성기(TRNG)는 본질적으로 무작위로 여겨지는 실제 물리적 프로세스를 사용하여 숫자 스트림을 생성합니다. 예를 들어, 방사성 선원의 붕괴 현상은 무작위이며 서로 상관 관계가 없으며 대기 소음도 사용할 수 있습니다.

TRNG는 여러 가지 목적에 실용적이거나 편리하지 않은(또는 필요한) 경우가 많습니다. 훨씬 더 일반적인 대안은 컴퓨터 알고리즘을 사용하여 일정 간격에 걸쳐 무작위로 분포된 것처럼 보이는 숫자 스트림을 만드는 것입니다. 이러한 알고리즘은 실제로 예측할 수 없는 것이 아니므로 PRNG(의사 난수 생성기)라고 합니다.

마지막으로, 준난수 시퀀스는 어떤 식으로든 표본 공간을 나타내기 위한 숫자의 유한한 모음입니다. 예를 들어, 염기서열의 평균은 모집단의 알려진 평균과 동일할 수 있습니다(또는 매우 유사할 수 있습니다). 준난수 시퀀스는 흥미롭고 유용할 수 있지만 이 기사의 초점이 아니므로 더 이상 논의하지 않을 것입니다.

The Standard Uniform Distribution

일반적으로 의사 난수 생성기에서 많은 수의 값 출력은 0에서 1 범위를 포함하는 표준 균일 분포 (SUD)를 근사화하기 위한 것입니다. 그러나 끝점 중 하나 또는 둘 다가 포함되는지 여부에는 약간의 차이가 있습니다. 연속 분포 수학의 개념 세계에서는 기본적으로 [0,1] (0과 1 포함) 사이의 균일 분포와 (0,1) 사이의 균일 분포 (0과 1 제외) 사이에는 차이가 없습니다. 부동 소수점 숫자의 실제 세계에서는 0과 1 사이의 가능한 값의 수가 한정되어 있으므로 그 차이는 실제이며 잠재적으로 문제가 될 수 있습니다. 예를 들어, 자연 로그 함수 내에서 생성된 숫자를 사용할 수 Math.log.

다른 분포에 대한 난수를 생성하는 것은 일반적으로 SUD PRNG에서 하나 이상의 숫자를 사용하여 관심 분포에서 적절한 값을 생성하는 "그저" 문제입니다. 원하는 최종 배포에 따라 여기에는 한 줄의 코드 또는 매우 복잡한 코드가 포함될 수 있습니다. 이 기사의 나머지 부분에서는 SUD PRNG에서 숫자 생성에 대해 계속 논의할 것입니다.

Period

유용한 PRNG는 주기가 커야 하며, 이는 반복하지 않고 많은 수의 숫자를 출력할 수 있어야 한다는 것입니다. 예를 들어, 1982년의 Wichmann Hill PRNG(나중에 자세히 설명)는 거의 7조 개의 주기를 가지고 있는 반면, 매우 인기 있는 Mersenne Twister PRNG는 2 ^19937-1 숫자의 주기를 가지고 있습니다. 전자는 현대 표준에 의해 매우 짧은 것으로 간주됩니다.

Math.random에 어떤 문제가 있습니까?

JavaScript의 내장 Math.random을 정기적으로 사용할 수 있으며 문제가 없습니다. 그러나 한 가지 큰 제한이 있습니다 : 출력을 재현 할 수 없습니다. Math.random을 사용하는 코드를 반복해서 실행하면 매번 다른 결과 집합을 얻을 수 있습니다. 대부분의 경우 실제로는 문제가 되지 않습니다. 사실 많은 (아마도) 경우에 그것은 정확히 당신이 원하는 것입니다. 예측 불가능성(적어도 출력물을 응시하고 앉아있는 인간에게는)이 정확히 필요한 것입니다. 그러나 때때로 우리는 동일한 결과 집합을 보고 싶어합니다.

잠시 자바스크립트에서 벗어나서, 출판하고 싶은 작품에 대해 시뮬레이션 실험을 해보는 것을 고려해보자. 아마도 C ++ 또는 Java 또는 R을 사용하고있을 것입니다. 결과를 재현할 수 있기를 원합니다. 이러한 언어 (및 다른 많은 언어)는 PRNG의 초기 상태를 "시드"하는 방법을 제공합니다. 어떤 식으로든 시드를 설정하면 동일한 순서의 "임의" 숫자가 나옵니다. 수학.랜덤 씨도 필요하며 직접 설정할 방법이 없습니다. 이 사양 때문에 수학.랜덤 또한 상당히 개방적이므로 출력이 [0,1] 범위에서 거의 균일한 한 경우 브라우저 공급업체가 "구현 종속 알고리즘"을 사용할 수 있습니다.

개인적인 관점에서, 저는 데이터와 개념을 모두 전달하기 위한 브라우저 기반 대화형 데이터 시각화를 매우 좋아합니다. 여기에는 시뮬레이션이 포함될 수 있습니다. 브라우저에서 실용적인 것에는 제한이 있지만 웹 작업자가 도움을 줄 수 있습니다. 시뮬레이션에는 난수가 필요한 경우가 많습니다. 난수를 재현할 수 없는 경우 시뮬레이션 조건을 다시 실행할 수 없습니다. 반복 가능한 애니메이션과 같은 다른 사용 사례도 많이 있으며 JavaScript는 더 이상 브라우저의 프로그래밍 언어가 아닙니다.

문제가 있는 PRNG

지금까지는 균일 분포 PRNG가 어떻게 작동하는지 건너 뛰었습니다. 그것은 모두 블랙 박스와 같습니다 : 함수를 한 번 이상 호출하고, 시드를 설정 한 다음 몇 가지 의사 난수가 나옵니다. 문제는 좋은 PRNG를 만드는 것이 어렵다는 것입니다. 이 주제와 여러 방법에 대한 수천 개의 논문이 있습니다. 그리고 이 주제에 대해 저보다 훨씬 더 많이 알고 있는 사람들이 뭔가를 잘못 알고 있는 것처럼 보이는 여러 사례가 있습니다. 예컨대...

RANDU

RANDU는 1950년대에 IBM에서 개발한 "선형 합동 생성기"(LCG)입니다. LCG는 새로운 의사 난수를 생성하기 위해 다음 형식의 반복 관계를 사용합니다.

RANDU의 경우 c는 0, a는 65,539, m은 2 ³¹ 입니다. c가 0이기 때문에 RANDU는 "곱셈 합동 생성기"(MCG)라고 하는 LCG의 하위 집합에 속합니다. 0에서 1 사이의 숫자를 얻으려면 (Math.random 대체에 필요한 것처럼) RANDU 재귀 관계의 결과를 m으로 나누면됩니다. JavaScript 구현 (절대 사용해서는 안됩니다!)은 다음과 같이 보일 수 있습니다.

var randu = function(seed){

   "use strict";
   
   if(!isFinite(seed)){
      throw new Error("Seed not a finite number");
   }
		   
   var x = Math.round(seed);
   var a = 65539;
   var m = Math.pow(2, 31);

   if(x<1 || x≥m){
      throw new Error("Seed out of bounds");
   }

   return function(){
      x = (a*x)%m;
      return x/m;
   };
    
};

RANDU의 반복 관계에 의해 생성된 값의 패리티는 변경되지 않습니다. 즉, 홀수 시드는 x의 홀수 값만 발생시키는 반면 짝수 시드는 x의 짝수 값만 발생시킵니다. 이것은 정확히 바람직한 속성은 아니지만 더 큰 문제가 있습니다.

LCG의 주기는 최대 m 이지만 RANDU의 경우 그보다 훨씬 짧으며 시드의 패리티에 따라 다릅니다. 홀수 시드의 경우 5억 3,600만 개가 넘지만 짝수 시드의 경우 16,384개에 불과 할 수 있습니다.

짝수 시드에 신경 쓰지 말아야 하는 또 다른 이유가 있습니다: 제너레이터의 임의성을 평가하는 일반적이고 간단한 방법 중 하나는 연속된 값 쌍을 산점도로 그리는 것입니다. 좋은 PRNG는 1x1 사각형을 상당히 균일하게 채워야 합니다. 10,000개의 난수, 5,000개의 포인트 및 1의 시드가 있으면 모든 것이 합리적으로 보입니다. ("x"는 10,000개의 난수로 구성된 (0-indexed) 배열에서 짝수 인덱스 위치에 있는 값을 참조하는 것으로 생각할 수 있습니다. 즉, 인덱스 0, 2, 4, 6... 9,996, 9,998. 산점도의 점은 다음 홀수 인덱스(1, 3, 5, 7... 9,997, 9999) "y" 값)

일부 짝수 씨앗으로 우리는 완전히 다른 것을 가지고 있습니다. 아래는 시드 32,768에 대한 산점도입니다.

분명히, 우리는 짝수 시드의 경우 점수가 부족한 것이 아닙니다. 어떤 경우에는 인접 값 간에 명확한 관계가 있습니다.

위의 randu 함수를 조정하여 시드도 거부하고 적절한 오류 메시지를 제공하는 것은 충분히 간단합니다. 불행히도 배당률 시드도 구조를 보여줍니다. 이를 보려면 연속적인 난수의 트리플렛을 살펴봄으로써 산점도 아이디어를 3차원으로 확장하기만 하면 됩니다. 3D 산점도는 종종 꽤 쓸모가 없습니다. RANDU 데이터는 이 규칙에 대한 예외를 제공합니다. (여기서 "x" 값에 대한 인덱스는 0, 3, 6, 9... 9,993, 9,996, "y" 값에 대한 인덱스는 1, 4, 7, 10... 9,994, 9997이고 "z" 값에 대한 인덱스는 2, 5, 8, 11... 9,995, 9,998.)

3,333 개의 RANDU 트리플렛이 1의 시드를 사용하여 숫자를 생성했습니다.

상자를 대충 균등하게 채우는 대신, 숫자의 세 쌍둥이는 씨앗에 관계없이 모두 15개의 평면 중 하나에 놓입니다! (사실, 짝수 시드 32,768의 경우 이것보다 더 나쁩니다.) 우리는 이것을 Math.random의 결과와 비교할 수 있습니다 (저는 이것을 위해 Chrome을 사용했습니다). 그 차이는 극명합니다.

3D 산점도의 일반적인 문제 중 하나는 그림에서 구조의 가시성이 시야각에 따라 달라질 수 있다는 것입니다. 특정 각도에서는 RANDU 플롯의 구조가 숨겨져 있습니다. 이 수에 대한 경우가 되십시오 수학.랜덤. 이 문제를 해결하기 위해 PRNG (및 적절한 경우 하나 이상의 시드)를 선택하고 다음을 사용하여 결과를 시각화 할 수있는 대화 형 버전을 만들었습니다. 웹GL. 이 데모는 다음과 같을 수 있습니다. 여기에서 찾을 수 있습니다. 그리고 난수 상자는 (마우스를 사용하여) 회전하고 다른 각도에서 볼 수 있습니다. 나는 아직 사용할 때 구조의 명백한 징후를 찾지 못했습니다. 수학.랜덤 여러 브라우저(데스크톱의 Chrome, Firefox, Maxthon, IE, Edge, Opera, iOS의 Safari)에서 사용할 수 있습니다.

3차원 이상의 격자 구조가 나타나는 것은 모든 MCG에 존재하지만 특히 RANDU에 좋지 않습니다. 1960년대부터 알려져 왔습니다. 그럼에도 불구하고 RANDU는 1970년대에도 여전히 사용되었으며 그 시대의 일부 시뮬레이션 결과는 아마도 회의적으로 보아야 할 것입니다.

뛰어나다

PRNG의 문제가 1960 년대와 70 년대에 국한되었는지 궁금 할 수 있습니다. 이 질문에 대한 짧은 대답은 "아니오"입니다. 오래된 난수 생성기에 대한 비판 후 Microsoft는 Excel 2003용 Wichmann-Hill PRNG로 변경했습니다. WH 생성기(1982년에 처음 발표 됨)는 단일 MCG의 일부 단점(예: 상대적으로 짧은 주기, 인접 값 그룹을 볼 때 보이는 격자 평면 및 초평면)을 극복하기 위해 세 개의 MCG를 결합합니다. WH의 빠른 JavaScript 구현은 다음과 같을 수 있습니다.

var wh = function(seeds){
  
   "use strict";

   if(seeds.length<3){
      throw new Error("Not enough seeds");
   }

   var xA = Math.round(seeds[0]);
   var aA = 171;
   var mA = 30269;

   var xB = Math.round(seeds[1]);
   var aB = 172;
   var mB = 30307;

   var xC = Math.round(seeds[2]);
   var aC = 170;
   var mC = 30323;
   
   if(!isFinite(xA) || !isFinite(xB) || !isFinite(xC)){
      throw new Error("Seed not a finite number");
   }

   if(Math.min(xA,xB,xC)<1 || xA≥mA || xB≥mB || xC≥mC){
      throw new Error("Seed out of bounds");
   }  

   return function(){
      xA = (aA*xA)%mA;
      xB = (aB*xB)%mB;
      xC = (aC*xC)%mC;
      return (xA/mA + xB/mB + xC/mC) % 1;
   };
	  
};

다시 우리는 인접한 값들의 집합을 2차원 또는 3차원으로 그릴 때 구조를 찾을 수 있습니다.

이것은 분명히 우리가 좋은 난수 생성기를 가지고 있는지 여부를 말하기에 충분하지 않지만 위의 플롯은 적어도 합리적으로 보입니다. (위에서 언급한 WebGL 데모에서 3차원 상자를 확인할 수도 있습니다.) 그러나 Excel의 RAND 함수에 대한 WH 알고리즘의 원래 구현에서는 때때로 음수를 뱉어냈습니다!

WH 알고리즘은 PRNG에 대한 보다 현대적이고 엄격한 여러 테스트에 실패했으며 Microsoft는 인기 있는(그러나 다소 복잡한) Mersenne Twister 알고리즘을 사용하는 것으로 보입니다.

V8

이전에는 Chrome의 Math.random 구현 출력을 사용하여 3 차원 산점도로 플로팅 할 때 난수의 트리플렛 분포가 어떻게 보이는지 설명했습니다. 그러나 Chrome의 JavaScript 엔진인 V8에서 사용하던 알고리즘에 결함이 있는 것으로 드러났습니다. 특히,이 길지만 유익한 기사에서 설명하는 것처럼 동일한 "임의" 문자열을 예상보다 훨씬 더 높은 빈도로 재현했습니다. V8 개발자는 사용 된 알고리즘을 즉시 변경 했으며 버전 49부터 Chrome에서 문제가 수정 된 것으로 보입니다.

Speed

JavaScript PRNG를 "성장"하기 전에 고려해야 할 또 다른 사항은 속도입니다. Math.random이 고도로 최적화 될 것으로 예상해야합니다. 예를 들어, 여러 브라우저를 사용한 몇 가지 매우 거친 테스트에서는 Math.random이 위의 간단한 WH 구현보다 100,000 개의 난수를 생성하는 데 ~ 3 배 더 빠르다는 것을 보여주었습니다. 이렇게 말했지만, 우리는 여전히 수십 밀리초 (적어도 내 노트북의 Chrome과 Firefox에서는)의 순서에 대해 이야기하고 있으므로 많은 수의 난수가 필요하더라도 병목 현상이 아닐 수 있습니다. 물론 더 나은 통계적 속성을 가진 더 복잡한 PRNG는 더 느릴 수 있습니다.

결론

나는 여기 표면을 거의 만지지 않았다. 나는 단지 몇 가지 간단한 PRNG를 보았고 여전히 문제가 될 수 있음을 보여주었습니다. PRNG에 대한 훨씬 더 복잡한 알고리즘이 있으며, 일부는 매우 엄격한 통계 테스트를 많이 통과했습니다. 그리고 이들 중 일부는 이미 오픈 소스 JavaScript 구현을 가지고 있습니다.

재현성이 필요하지 않은 경우 Math.random은 모든 난수 요구 사항에 적합 할 수 있습니다. 어느 쪽이든, 난수 생성기의 신뢰성이 사이트 작동 방식에 중요하다면 관련 검사를 수행해야 합니다. Math.random의 경우 JavaScript 사양이 공급업체가 사용해야 하는 특정 알고리즘을 지정하지 않기 때문에 이는 모든 대상 브라우저에서 확인하는 것을 의미합니다.

웹 앱용 JavaScript HTML5 컨트롤을 사용해 보고 놀라운 데이터 시각화 기능을 즉시 활용할 수 있습니다. 지금 무료 평가판을 다운로드하세요.

어떻게