m의 최적값

대부분의 응용에서, 하위 비트는 중요하지 않으며, m = w의 선택은 상당히 만족스럽다 -- 단, 난수를 사용하는 프로그래머가 현명하게 그렇게 하는 경우에 한해.

지금까지의 논의는 MIX와 같은 "부호-크기" 컴퓨터를 기반으로 했다. 보수 표기법을 사용하는 기계에도 유사한 아이디어가 적용되지만, 교훈적인 변형이 있다. 예를 들어, DECsystem 20 컴퓨터는 2의 보수 산술을 가진 36비트를 가지고 있다; 두 개의 비음수 정수의 곱을 계산할 때, 하위 절반은 더하기 부호와 함께 최하위 35비트를 포함한다. 이 기계에서 우리는 따라서 w = 2^36이 아닌 2^35를 취해야 한다. IBM System/370 컴퓨터의 32비트 2의 보수 산술은 다르다: 곱의 하위 절반은 32비트 전체를 포함한다. 일부 프로그래머들은 이것이 단점이라고 느꼈는데, 피연산자가 양수일 때 하위 절반이 음수일 수 있고 이를 수정하는 것이 귀찮기 때문이다; 그러나 실제로 이것은 난수 생성의 관점에서 뚜렷한 장점인데, 우리가 2^31 대신 m = 2^32를 취할 수 있기 때문이다! (연습문제 4 참조).

1. [M12] 연습문제 3.2.1-3에서 우리는 최선의 합동 생성기는 승수 a가 m과 서로소일 것이라고 결론지었다. 이 경우 m = w일 때 (aX + c) mod w를 결과가 레지스터 X에 나타나게 하여 (1)의 네 개 대신 단 세 개의 MIX 명령어로 계산할 수 있음을 보여라.

1. [M12] 연습문제 3.2.1-3에서 우리는 최선의 합동 생성기는 승수 a가 m과 서로소일 것이라고 결론지었다. 이 경우 m = w일 때 (aX + c) mod w를 결과가 레지스터 X에 나타나게 하여 (1)의 네 개 대신 단 세 개의 MIX 명령어로 계산할 수 있음을 보여라.

2. [16] 다음 특성을 가진 MIX 서브루틴을 작성하라:

종료 조건: X <- rA <- (aX + c) mod w, rX <- 0, 오버플로 끔.

종료 조건: X <- rA <- (aX + c) mod w, rX <- 0, 오버플로 끔.

(따라서 이 서브루틴 호출은 선형 합동 수열의 다음 난수를 생성할 것이다.)

3. [M25] 많은 컴퓨터는 두 워드 수를 한 워드 수로 나누는 기능을 제공하지 않는다; 그들은 z와 y가 워드 크기 w보다 작은 비음수 정수일 때 himult(z, y) = floor(zy/w)와 lomult(z, y) = zy mod w와 같은 단일 워드 숫자에 대한 연산만 제공한다. 0 < a, c < m < w이고 m이 w를 나누지 않는다고 가정하고, himult와 lomult의 관점에서 az mod m을 평가하는 방법을 설명하라. a, m, w에 의존하는 미리 계산된 상수를 사용할 수 있다.