random_u64() % n은 균등하지 않다, 저자는 확률 분포를 직접 적는 random_choice()를 권한다

10개 정수로 3개 고르는 부분에서 나도 헷갈렸는데, random_u64() % 3이면 한 버킷만 5×10^-20 정도 과대평가되는 거임. rand()는 값이 32767개뿐이라 버킷 수에 따라 편향이 훨씬 흔함.

5×10^-20 과대평가를 언제부터 신경 써야 하는지 궁금해지더라.

rand()가 32767인 건 MingW/MSVCRT 얘기고, glibc는 RAND_MAX가 2147483647임.

진짜 원하는 건 거부 샘플링임. 위키 페이지는 복잡해 보이지만 구현은 웃길 정도로 단순함. 범위 밖이면 버리고 다시 뽑으면 됨. 랜덤 숫자를 아껴 써야 할 자원처럼 다루는 프로그래머가 너무 많음.

그 위키 페이지는 다차원으로 너무 깊이 들어가더라. 그냥 범위 밖이면 리롤이고, 0부터 n까지에서 n이 들어갈 만큼만 비트를 뽑으면 됨.

랜덤 숫자가 아깝진 않지만 생성에 시간이 걸림. 거부 샘플링은 분기가 하나 늘고 그게 얼마나 자주 타는지가 중요함. 내 property-testing 프레임워크에서는 큰 랜덤 배열을 더 효율적으로 만드니 성능이 올라갔음.

random uint API가 저수준이라기보다는 그냥 잘못된 API를 쓰는 것임. 'n비트를 무작위로 1이나 0으로'와 '확률 분포에 따라 원소 선택'은 별개 문제고, 표준 라이브러리에 std.choice가 있어야 함.

randomness test로는 NIST SP-800-22가 있고, paranoid_crypto의 테스트는 아카이브됨. whitening transformation으로 균등 분포에 가깝게 만들 수도 있음.

랜덤이 랜덤하지 않은 게 아니라 operator%가 나쁘게 만드는 거임.

맞음. rand()에 modulo 쓰면 안 된다는 글은 널려 있는데 제일 쉬워서 다들 그렇게 함.

그래도 그렇게 쓰면 클릭베이트가 안 되잖아.

modulo는 균등 매핑이 아님. Lemire의 nearly divisionless method나 거부 샘플링 쓰고 넘어가면 됨.

커널마다 trig/transcendental 함수 결과가 같다는 보장이 없어서 (libc vs musl) CI에서만 실패하는 문제를 겪고 github.com/pmarreck/random을 만들었음.

normal PRNG에 Box-Muller 대신 Ziggurat을 왜 안 썼는지 궁금함.

Uniform(0,1) PRNG가 기본 프리미티브인 건 맞음. 어떤 실수 확률변수든 역분위 변환으로 표현되니까. 근데 더 좋은 UI만으로 실수를 줄일 거라고는 안 봄. 이분 탐색도 라이브러리가 널려 있는데 직접 짜다 버그 나는 걸 흔히 봄. 퍼징이나 결정적 시뮬레이션 테스트가 필요함.

그 논리는 니르바나 오류임. 안전벨트나 난간도 100% 막지 못한다고 안 만들진 않음. 더 쓰기 쉬운 API는 개발 시간도 아끼고 오류도 줄임.

암호 다루는 사람에겐 엄청 중요한 얘기겠지만 나는 게임 만드는 사람이라 이론으로 재밌게 읽음.

글에는 없지만 흔히 modulo bias라고 부름. romailler.ch에 정리된 글이 있음.