더시드위키
최근 변경최근 토론
특수 기능

namuid(r13 판)

보기RAWBlame되돌리기비교
[주의!] 문서의 이전 버전(에 수정)을 보고 있습니다. 최신 버전으로 이동
이 문서는 분류가 되어 있지 않습니다. 분류:분류에서 적절한 분류를 찾아 문서를 분류해주세요!
유니코드 기준 현대 한글의 모든 완성형 글자는 총 19×21×28=11,17219 \times 21 \times 28 = 11,172자이며, 66개의 문자가 연달아 사용되므로 표본 공간의 크기는
11,1726=1,944,399,775,118,767,509,471,232≈1.9443997751×102411,172^6 = 1,944,399,775,118,767,509,471,232 \approx 1.9443997751 \times 10^{24}

입니다. 편의상 이를 NN이라고 하겠습니다.

하나의 작업에서 xx개의 식별자를 생성했을 때, 이중 '적어도 하나의 식별자 충돌이 발생할 확률'을 구하고자 합니다. 이 확률을 pp로 둡시다. 예를 들어 p=30%p = 30\%라면 대략 30%30\%의 확률로 충돌이 발생할 가능성이 있다는 뜻입니다.

이어서 이 확률식을 역으로 계산하여 '식별자 충돌이 발생할 확률이 pp 이상이기 위해서는 적어도 xx개의 식별자를 생성해야 하는지'를 보이려고 합니다. namuid의 식별자 충돌이 거의 불가능함을 보이고 싶으므로 p=0.1%p = 0.1\%로 두고 테일러 전개로 필요한 표본의 수 xx의 하한을 근사해 봅시다. 일단 자명하게
p=1−NPxNx\displaystyle p = 1 - \frac{_N\mathrm P_x}{N^x}

이므로 어떤 함수 f(x)f(x)에 대해 f(x)≤1−pf(x) \leq 1 - p 를 성립시키는 가장 큰 xx를 근사하면 됩니다. 우선 위에 쓴 pp를 구하는 수식을 곱의 형태로 정리해 봅시다.
1−p=∏k=1x−11−kN\displaystyle 1 - p = \prod^{x-1}_{k = 1} 1 - \frac kN

이어서 e−kNe^{-\frac kN}을 테일러 전개하고 선형 근사를 구하면
e−kN=∑i=0(−kN)ii!≈1−kN\displaystyle e^{-\frac kN} = \sum_{i = 0} \frac{\left(-\frac kN\right)^i}{i!} \approx 1 - \frac kN

이 근사를 적용해서 '어떤 함수' f(x)f(x)가 1−p1 - p를 근사하도록 조립해 봅시다.
f(x)=e−x(x−1)2N=∏k=1x−1e−kN≈∏k=1x−11−kN=1−p\displaystyle f(x) = e^{-\frac{x(x-1)}{2N}} = \prod^{x - 1}_{k = 1} e^{-\frac kN} \approx \prod^{x - 1}_{k = 1} 1 - \frac kN = 1 - p

보기 편하게 로그 형태로 전개하면 다음과 같이 xx에 대한 이차방정식이 나옵니다. 편의상 f(x)f(x)를 yy라고 두었습니다.
x2−x+2Nln⁡y=0\displaystyle x^2 - x + 2N \ln y= 0

방정식을 풀면 역함수를 구할 수 있겠군요. 시행 횟수 xx는 양의 정수임이 자명하니 음수근은 버리겠습니다.
f−1(y)=x=12+14−2Nln⁡y\displaystyle f^{-1}(y) = x = \frac12 + \sqrt{\frac14 - 2N \ln y}

k>62,375,838,650=6.237583865×1010k > 62,375,838,650 = 6.237583865 \times 10^{10}