Strict Standards: Non-static method Soojung::addReferer() should not be called statically in /home/lifthrasiir/sites/sapzil.info/soojung/settings.php on line 79

Warning: Cannot modify header information - headers already sent by (output started at /home/lifthrasiir/sites/sapzil.info/soojung/settings.php:79) in /home/lifthrasiir/sites/sapzil.info/soojung/classes/Counter.class.php on line 63

Strict Standards: Non-static method Entry::getEntry() should not be called statically in /home/lifthrasiir/sites/sapzil.info/soojung/entry.php on line 51

Strict Standards: Non-static method Soojung::entryIdToFilename() should not be called statically in /home/lifthrasiir/sites/sapzil.info/soojung/classes/Entry.class.php on line 182

Strict Standards: Non-static method Soojung::queryFilenameMatch() should not be called statically in /home/lifthrasiir/sites/sapzil.info/soojung/classes/Soojung.class.php on line 55
TokigunStudio3 | 블로그: 큰 숫자의 앞뒷 자릿수를 빨랑 빨랑 알아 내는 방법

내용으로 바로 넘어 가기


TokigunStudio3

1 / 3283   


더 이상 이 블로그는 운영되지 않습니다. 새 블로그로 가 주세요.

큰 숫자의 앞뒷 자릿수를 빨랑 빨랑 알아 내는 방법

2005/01/04 PM 11:09 | 일상/진지하게 | 5 comments | 0 trackbacks | AllBlog: vote, to pocket

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

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

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

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

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

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

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

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

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

TrackBack URL: http://sapzil.info/soojung/trackback.php?blogid=285

Comment: 페이군 (2005/01/05 AM 01:23)

오 그런 방법이 있다니!!!

통 뭔말인지;

Comment: 토끼군 (2005/01/05 AM 02:02)

페이군: 고등학교 수학은 대충 익혀 두는 게 좋겠지. -_-;;; 크게 어려운 내용은 아님.

Comment: 정태영 (2005/01/05 AM 10:44)

^ 는. xor이니까..
3^3^3^3^3 = 0^3^3^3 = 0^0^3 = 0^3 = 3 이군요..

Comment: falsetru (2005/01/05 AM 11:37)

요즘 고등수학은 내 고등학교 시절과는 다른듯 -_-;

Comment: 토끼군 (2005/01/05 PM 01:18)

정태영: 앗 그런 썰렁한 농담을 =33
falsetru: 음... 사실 고등 수학이 아니라 중등 수학으로도 충분한 내용입니다. 그런데도 제가 "고등 수학"이라고 못 박은 이유는 추론 과정을 대충 대충 넘겨 버렸기 때문에 -_-; 이런 걸 유추하려면 고등 수학 정도에서 다루는 추론력은 있어야 한다고 판단했기 때문이지요... 근데 제가 까먹고 빼 먹은 게 있는데, "a mod b"는 a를 b로 나눈 나머지, [a]는 a의 정수부(a-[a]는 물론 a의 소수부)를 의미합니다. -_-;;;

Copyright (c) 1995-2005, Kang Seonghoon (Tokigun).