알고리즘 K의 구조

알고리즘 K ("초난수" 생성기). 10자리 십진수 X가 주어졌을 때, 이 알고리즘은 X를 아마도 무작위 수열에서 다음에 와야 할 숫자로 변경하는 데 사용될 수 있다. 이 알고리즘이 상당히 무작위한 수열을 산출할 것으로 예상될 수 있지만, 아래에 주어진 이유는 사실 그것이 전혀 좋지 않다는 것을 보여준다. (독자는 이 알고리즘을 얼마나 복잡한지 관찰하는 것 외에 자세히 연구할 필요가 없다; 특히 단계 K1과 K2에 주목하라.)

K1. [반복 횟수 선택.] Y <- |X/10^9|, X의 가장 중요한 자릿수를 설정한다. (우리는 K2부터 K13까지의 단계를 정확히 Y + 1번 실행할 것이다; 즉, 무작위화 변환을 무작위 횟수만큼 적용할 것이다.)

K2. [무작위 단계 선택.] Z <- |X/10^8| mod 10, X의 두 번째로 중요한 자릿수를 설정한다. 단계 K(3 + Z)로 간다. (즉, 우리는 이제 프로그램의 무작위 단계로 점프한다.)

K2. [무작위 단계 선택.] Z <- |X/10^8| mod 10, X의 두 번째로 중요한 자릿수를 설정한다. 단계 K(3 + Z)로 간다. (즉, 우리는 이제 프로그램의 무작위 단계로 점프한다.)

K3. [> 5 x 10^9 보장.] X < 5000000000이면, X <- X + 5000000000을 설정한다.

K4. [중간 제곱.] X를 |X^2/10^5| mod 10^10으로, 즉 X의 제곱의 중간으로 교체한다.

K4. [중간 제곱.] X를 |X^2/10^5| mod 10^10으로, 즉 X의 제곱의 중간으로 교체한다.

K5. [곱셈.] X를 (1001001001 X) mod 10^10으로 교체한다.

K6. [의사 보수.] X < 100000000이면, X <- X + 9814055677을 설정한다; 그렇지 않으면 X <- 10^10 - X를 설정한다.