난수 생성의 병목 현상: 바로 당신의 PRNG가 아니다

이 글은 이야기를 통해 난수 생성 알고리즘 최적화에서 중요한 문제점을 부각합니다. 병목 현상은 PRNG 자체가 아니라 특정 범위 내의 난수를 생성하는 방법에 있을 수 있다는 것입니다. 저자는 고전적인 모듈러 연산, 부동 소수점 곱셈, 정수 곱셈, 그리고 기각 샘플링이나 비트 마스킹과 같은 몇 가지 편향되지 않은 방법을 포함한 다양한 범위의 난수 생성 방법을 비교합니다. 실험 결과는 최적의 방법은 PRNG와 데이터 규모에 따라 다르다는 것을 보여주지만, Lemire의 정수 곱셈 기반 방법은 최적화 후 뛰어난 성능을 보이며 성능을 크게 향상시켰습니다. 이 글에서는 다양한 PRNG의 성능도 비교하여 가장 빠른 PRNG라도 범위 생성 방법 최적화로 인한 성능 향상에는 훨씬 못 미친다는 것을 발견했습니다.