간만에 puzzlist 님 홈페이지를 들어 갔는데 3^3^3^3^3(도대체 이게 3³³³³인 지 ((((3³)³)³)³)³인 지 어찌 알란 말이야)가 얼마나 큰 수인 지 묻는 글이 보여서 간단하게 계산해 주고(다들 알겠지만, 전자가 훨씬 더 큰 수이다) 답장을 달아 줬다. 이런 류의 거듭제곱 계산은 사실 크게 어려운 건 아니고... 일종의 "요령"만 안다면 쉽게 구할 수 있다. (물론 이 요령들은 정수론의 기초 상식에서 간단하게 유추할 수 있지만)
별 거 아니긴 하지만, 일단 여기서는 N = a^b 꼴의 숫자를 계산하는 방법을 간단하게 정리하겠다. 아, 이 내용들을 이해하는 데는 고등 수학으로도 충분하다 :)

자릿수 구하기
가장 쉬운 축에 속한다. 자릿수 n = log₁₀N + 1로 표현할 수 있다. 물론, 위에서 말했듯이 N = a^b니까, n = log₁₀a^b + 1 = b log₁₀a + 1이 되겠다.

앞의 자릿수 구하기
양수 N에 대해서, N = 10^log₁₀N이라는 건 잘 알고 있을 것이다. 만약 N = p 10^q로 표현된다는 걸 알고 있다고 한다면, 위의 식은 다음과 같이 고칠 수 있다.
N = 10^{q + log₁₀p} = 10^q 10^log₁₀p
그럼 도대체 이게 뭔 소리냐? 하면, log₁₀N의 소숫점 전개를 알고 있다면 앞쪽(significant) 유효자리를 쉽게 구할 수 있다 이거다. (12345678...919191이라면 12345678이 이 앞쪽 유효자리에 해당된다)

기계적으로 이 방법을 구현한다면 이렇게 되겠지.
1. n = log₁₀N을 구한다. 물론, n의 정수부 + 1이 자릿수가 된다.
2. n의 소수부를 분리해서 n'라 하자.
3. 10^n'를 구한 뒤 앞쪽 유효자리를 적당히 잘라 낸다. 이 때 실제로 사용할 수 있는 유효자릿수는 n의 정확도에 관계되는데, 배정도 부동 소숫점이라 하더라도 유효자릿수가 턱없이 부족하기 때문에 웬만큼 큰 수를 다룰 경우 매쓰매티카, 메이플 같은 CAS들을 쓸 것을 권한다. (CAS가 아니더라도 실수를 적절한 유효 자릿수로 나타낼 수 있으면 된다)

실습을 해 보자. N = 3³³³³이라 하면,
n = 3333 log₁₀3 = 1590.245141980...
자릿수: [n]+1 = 1591자리
앞쪽 유효자리: 10^n-[n] = 10^{0.245141980...} = 1.75849841268...
(실제로 N은 175849841268201098336...으로 시작한다. 파이썬 같은 걸로 확인해 보라!)

참고: b가 크다면 p도 커지기 때문에 아무리 유효숫자를 늘려도 소숫점 아래 자리를 확인할 수 없는 경우가 있다. (예를 들어서 -- 내가 아는 한에는 -- 위에서 든 3³³³³는 죽어도 앞쪽 유효자리를 구할 수 없다.) 이럴 때는... 과감히 포기하거나 좋은 시스템에서 한 수만자리 유효자릿수 잡고 계산을 하시던지... 알아서 하세요 ~_~

뒤의 자릿수 구하기
뒷쪽 유효자리를 구하기 위해서는 조금 다른 방법을 사용해야 한다.
일단 우리가 구하려는 걸 수학적으로 표시해 보면, a^b의 마지막 m자리는 a^b mod 10^m가 된다.
여기서 정수론을 들먹여야 할 때가 되었는데, 오일러의 나머지 함수라고도 불리는 φ(phi) 함수가 있다. 가장 간단하게 정의하자면, φ(n)은 n보다 작거나 같은 수 중 n이랑 서로 소인 자연수의 갯수이다. (당연하지만, n이 솟수라면 φ(n) = n-1 되겠다.) 이 함수에 대한 자세한 설명은 MathWorld를 참고하자.
근데 왜 이 함수가 나왔냐 하면, 다음과 같이 Euler's Totient Theorem이라 불리는 중요한 성질이 있기 때문이다. 자연수 a와 n이 있다고 하면,
a^φ(n) ≡ 1 (mod n)
이 된다. 이걸 조금 응용하면 다음 결과도 얻을 수 있다.
a^b ≡ a^{b mod φ(n)} (mod n)
이게 바로 우리가 원하는 결과 아니겠는가? 결국, b가 무진장 큰 수일 경우 φ(n)의 나머지를 b 대신에 써 먹을 수도 있다는 것이다!
참고로 φ(10^m) = 4 10^m-1라는 걸 정의에서 구할 수 있으므로, 괜히 쓸데 없이 phi 함수를 따로 구현할 필요는 없다. :)

...여기까지만 알아도 좋겠지만, m이 크면 클 수록 이 방법을 그대로 쓰기에는 귀찮은 감이 많다. (m=20이라면 너무 시간이 많이 걸린다!) 이런 경우에는 a^b mod c를 빠르게 계산할 수 있는 binary exponentiation 같은 방법을 쓰는 것이 좋은데, 여기에 대해서 말하기는 너무나도 귀찮기 때문에 The Prime Glossary를 뒤져 보길 권한다. (파이썬 같은 경우 2.3부터는 이 과정을 자동으로 처리해 주기는 하지만, 지금 해 보니까 이게 숫자 커지면 또 안 된다고 발악을 해서 그냥 binary exponentiation 구현해서 썼다. -_-;)

위의 실습을 마저 해 보자. N의 마지막 3자리를 구한다고 하면 φ(10³) = 400이므로, 3³³³³ ≡ 3¹³³ (mod 10³)이고 3¹³³ mod 10³ = 523이다. (실제로 N은 3414753523로 끝난다.)