무한대를 0과 곱하면 어떻게 될까

주의: 이 포스트에는 \lim 같은 거 안 나옵니다. 쉬운 이해를 위해 안타깝게도 엄밀함을 일부 포기했습니다. 편하게 읽어 주세요!

최근 트위터를 하다가 재밌는 글을 발견했습니다. 파라과이 위키의 캡쳐였습니다. 내용을 보니 \infty\times0=0, \infty-\infty=0이라고 적혀 있었습니다. 지금은 이 문장이 삭제되어서 문서 기록에만 남아 있습니다. 무한대 문서의 r196판입니다.

사실 이 말은 들어 보면 얼핏 보면 맞는 말 같기도 합니다. 그렇지만 과연 그럴까요? 조금만 생각해 본다면 \infty-\infty=x에서 \infty를 양쪽에 더해 주면 \infty=x+\infty가 되는데요, 무한하게 큰 숫자에다 그냥 숫자 몇 개 더해봤자 어차피 무한하게 클 텐데 굳이 x=0이 아니어도 되지 않을까요?

그런지 아닌지 확인해 봅시다. 먼저 무한대의 정의부터 살펴봅시다.

무한대의 정확한 정의가 무엇인가요?

우리는 무한대를 말 그대로 무한히 큰 수로 알고 있습니다.

처음으로 ∞ 기호를 쓴 수학자, John Wallis (1616 – 1703)

따라서 실수 중에서 어떤 수를 골라도 아마 그것보단 클 겁니다. 한 {10}^{{100}^{1000}} 정도라고 해도 어쨌든 유한하긴 유한하기 때문에 무한대보단 작을 겁니다. 이걸 수학적으로 정의한다면 어떻게 하면 좋을까요?

일단 실수 중에서 아무 거나 골라서 x라고 해 봅시다. 무한대는 그것보단 클 겁니다. 따라서 x<\infty입니다. 근데 아무 숫자나 골라도 다 되기 때문에, 우리는 모든 실수 x에 대해 x<\infty라고 할 수 있습니다. 굳이 이걸 기호를 써서 표현하자면,

    \[x<\infty\qquad\forall x\in\mathbb{N}\]

이라고 할 수 있습니다. 여기서 \mathbb{N}은 모든 실수의 집합이고, \forall x는 ‘모든 x에 대하여’라는 뜻입니다.

그럼 무한대는 실수일까요? 실수 x=\infty라고 가정해 보면, x는 실수이기 때문에 x<\infty이어야 될 겁니다. 근데 x=\infty였으니까 이걸 대입해 보면 \infty<\infty라는 모순이 발생하게 됩니다. 따라서 신기하게도 무한대는 실수가 아니라는 결론이 나옵니다. 이것은 우리가 일반적으로 알고 있는 사칙연산의 법칙들이 통하지 않는 이유이기도 합니다.

무한대의 연산

덧셈과 뺄셈

앞서 \infty는 실수가 아님을 증명했습니다. 그렇다고 복소수 같은 것도 아닐 겁니다. 실수나 복소수까지만 다뤄봤다면 생판 처음 보는 종류의, 어떻게 다뤄야 할 지 모르는 수가 등장한 겁니다.

그렇다면 무한대의 연산은 어떻게 정의하는 것이 좋을까요? 무한대의 정의를 다시 생각해 봅시다. 무한대는 무한히 큰 수입니다. 따라서 여기에다 실수 얼마를 더하거나 빼도 여전히 무한히 크기 때문에, 일단 \forall x\in\mathbb{N}에서

    \[\infty+x=\infty\]

    \[\infty-x=\infty\]

입니다. 그리고 x가 실수가 아니라 무한대일 때, \infty+\infty=\infty인 건 어차피 왼쪽(2\infty)도 오른쪽도 무한히 큰 수이기 때문에 당연합니다.

하지만 \infty-x=\infty에 의해, \infty-\infty=x가 됩니다. 즉, \infty-\infty는 어떤 실수든 될 수 있습니다. 이런 경우는 보통 ‘정의되지 않았다’고 합니다.

잘 이해가 되지 않는다면 0\div0=x의 경우를 생각해 보면 될 것 같습니다. 양 변에 0씩 ‘곱해’ 주면 0=x\times0인데, 이 경우도 모든 x에 대해 성립하기 때문에 ‘정의되지 않았다’고 합니다.

곱셈과 나눗셈

덧셈, 뺄셈과 같이 생각해 본다면 모든 실수 x > 0에 대해 다음이 성립합니다.

    \[\infty\times x=\infty\]

    \[\infty\div x=\infty\]

…그리고 만약 x < 0이라면,

    \[\infty\times x=-\infty\]

    \[\infty\div x=-\infty\]

이 될 것입니다.

이번에도 마찬가지로 \infty=\infty\times x에서 양 변을 \infty씩 ‘나눠’ 주면 \infty\div\infty=x가 되고, 따라서 \infty\div\infty도 모든 실수가 될 수 있습니다. 그래서 \infty\div\infty도 정의되지 않습니다.

그럼 마지막으로 \infty\times 0은 어떻게 될까요? 일단 \infty\times 0=x라고 하고 양 변에서 0을 ‘나눠’ 봅시다. 그러면 \infty=x\div 0이 됩니다. x\div0을 계산해 본다고 하면 얼마일까요?

a\div b=x를 ‘a에서 bx번 빼야 0이 된다’고 생각해 보면, x0이 아니라면 x에서 0을 아무리 유한히 빼도 0이 되진 않을 것 같습니다. 따라서 0을 무한 번 빼야 되고, x\div0=\infty가 됩니다. 이걸 위에 대입해 보면 \infty=\infty가 되어 모든 x에 대해 식이 성립하는 것을 알 수 있습니다. 결국 \infty\times0도 모든 실수가 될 수 있고, 무한대에 0을 곱하는 것도 정의가 안 됩니다.

물론 파라과이에서는 0이 될지도 모르겠습니다.

모든 캐릭터를 모으기 위해서는 얼마를 써야 하는가

가챠(뽑기)는 나쁜 문명입니다.

뜬금없이 웬 가챠냐고 하면, 요즘 게임을 ‘확률성 아이템’을 빼놓고는 이야기할 수 없을 정도이기 때문입니다. 물론 필자가 하고 있는 게임 대부분에도 확률성 아이템이 들어가 있습니다. 하지만 저는 확률성 아이템의 윤리성 같은 것을 논하는 현명한 소비자와는 꽤 거리가 있으므로, 전혀 반대의 논지, 즉 몇 가지 게임에서 ‘모든 캐릭터를 모으려면 얼마를 써야 할까?’(Shut up and take my money)를 중심으로 이야기해보겠습니다.

확률 계산의 기본

통계학에서 확률을 계산할 때 수학적인 표현을 위해 사용되는 개념들이 있습니다. 확률변수확률질량함수, 기댓값이 그들 중 하나입니다.

확률변수는 값과 확률을 갖는 수입니다. 보통 대문자로 표시합니다. 예를 들어 주사위를 던져서 나오는 수를 확률변수 X라고 할 수 있습니다.

확률질량함수는 확률변수와 그 값을 대응시켜 주는 함수입니다. P\left(X=x\right)과 같은 방식으로 표기합니다. 쉽게 말하자면, P\left(X=x\right)X가 x일 확률을 말합니다. 위에서 언급한 주사위를 던져서 나오는 수를 예로 들면,

    \[P\left(X=x\right) = \dfrac{1}{6} \left(x = 1, 2, 3, 4, 5, 6\right)\]

이라고 표시할 수 있겠습니다.

그리고 기댓값은 말 그대로 확률변수에 기대하는 값입니다. 평균이라고도 하는 기댓값은 E\left(X\right)로 표기합니다. 주사위의 눈 같은 경우엔 평균 E\left(X\right) = 3.5입니다.

조작된 주사위. 거의 매번 7 혹은 11이 나오게 해 줍니다.

그러나 주사위 안쪽에 쇠 같은 걸 붙여 둬서 한 면만 나올 확률이 비정상적으로 높은 주사위가 있다고 생각해 봅시다. 예를 들어, 6은 나올 확률이 \dfrac{95}{100}고, 나머지는 나올 확률이 \dfrac{1}{100}밖에 안 된다고 생각해 봅시다. 이 때도 주사위를 많이 던졌을 때 평균 E\left(X\right) = 3.5라고 생각할 수 있을까요?

아닙니다. 이 때는 거의 6이 나올 것이므로 평균이 6에 가까우면 가까웠지 3.5에 가깝진 않을 겁니다. 그래서 평균, 즉 기댓값을 구할 때는 평균과 확률을 곱해 줘야 합니다. 이 때 기댓값은 이렇게 구할 수 있습니다.

    \[E\left(X\right) = 1\times\dfrac{1}{100} + 2\times\dfrac{1}{100} + 3\times\dfrac{1}{100} + 4\times\dfrac{1}{100} + 5\times\dfrac{1}{100} + 6\times\dfrac{95}{100} = 5.85\]

5.85는 3.5보다는 조금 믿을 수 있는 숫자 같네요!

아무튼 이걸 일반화하면, P\left(X=x_i\right) = p_i \left(i=1, 2, \ldots, n\right)일 때 아래와 같이 적을 수 있습니다.

    \[E\left(X\right) =\sum_{i=1}^{n} {x_i}{p_i}\]

또한 보이다시피 E\left(X\right){x_i}{p_i}들의 합으로 이루어져 있기 때문에, E\left(aX+b\right)=aE\left(X\right)+b, \sum_{}^{} E\left(X\right)=E\left(\sum_{}^{} X\right) 등도 성립합니다.

모든 카드를 얻으려면 – 등급별 가중치가 없을 때

여러 가지 게임들의 예를 들어 보겠습니다만, 일단 ‘사운드 볼텍스’의 예를 들어 보겠습니다. 사운드 볼텍스는 리듬게임이지만 스토리를 진행함에 있어 높은 등급의 카드를 뽑는 것이 거의 필수적입니다. 등급이 나누어져 있긴 하고 실제로 중복 카드를 일부러 더 잘 나오게 설정했다는 게 체감된다고 하지만, 일단은 실제 확률이 고지되어 있지 않으므로 등급별 확률이 정해져 있지 않고 모든 카드가 나올 확률이 같다고 가정하겠습니다.

‘사운드 볼텍스 IV’의 PUR 등급 카드 중 하나의 모습. 필자도 갖고 있습니다.

일단 몇 가지를 가정해 봅시다.

  1. 카드는 한 번 뽑는 데 1,000원입니다.
  2. 카드는 한 장 씩 뽑고, 다음 카드를 뽑기 전에 카드를 확인합니다.
  3. 카드는 전체 n종류입니다. 각 카드 종류가 등장할 확률은 \dfrac{1}{n}입니다.
  4. n종류의 카드를 전부 뽑으면 더 이상 뽑지 않습니다.
  5. 게임에서는 이미 나온 카드를 10번 다시 뽑으면 다음 한 장은 중복이 아님이 보장되지만, 여기서는 무시합니다.

이 때 우리는 평균적으로 카드를 총 몇 장 뽑아야 모든 종류의 카드를 뽑을 수 있을까요? 즉 뽑아야 하는 카드 수를 확률변수 X라고 둘 때 E\left(X\right)는 얼마일까요?

그냥 구하고자 하니 막막합니다. 조금 더 쉬운 방법을 생각해 봅시다. 이미 i-1종류의 카드를 모았을 때 새로운 종류의 카드를 모으는 데 뽑는 횟수를 확률변수 Y_i라고 두면 X = Y_1 + Y_2 + Y_3 + \ldots + Y_n으로 생각할 수 있습니다.

 

 

이렇게 하면 P\left(Y_i = k\right)는 i-1종류를 뽑은 상황에서 k번째에 새로운 종류의 카드를 뽑은 셈이 되므로, k-1번은 원래 뽑았던 카드 i-1종류 중 하나를, 마지막에는 남은 카드 종류 n-\left(i-1\right)개 중 하나를 뽑는 셈이 됩니다. 즉,

    \[P\left(Y_i = k\right) = {\left(\dfrac{i-1}{n}\right)}^{k-1}{\left(1-\dfrac{i-1}{n}\right)}\]

가 됩니다. 식이 나왔으니 카드 i-1종류가 있을 때 새로운 종류의 카드를 뽑으려면 몇 장을 뽑아야 하는지에 대한 기댓값을 구할 수 있는데요, 이론적으로는 무한 장 뽑아도 새 종류가 안 나올 수도 있으니 k에는 사실상 1부터 무한대까지 들어갈 수 있겠습니다. 그러므로,

    \[E\left(Y_i\right) =\sum_{k=1}^{\infty} {k}P\left(Y_i = k\right)\]

    \[=\sum_{k=1}^{\infty} k{\left(\dfrac{i-1}{n}\right)}^{k-1}{\left(1-\dfrac{i-1}{n}\right)}\]

식이 복잡하므로 \dfrac{i-1}{n} = r으로 치환하고 계속 계산해 보면,

    \[=\sum_{k=1}^{\infty} k{r^{k-1}{\left(1-r\right)}\]

    \[=\left(1-r\right)\sum_{k=1}^{\infty} kr^{k-1}\]

여기서 r1보다 작으므로 위의 멱급수는 무한등비급수의 합을 이용해 계산할 수 있습니다. 항등식 \sum_{k=1}^{\infty} r^{k} = \dfrac{1}{1-r}에서 양변을 r에 대해 미분하면 \sum_{k=1}^{\infty} kr^{k-1} = \dfrac{1}{{\left(1-r\right)}^2}이므로, 이를 이용해서 정리하면

    \[E\left(Y_i\right) = \left(1-r\right)\dfrac{1}{{\left(1-r\right)}^2}\]

    \[= \dfrac{1}{1-r}\]

라는 꽤 간단한 식이 됩니다. 최종적으로 r = \dfrac{i-1}{n}을 다시 대입하고 정리해 주면

    \[E\left(Y_i\right) = \dfrac{n}{n-i+1}\]

입니다.

처음에 Xn개의 Y_i로 쪼갰으니까 X = \sum_{i=1}^{n} Y_i라고 쓸 수 있겠습니다. 앞서 언급한 기댓값의 정의에 의해

    \[E\left(X\right) = E\left(\sum_{i=1}^{n} Y_i\right) = \sum_{i=1}^{n} E\left(Y_i\right)\]

이므로, E\left(Y_i\right) = \dfrac{n}{n-i+1}를 대입하면

    \[E\left(X\right) = \sum_{i=1}^{n} \dfrac{n}{n-i+1}\]

입니다. 여기서 u = n-i+1, 즉 i = n-u+1로 치환해 버린다면 1에서부터 n까지의 i의 범위는 n에서부터 1까지의 u의 범위가 되고, 시그마는 범위가 반대여도 결과는 같으므로 식은

    \[E\left(X\right) = \sum_{u=n}^{1} \dfrac{n}{u} = n\sum_{u=1}^{n} \dfrac{1}{u}\]

이 나옵니다. \sum_{u=1}^{n} \dfrac{1}{u}는 달리 간단히 할 방법이 없으므로 여기서 만족하고 Wolfram|Alpha에 맡기도록 합시다.

적용

이제 식에 대입하는 일만 남았습니다! 만약 카드 한 세트가 총 31장이라고 하고 31장 안에서만 카드가 나온다고 한다면, n = 31일 때 E\left(X\right)

    \[E\left(X\right) =31\sum_{u=1}^{31} \dfrac{1}{u} \approx 124.84460\]

이므로, 약 124,845원을 넣으면 모든 카드를 수집할 수 있다는 뜻이 되겠습니다! 물론 실제 게임에서는 이미 나온 카드를 10번 다시 뽑으면 다음 한 장은 중복이 아님이 보장되지만 이를 무시하고 계산한 것이기에 숫자가 현저히 크게 나오는 감도 없지 않습니다.

모든 아이돌을 프로듀스하려면 – 등급별 가중치가 있을 때

그러나 많은 게임들은 그렇게 호락호락하지 않습니다. 바로 등급에도 확률을 부여하기 때문입니다.

‘아이돌마스터 신데렐라 걸즈 스타라이트 스테이지’의 SSR 봉투.

대표적으로 ‘아이돌 마스터 신데렐라 걸즈 스타라이트 스테이지’는 노멀, 레어, S레어, SS레어의 4개 등급의 카드를 만들어 놓았습니다. 5명의 아이돌을 유닛으로 편성해 즐기는 리듬게임인데, SS레어 아이돌들이 점수와 직결되는 합계 어필 수치가 현저히 높고 부가 능력치도 훨씬 좋기 때문에 S레어 5인으로 덱을 구성해 게임을 하는 것보다 SS레어 5인으로 구성하는 것이 훨씬 점수가 잘 나와서 높은 점수를 얻으려면 SS레어 아이돌의 존재는 필수적입니다. 결정적으로 일러스트가 상당히 예뻐서 수집욕구를 불러일으키기도 합니다.

하지만 이 게임은 SSR를 얻을 수 있는 확률은 1.5%라고 공지해 두고 있습니다. 결국 98.5%는 S레어 이하의 등급이라는 뜻이죠. 그러면 모든 종류의 SSR 아이돌을 얻기 위해서는 얼마만큼의 돈이 필요할까요?

몇 가지를 가정하겠습니다.

  1. 아이돌은 한 번 스카우트하는 데 스타 쥬얼 250개가 필요합니다. 스타 쥬얼 0.85개는 1엔입니다.
  2. 아이돌은 한 명 씩 스카우트하고, 다음 아이돌을 스카우트하기 전에 아이돌의 이름을 기억해 둡니다.
  3. SS레어 아이돌은 전체 n명입니다. 각 아이돌이 등장할 확률은 등급 내에서 \dfrac{1}{n}입니다. 한정 아이돌은 한정으로 생각하지 않습니다.
  4. SS레어 아이돌이 등장할 확률은 p입니다.
  5. n명의 SS레어 아이돌을 전부 스카우트하면 더 이상 스카우트하지 않습니다.

이번에도 사운드 볼텍스에서 계산했던 것과 같이 확률변수 Xn개의 Y_i로 쪼개서 계산합시다. 하지만 이번에는 SSR가 아닌 아이돌은 고려하지 않습니다. 저번처럼 P\left(Y_i = k\right)는 i-1명을 스카우트한 상황에서 k번째에 새로운 아이돌을 스카우트한 것인데, k-1번은 원래 스카우트했던 SSR 아이돌 i-1명 중 하나 또는 SR 이하 아이돌을, 마지막에는 SSR 등급에 아직 스카우트하지 못한 아이돌 n-\left(i-1\right)명 중 하나를 뽑는 셈이 됩니다.

여기서 SSR 등급에 남은 아이돌 n-\left(i-1\right)명 중 한 명을 스카우트하는 확률은 p\left(1-\dfrac{i-1}{n}\right)입니다. 원래 스카우트했던 SSR 아이돌 i-1명 중 하나 또는 SR 이하 아이돌을 스카우트하는 경우는 전체 카드 중 SSR 등급에 아직 스카우트하지 못한 아이돌 n-\left(i-1\right)명 중 한 명을 제외하고 누구를 스카우트하든 상관없는 경우이므로, 확률은 1 - p\left(1-\dfrac{i-1}{n}\right)이라고 할 수 있겠습니다. 따라서,

    \[P\left(Y_i = k\right) = {\left(1 - p\left(1-\dfrac{i-1}{n}\right)\right)}^{k-1}{\left(p\left(1-\dfrac{i-1}{n}\right)\right)}\]

계산하기 쉽게 p\left(1-\dfrac{i-1}{n}\right) = s로 놓으면

    \[P\left(Y_i = k\right) = {\left(1 - s\right)}^{k-1}{\left(s\right)\right)}\]

1-s=r로 놓으면

    \[P\left(Y_i = k\right) = r^{k-1}{\left(1-r\right)\right)}\]

으로 지난번과 똑같은 형태가 됩니다. 다만 r 안의 식이 지난번과 다를 뿐입니다.

역시 이론적으로는 무한 번 뽑아도 안 나올 수 있으므로 지난번과 같은 계산을 하면

    \[E\left(Y_i\right) = \dfrac{1}{1-r} = \dfrac{1}{s}\]

    \[= \dfrac{n}{p\left(n-i+1\right)}\]

이 됩니다. E\left(X\right)도 계산해 보면

    \[E\left(X\right) = \sum_{i=1}^{n}\dfrac{n}{p\left(n-i+1\right)}\]

    \[= \dfrac{1}{p}n\sum_{i=1}^{n}\dfrac{1}{\left(n-i+1\right)}\]

이므로, 앞서 \sum_{i=1}^{n}\dfrac{1}{\left(n-i+1\right)} = \sum_{u=1}^{n}\dfrac{1}{u}로 계산한 것과 같이

    \[E\left(X\right) = \dfrac{n}{p}\sum_{u=1}^{n}\dfrac{1}{u}\]

가 됩니다. 따라서 기댓값은 등장 확률에 반비례함을 알 수 있습니다.

적용

데레스테 SSR 소유율이라는 사이트에 의하면 현재(2017년 8월 13일) SSR 아이돌은 총 127명입니다. (통상 70명, 한정 57명) 또한, SSR 확률은 1.5%이므로 p = \dfrac{3}{200}입니다.

한정 아이돌을 고려하지 않고 127명이 가챠에서 모두 나올 수 있다고 가정하면, n = 127일 때

    \[E\left(X\right) = \dfrac{200\times 127}{3}\sum_{u=1}^{127}\dfrac{1}{u}\]

    \[\approx\dfrac{200\times 127}{3}\times 5.4253346\approx45934.5\]

이므로, 평균적으로 스타 쥬얼을 11,483,625(11483625)개, 즉 구매량에 따른 효율에 따라 평균적으로 13,353,052엔(13353052엔, \approx 1.35억원)을 과금하면 SSR 아이돌을 전부 모을 수 있습니다.

반면 통상 아이돌 70명만 고려한다면, n = 70일 때

    \[E\left(X\right) = \dfrac{200\times 70}{3}\sum_{u=1}^{70}\dfrac{1}{u}\]

    \[\approx\dfrac{200\times 70}{3}\times 4.8328368\approx22553.2\]

이므로, 이 경우엔 스타 쥬얼 5,638,300개가 필요합니다. 그러므로 평균적으로 6,633,294엔(6633294엔, \approx 0.670억원)을 과금하면 통상 SSR 아이돌을 전부 모을 수 있습니다.

신데렐라 페스 한정 아이돌, SSR 마에카와 미쿠. 한 아이돌은 보통 여러 카드에 등장합니다.

6월 말에 신데렐라 페스를 진행했을 때 SSR 확률이 3%로 고정되었습니다. 이 때의 p = \dfrac{3}{100}이므로 페스 기간 동안에만 가챠를 돌린다면, 소모되는 비용은 등장 확률에 반비례하기 때문에 현재는 위에 적힌 가격의 반값으로 전부 스카우트하는 것을 기대해 볼 수 있습니다.

스타 쥬얼을 얻을 수 있는 경로가 필요한 스타 쥬얼의 양에 비해 꽤 적은 비율이지만 과금 외에도 존재하므로 이를 고려한다면 위에 적힌 가격보다는 적을 수도 있습니다.

모든 용사를 얻으려면 – 등급별 가중치와 결제 한정 캐릭터를 고려할 때

용사에게 등급이 있지만 4성 이후로는 등급을 올리는 게 가능해 오히려 도감을 채우기 위해 5성 이상보다는 4성이 선호되는 게임 ‘크루세이더 퀘스트’

‘크루세이더 퀘스트’는 특이한 게임입니다. 뽑기로 얻을 수 없는 ‘전설 용사’를 제외하고 1~3성 용사는 ‘일반 용사’, 4~6성은 ‘고급 용사’로 분류됩니다. 용사에 등급이 매겨져 있는 건 다른 게임과 다를 게 없으나, 용사들은 조금의 노력으로 더 높은 단계로 승급할 수 있습니다. 2~4성으로의 승급은 아예 랜덤이지만 5~6성으로의 승급은 고정됩니다. 예를 들어 3성 가챠레인저B는 4성 바이올렛으로 승급이 가능하지만, 4성 바이올렛이 승급하면 5성 인형사 바이올렛, 6성 마법인형사 바이올렛이 고정되는 식입니다.

전설 용사 ‘병아리’. 게임을 시작할 때 바로 얻을 수 있습니다.

하지만 고급 용사는 또 ‘승급 용사’와 ‘계약 전용 용사’로 나뉩니다. 계약 전용 용사는 보석을 5~6개 소모하는 ‘황금 계약서’에서 확률적으로 나옵니다. 그러면 모든 ‘계약 전용 용사’를 얻기 위해서는 얼마가 필요할까요?

이번의 조건은 다음과 같습니다.

  1. 용사는 연속으로 계약한다고 가정합니다. 첫 번째 계약 가격을 무시하고, 한 번 계약하는 데 보석 5개를 소모합니다. 보석 1개는 550원입니다.
  2. 용사는 한 명 씩 계약하고, 다음 용사를 계약하기 전에 용사의 이름을 확인합니다.
  3. 4성 이상의 용사는 전체 n명입니다. 각 용사가 등장할 확률은 \dfrac{1}{n}입니다. 이 중 한정 용사는 m명입니다.
  4. n종류의 용사와 모두 계약하면 더 이상 계약하지 않습니다.
  5. 게임에서는 10명씩 계약하면 마지막 1명은 4성 이상이 보장되지만, 여기에서는 고려하지 않습니다.
  6. 게임에서는 기간 한정으로 특정 용사의 계약확률이 증가하지만, 여기에서는 고려하지 않습니다.

앞서 확률이 p인 등급의 아이돌 n명을 전부 스카우트할 때의 기댓값은

    \[E\left(X\right) = \dfrac{n}{p}\sum_{u=1}^{n}\dfrac{1}{u}\]

이었습니다. 여기서 ‘모든 계약 전용 용사’를 4~6성 내의 또 하나의 등급으로 생각한다면, 4~6성 내에서 계약 전용 용사와 계약할 확률은 \dfrac{m}{n}이므로 더 복잡한 계산을 할 필요 없이 모든 계약 전용 용사와 계약했을 때 계약 횟수에 대한 기댓값은

    \[E\left(X\right) = \dfrac{n}{\dfrac{m}{n}p}\sum_{u=1}^{m}\dfrac{1}{u}\]

    \[= \dfrac{n^2}{mp}\sum_{u=1}^{m}\dfrac{1}{u}\]

이 됩니다.

적용

황금 계약서에서 4성 이상의 용사가 나올 확률은 19%입니다. 또한 용사등급표에 따르면 현재(2017년 8월 13일) 크루세이더 퀘스트에는 계약서로 획득할 수 없는 이벤트, 전설 용사를 제외하고 승급 용사 43명, 계약 용사 58명이 있으므로 n = 43 + 58 = 101, m = 58, p = \dfrac{19}{100}으로 두면

    \[E\left(X\right) = \dfrac{101^2 \times 100}{58 \times 19}\sum_{u=1}^{58}\dfrac{1}{u}\]

    \[\approx \dfrac{101^2 \times 100}{58 \times 19} \times 4.646254 \approx 4300.95\]

이므로 평균적으로 보석을 21,505개, 즉 11,827,750원(11827750원)을 과금하면 모든 계약 용사를 얻을 수 있습니다. 물론 이 게임은 보석을 획득할 수 있는 경로가 과금 이외에도 굉장히 다양하고 계약 용사 확정을 고려하지 않았으므로 실제 과금액은 이보다 현저히 적으리라 예상됩니다.

정리

확률형 아이템이 게임을 진행하는 데 중요한 요소가 되는 대표적인 게임 ‘아이돌 마스터 신데렐라 걸즈 스타라이트 스테이지’. 물론 여기다 쓸 돈을 다른 데다 쓰는 게 나을 수도 있겠지만, 적어도 자동차에 쓰면 자동차가 춤추고 노래하진 않을 것 같습니다.

계산하면서 큰 값이 나오리라고는 예상하고 있었지만, 예상을 훨씬 웃도는 숫자들이 나오면서 많이 놀랐습니다.

특히 ‘아이돌 마스터 신데렐라 걸즈 스타라이트 스테이지’의 경우 모든 아이돌을 모으는 데에 평균적으로 몇 천만원대의 과금이 필요하다는 것을 계산하고 나서는 차라리 자동차를 사는 게 낫다고 생각될 수도 있겠지만, 역시 자동차가 춤추고 노래하진 않기에 나름의 의미가 있다고 생각합니다.

마지막으로, 언급된 모든 게임들이 캐릭터를 모두 모으지는 않아도 진행하는 데에 큰 무리는 없으므로, 언급된 가격들은 전부 모으실 게 아니라면 ‘이렇게 큰 숫자가 나오는구나’ 라고 생각해 주시길 부탁드리겠습니다.

컴퓨터는 삼각함수를 어떻게 계산하는가

주의: 이 포스트는 약간의 미적분학 지식이 있어야 이해하기 쉽습니다. 그래도 설명을 위해 약간의 증명은 들어가 있으니, 아는 부분은 스킵하셔도 됩니다.

 

우리는 언제나 직각과 직사각형이 편합니다. 인류는 직교좌표계를 발명했습니다. 그리고 컴퓨터 모니터의 픽셀 배열은 대부분 가로세로 수백~수천 개 픽셀로 이루어진 격자로 이루어져 있고, 이는 직교좌표계로 접근할 수 있습니다. 직교좌표계로 화면을 그리면 픽셀 하나하나를 관리하기가 제일 쉽고 자유로워서가 아닐까 싶습니다.

만약에 누군가가 사칙연산만 제공되는 엔진으로 게임을 개발한다고 생각합시다. 직교좌표계 위에 그려진 어떤 도형이 있는데 이 도형을 회전시켜야 한다고 합니다. 어떻게 하면 될까요?

사실 수학은 이미 답을 알고 있습니다. 어떤 픽셀의 좌표 \left ( x, y\right )에 대해 회전된 좌표 \left ( x', y'\right )

    \[ \begin{bmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{bmatrix} \begin{bmatrix} x\\ y \end{bmatrix} = \begin{bmatrix} x'\\ y' \end{bmatrix} \]

다른 말로

    \[ \left\{\begin{matrix} x'=x\cos\theta-y\sin\theta \\ y'=x\sin\theta+y\cos\theta \end{matrix}\right. \]

임이 자명합니다. 이걸 회전하기 전의 이미지의 모든 픽셀\left ( x, y\right )에 대해 한 번씩 해 주면 회전한 이미지가 나옵니다. 참 쉽죠?

사칙연산만 갖고 삼각함수를 계산하라고요?

컴퓨터가 어떻게 삼각함수를 계산하는지를 논하기로 했으니까, 컴퓨터가 할 수 있는 연산만을 이용해야겠습니다. 아주 기본적인 연산만 사용 가능한 프로세서에서 말입니다.

그럼 대체 삼각함수는 어떻게 근사할 수 있을까요? \sin과 \cos를 구하면 \tan 등은 나눗셈으로도 구할 수 있으니까 \sin과 \cos를 구하는 데 집중해 봅시다.

삼각함수를 다항함수로 근사하면 되지 않을까요?

다항함수는 사칙연산만으로 계산할 수 있으니 삼각함수의 그래프와 비슷한 다항함수를 만들어서 거기다 집어넣으면 되겠네요!

근데 그 다항함수는 대체 어떻게 구할까요? 여기서 테일러 급수가 등장합니다.

테일러 급수

테일러 급수를 이용하면 어떤 미분 가능한 함수라도 다항함수로 근사해 버릴 수 있습니다. 세상에 그런 흑마법이 존재하냐고요? 네, 놀랍게도 존재합니다!

증명

우선 어떤 함수 f'\left(x\right )a부터 x까지 정적분해 봅시다. 미적분의 정의에 의해 아래 식과 같이 표현할 수 있습니다.

    \[ \int_{a}^{x}f'\left(t\right )\mathrm{d}t=f\left(x\right )-f\left(a\right ) \]

그리고 위 식을 변형해 봅시다.

    \[ \int_{a}^{x}f'\left(t\right )\mathrm{d}t=\int_{a}^{x}\left(-1\right )\left(-f'\left(t\right )\right )\mathrm{d}t \]

이제 -1을 적분하고 -f'\left(t\right )를 미분해 부분적분법을 씁시다. 이 때 f\left(x\right )가 무한히 미분 가능하다면, 부분적분법도 무한히 써 버릴 수 있습니다. 그러니까

    \[ \cdots = \left.\begin{matrix} \left ( -\left ( x-t \right )f'\left ( t \right ) - \dfrac{\left( x-t \right )^2}{2}f''\left ( t \right ) - \dfrac{\left( x-t \right )^3}{6}f'''\left ( t \right ) - \cdots \right ) \end{matrix}\right|_{a}^{x} \]

가 됩니다. 이 때 적분변수 t와 관계없는 x는 상수취급됩니다. 이 식을 전개해 보면

    \[ \cdots = \left ( x-a \right )f'\left ( a \right ) + \dfrac{\left( x-a \right )^2}{2!}f''\left ( a \right ) + \dfrac{\left( x-a \right )^3}{3!}f'''\left ( a \right ) + \cdots\\ \]

    \[ = f\left ( x \right )-f\left ( a \right ) \]

마지막으로 f\left ( a \right )를 이항하면

    \[ f\left ( x \right ) = f\left ( a \right ) + \left ( x-a \right )f'\left ( a \right ) + \dfrac{\left( x-a \right )^2}{2!}f''\left ( a \right ) + \dfrac{\left( x-a \right )^3}{3!}f'''\left ( a \right ) + \cdots \]

f^{\left ( n \right )fn번 미분한 함수라고 할 때

    \[ f\left ( x \right ) = \sum_{n=0}^{\infty} \dfrac{f^{\left ( n \right )}\left ( a \right )}{n!}\left( x-a \right )^n \]

가 유도됩니다. 이 때 a에 어떤 수를 넣어도 근사됩니다.

그래서 이게 삼각함수랑 무슨 상관이에요!

삼각함수는 무한히 미분 가능합니다. 그러니까, f 대신 삼각함수를 넣으면 삼각함수를 다항함수로 근사할 수 있습니다. 어떤 삼각함수 f\left ( x \right )에 대해 a0을 대입해 보면

    \[ f\left ( x \right ) = f\left ( 0 \right ) + \left ( x-0 \right )f'\left ( 0 \right ) + \dfrac{\left( x-0 \right )^2}{2!}f''\left ( 0 \right ) + \dfrac{\left( x-0 \right )^3}{3!}f'''\left ( 0 \right ) + \cdots \]

    \[ = f\left ( 0 \right ) + x f'\left ( 0 \right ) + \dfrac{x^2}{2!}f''\left ( 0 \right ) + \dfrac{x^3}{3!}f'''\left ( 0 \right ) + \cdots \]

인데요, f\left ( x \right ) = \sin x라고 하고 대입해 보면

    \[ \sin x = \sin\left ( 0 \right ) + x \sin'\left ( 0 \right ) + \dfrac{x^2}{2!}\sin''\left ( 0 \right ) + \dfrac{x^3}{3!}\sin'''\left ( 0 \right ) + \cdots \]

    \[ = 0 + \left ( x \cdot 1 \right ) + \left ( \dfrac{x^2}{2!}\cdot 0 \right ) + \left ( \dfrac{x^3}{3!}\cdot -1 \right ) + \left ( \dfrac{x^4}{4!}\cdot 0 \right ) + \left ( \dfrac{x^5}{5!}\cdot 1 \right ) + \cdots \]

정리하면

    \[ \therefore \sin x = x - \dfrac{x^3}{3!} + \dfrac{x^5}{5!} - \dfrac{x^7}{7!} + \dfrac{x^9}{9!} + \cdots \]

마찬가지로

    \[ \cos x = 1 - \dfrac{x^2}{2!} + \dfrac{x^4}{4!} - \dfrac{x^6}{6!} + \dfrac{x^8}{8!} + \cdots \]

이 됩니다. 중간 과정에 비해서 정말 간단한 식이 되었습니다. 더구나, 우리의 궁극적인 목표인 사칙연산만으로 삼각함수 표현하기에 성공했습니다! (팩토리얼은 곱셈의 연속일 뿐이니까요!)

근데, 식이 참… 무한합니다. 이건 어떻게 하면 좋을까요? 우리는 어차피 floating-point 변수들은 굉장히 정확하지 않다는 걸 잘 알고 있습니다. 그러니까 저 식을 어디까지만 계산하고 그 이후의 오차는 무시해 버려도 됩니다.

위에서 구한 다항식을 최고차항이 n인 항까지만 계산하고, 그 이후는 무시해버립시다. 그리고 이걸 n차 근사식이라고 합시다. 이제부터 차수를 올려나가면서 n차 근사식의 그래프를 그려보겠습니다.

그래프

▶ 1차 근사식: f\left ( x \right ) = x

Rendered by QuickLaTeX.com

… 하나도 비슷해보이진 않습니다. 다음!

▶ 3차 근사식: f\left ( x \right ) = x - \dfrac{x^3}{3!}

Rendered by QuickLaTeX.com

앞에서는 감을 좀 잠은 거 같기도 한데, 겨우 \dfrac{\pi}{2}도 가기 전에부터 조금씩 이상하더니 아래로 곤두박질쳐버리는군요. 다음!

▶ 5차 근사식: f\left ( x \right ) = x - \dfrac{x^3}{3!} + \dfrac{x^5}{5!}

Rendered by QuickLaTeX.com

이제 \dfrac{\pi}{2}에서도 비슷해졌네요! 다음!

▶ 7차 근사식: f\left ( x \right ) = x - \dfrac{x^3}{3!} + \dfrac{x^5}{5!} - \dfrac{x^7}{7!}

Rendered by QuickLaTeX.com

\pi 근처까지도 꽤 비슷해졌습니다. 몇 개만 더 해 봅시다.

▶ 9차 근사식: f\left ( x \right ) = x - \dfrac{x^3}{3!} + \dfrac{x^5}{5!} - \dfrac{x^7}{7!} + \dfrac{x^9}{9!}

Rendered by QuickLaTeX.com

거의 원본 함수와 같아졌습니다. 사실 여기부터는 이제 0 < x < \pi일 때는 그냥 가져다 써도 오차는 크지 않을 것 같습니다. 어차피 \sin은 주기함수이고 대칭함수이니까 0 < x < \dfrac{\pi}{2}에서만 정확해도 다른 범위에서는 함수의 특징을 이용해 계산해내면 됩니다.

▶ 11차 근사식: f\left ( x \right ) = x - \dfrac{x^3}{3!} + \dfrac{x^5}{5!} - \dfrac{x^7}{7!} + \dfrac{x^9}{9!} - \dfrac{x^{11}}{11!}

Rendered by QuickLaTeX.com

차이가 얼마나 나는지 점점 이렇게 봐서는 확인하기가 어렵습니다. 마지막으로 13차 근사식까지만 그려보겠습니다.

▶ 13차 근사식: f\left ( x \right ) = x - \dfrac{x^3}{3!} + \dfrac{x^5}{5!} - \dfrac{x^7}{7!} + \dfrac{x^9}{9!} - \dfrac{x^{11}}{11!} + \dfrac{x^{13}}{13!}

Rendered by QuickLaTeX.com

그래프 범위 내에서는 거의 똑같은 곡선이 그려집니다.

프로그래밍 언어에서의 구현 사례

OpenJDKStrictMath 네이티브 코드가 13차 근사식을 통해 삼각함수를 구현하고 있습니다. 정확성을 위해서 13차 근사식을 그대로 사용하진 않고, 이렇게 조금 변형해서 사용합니다.

    \[ \sin x \sim x - \dfrac{x^3}{3!} + \dfrac{x^5}{5!} - \dfrac{x^7}{7!} + \dfrac{x^9}{9!} - \dfrac{x^{11}}{11!} + \dfrac{x^{13}}{13!} \]

    \[ \frac{\sin x}{x} \sim 1 - \dfrac{x^2}{3!} + \dfrac{x^4}{5!} - \dfrac{x^6}{7!} + \dfrac{x^8}{9!} - \dfrac{x^{10}}{11!} + \dfrac{x^{12}}{13!} \]

그러므로 r을 이렇게 정의할 때

    \[ r = x^3 \left( \dfrac{1}{5!} + x^2 \left( -\dfrac{1}{7!} + x^2 \left( \dfrac{1}{9!} + x^2 \left( -\dfrac{1}{11!} + {x^{2}} \cdot \dfrac{1}{13!} \right) \right) \right) \right) \]

\sin x는 이렇게 표현할 수 있습니다.

    \[ \sin x \sim x + x^3 \cdot \left(-\dfrac{1}{3!} + x^2 r \right) \]

예를 봅시다. sin 함수에서 __kernel_sin 함수를 호출할 때 코드에서 |x| \prec \pi/4라면 y, iy의 값은 모두 0입니다. 이외의 범위에서는 적절한 범위로 평행이동시켜 __kernel_sin 혹은 __kernel_cos 함수값을 구합니다.

#include "fdlibm.h"
 
#ifdef __STDC__
static const double
#else
static double
#endif
half =  5.00000000000000000000e-01, /* 0x3FE00000, 0x00000000 */
S1   = -1.66666666666666324348e-01, /* 0xBFC55555, 0x55555549 */
S2   =  8.33333333332248946124e-03, /* 0x3F811111, 0x1110F8A6 */
S3   = -1.98412698298579493134e-04, /* 0xBF2A01A0, 0x19C161D5 */
S4   =  2.75573137070700676789e-06, /* 0x3EC71DE3, 0x57B1FE7D */
S5   = -2.50507602534068634195e-08, /* 0xBE5AE5E6, 0x8A2B9CEB */
S6   =  1.58969099521155010221e-10; /* 0x3DE5D93A, 0x5ACFD57C */
 
#ifdef __STDC__
double __kernel_sin(double x, double y, int iy)
#else
double __kernel_sin(x, y, iy)
double x,y; int iy; /* iy=0 if y is zero */
#endif
{
double z,r,v;
int ix;
ix = __HI(x)&0x7fffffff; /* high word of x */
if(ix<0x3e400000) /* |x| &lt; 2**-27 */
{if((int)x==0) return x;} /* generate inexact */
z = x*x;
v = z*x;
r = S2+z*(S3+z*(S4+z*(S5+z*S6)));
if(iy==0) return x+v*(S1+z*r);
else return x-((z*(half*y-v*r)-y)-v*S1);
}

소스에서
S1 = -\dfrac{1}{3!} \approx -1.66666667 \times {10}^{-1}
S2 = \dfrac{1}{5!} \approx 8.33333333 \times {10}^{-2}
S3 = -\dfrac{1}{7!} \approx -1.98412698 \times {10}^{-4}
S4 = \dfrac{1}{9!} \approx 2.75573137 \times {10}^{-6}
S5 = -\dfrac{1}{11!} \approx -2.50521084 \times {10}^{-8}
S6 = \dfrac{1}{13!} \approx 1.58969099 \times {10}^{-10}
으로 근사식의 계수들이 근사되어 하드코딩되어 있는 것을 알 수 있습니다. 또한 z=x^2, v=zx=x^3으로 계산하고 있습니다. 13차 근사식을 그대로 쓴다면 항마다 1번, 3번, 5번, …, 13번의 곱셈을 해야 하지만 x^2를 새 상수로 두면 곱셈을 줄일 수 있어서 이런 방법을 사용하지 않았을까 하는 생각입니다.

다른 방법으로도 계산할 수 있나요?

물론 다른 방법들도 있습니다. 예를 들어 볼더가 1956년에 고안한 CORDIC(COordinate Rotation DIgital Computer) 알고리즘을 이용해 삼각함수의 값을 근사하는 것도 가능합니다.

간단하게 설명하자면, 맨 위에서 회전을 하기 위해 곱하는 행렬을

    \[ \begin{bmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{bmatrix} \]

으로 소개했습니다만, CORDIC 알고리즘은 이를 tan 함수만으로 표현해

    \[ R_i = \dfrac{1}{\sqrt{1 + \tan^2 \left(\gamma_i\right)}} \begin{bmatrix} 1 & -\tan \left(\gamma_i\right) \\ \tan \left(\gamma_i\right) & 1 \end{bmatrix} \]

로 변형하고, 컴퓨터가 빠르게 계산할 수 있도록 \tan \left(\gamma_i\right) = \pm2^{-i}가 되는 \gamma_i, 즉 \arctan\left(2^{-i}\right)의 값들과 이 때의 \dfrac{1}{\sqrt{1 + \tan^2 \left(\gamma_i\right)}}의 값들을 하드코딩해 두고 원하는 각도에 가까워질 때까지 i를 하나씩 증가시키면서
\arctan\left(2^{-i}\right)를 더하거나 빼면서 행렬 계산을 해나가는 알고리즘입니다.

이 알고리즘은 계산기에 주로 쓰이고 있고, 인텔의 8087 ~ 80486 CPU에도 채용되어 왔습니다.

컴퓨터는 이렇게 삼각함수를 계산합니다.