로그인하고 있지 않습니다. 편집하면 당신의 IP 주소가 공개적으로 기록됩니다. 계정을 만들고 로그인하면 편집 시 사용자 이름만 보이며, 위키 이용에 여러 가지 편의가 주어집니다.스팸 방지 검사입니다. 이것을 입력하지 마세요!이 문서는 컴퓨터가 [[거듭제곱]]을 빠르게 계산하는 방법을 다룬다. <math>a^b</math>의 값을 구하려고 할 때, <math>a, b</math>중 하나가 정수가 아닌 실수이면 계산 결과는 일반적으로 정수가 아니다. 이 경우 <math>e^{b\ln a}</math>와 같이 변형하거나, 이항급수인 <math>(1+x)^b=\sum_{n=0}^{\infty} \binom{b}{n}x^n</math> 등으로 [[테일러 급수]]를 적용하여 근삿값을 산출한다. 그런데 밑이 정수이고, 지수가 자연수일 때 '''참값'''을 직접 출력하고자 한다면, 아래 방법을 이용한다. 이 알고리즘은 <math>a</math>가 다항식 또는 행렬 등 거듭제곱이 적용되는 어떤 대상이라도 쓸 수 있다. == 지수의 이진법 전개 == 먼저 입력받은 지수를 [[이진법]]으로 적는다. 그 다음 각 비트의 값인 0 또는 1에 따라 계산 과정을 결정한다. 이진법 상에서 <math>n+1</math>비트라 가정하고, 맨 오른쪽 비트는 0번째로 취급한다. :<math>b=\sum_{k=0}^{n} e_k2^k, e_k \in \{0, 1\}</math> :<math>a^b=\prod_{k=0}^{n} a^{e_k2^k}</math> :<math>A=\{k: 0 \leq k \leq n, e_k=1\}</math> === 오른쪽 비트부터 읽기 === 위 식에서 <math>c_k=a^{2^k}</math>라 하면 <math>a^b=\prod_{k=0}^{n} c_k^{e_k}=\prod_{k \in A}c_k</math>와 같이 쓸 수 있다. 한편 <math>c_0=a, c_n=c_{n-1}^2 (n \leq 1)</math>을 이용하면 주어진 식을 빠르게 셈할 수 있다. 오른쪽 비트부터 읽는 방식은 가장 작은 항인 <math>c_0</math>부터 시작해서 제곱을 반복하고, 비트의 값이 1인 항마다 주어진 수에 곱하는 방식이다. * <math>\text{Input }a, n \leftarrow \lfloor \log_2 a \rfloor</math> * <math>x \leftarrow 1, c \leftarrow a, k \leftarrow 0</math> * [※] <math>e_k=1</math>이면 <math>x \leftarrow cx</math> * <math>k=n</math>이면 여기서 알고리즘을 종료하고 <math>x</math>를 반환한다. * <math>c \leftarrow c^2, k \leftarrow k+1</math> 다음 [※]로 돌아간다. 예를 들어 3의 13제곱을 셈하고자 한다면, 13을 이진법인 1101<sub>(2)</sub>과 같이 적고, 비트를 맨 오른쪽부터 읽어서 1, 0, 1, 1 순으로 적용한다. a=3, n=3, x=1, c=3, k=0 e={1, 0, 1, 1} e[0]==1: x=c*x ##x=3 c=c*c, k=k+1 ##c=9, k=1 e[1]==0: pass c=c*c, k=k+1 ##c=81, k=2 e[2]==1: x=c*x ##x=243 c=c*c, k=k+1 ##c=6561, k=3 e[3]==1: x=c*x ##x=1594323 k==3: END 최종 결과: 1594323 === 왼쪽부터 비트 읽기 === 이번에는 지수의 비트를 반대로 가장 큰 자리부터 읽는다. <math>a^r=\begin{cases}(a^{\frac{n}{2}})^2 &\text{if } 2 \mid r \\ a\cdot (a^{\frac{n-1}{2}})^2 &\text{if } 2 \nmid r \end{cases}</math>을 이용하여 아래 수열을 정의한다. :<math>x_0=a, x_{k+1}=\begin{cases}x_{k-1}^2 &\text{if } e_{n-k}=0 \\ ax_{k-1}^2 &\text{if } e_{n-k}=1 \end{cases}</math> 이렇게 식을 세우면 <math>x_n=a^b</math>에 도달하며, 알고리즘은 아래와 같이 세울 수 있다. * <math>\text{Input }a, n \leftarrow \lfloor \log_2 a \rfloor</math> * <math>x \leftarrow 1, j \leftarrow n</math> * <math>e_j=1</math>이면 <math>x \leftarrow ax</math> * [※] <math>x \leftarrow x^2, j \leftarrow j-1</math> * <math>j=0</math>이면 여기서 알고리즘을 종료하고 <math>x</math>를 반환한다. 그렇지 않으면 [※] 지점으로 돌아간다. 이번에는 3의 13제곱을 왼쪽부터 읽는 방식으로 계산해본다. 이번에는 비트를 위 예시와는 반대로 맨 왼쪽부터 1, 1, 0, 1 순으로 읽는다. a=3, n=3, x=1, j=3 e={1, 0, 1, 1} e[3]==1: x=a*x ##x=3 x=x*x, j=j-1 ##x=9, j=2 e[2]==1: x=a*x ##x=27 x=x*x, j=j-1 ##x=729, j=1 e[1]==0: pass x=x*x, j=j-1 ##x=531441, j=0 e[0]==1: x=a*x ##x=1594323 j==0: END 최종 결과: 1594323 == 모듈러 연산 == [[모듈러산술]]에서 거듭제곱을 셈할 때에는 상술한 알고리즘에서 모든 곱셈을 ''곱셈 후 나머지 연산''으로 치환하면 된다. [[정수론]] 영역 중 [[소수판정법]]에서 이 연산을 많이 적용한다. 대표적으로 [[페르마의 소정리]], [[프로트의 정리]], [[밀러-라빈 소수판정법]], [[포클링턴-레머 소수판정법]] 등 <math>a^b \mod p</math> 꼴의 식을 계산하는 알고리즘에서 유용하게 쓰인다. 또, [[소인수분해]] 중 [[폴라드 p-1 소인수분해법]]에서도 마찬가지로 쓸 수 있다. {{각주}} {{수론 알고리즘}} [[분류:알고리즘]] 요약: 리브레 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-동일조건변경허락 3.0 라이선스로 배포됩니다(자세한 내용에 대해서는 리브레 위키:저작권 문서를 읽어주세요). 만약 여기에 동의하지 않는다면 문서를 저장하지 말아 주세요. 글이 직접 작성되었거나 호환되는 라이선스인지 확인해주세요. 리그베다 위키, 나무위키, 오리위키, 구스위키, 디시위키 및 CCL 미적용 사이트 등에서 글을 가져오실 때는 본인이 문서의 유일한 기여자여야 하고, 만약 본인이 문서의 유일한 기여자라는 증거가 없다면 그 문서는 불시에 삭제될 수 있습니다. 취소 편집 도움말 (새 창에서 열림) | () [] [[]] {{}} {{{}}} · <!-- --> · [[분류:]] · [[파일:]] · [[미디어:]] · #넘겨주기 [[]] · {{ㅊ|}} · <onlyinclude></onlyinclude> · <includeonly></includeonly> · <noinclude></noinclude> · <br /> · <ref></ref> · {{각주}} · {|class="wikitable" · |- · rowspan=""| · colspan=""| · |} {{lang|}} · {{llang||}} · {{인용문|}} · {{인용문2|}} · {{유튜브|}} · {{다음팟|}} · {{니코|}} · {{토막글}} {{삭제|}} · {{특정판삭제|}}(이유를 적지 않을 경우 기각될 가능성이 높습니다. 반드시 이유를 적어주세요.) {{#expr:}} · {{#if:}} · {{#ifeq:}} · {{#iferror:}} · {{#ifexist:}} · {{#switch:}} · {{#time:}} · {{#timel:}} · {{#titleparts:}} __NOTOC__ · __FORCETOC__ · __TOC__ · {{PAGENAME}} · {{SITENAME}} · {{localurl:}} · {{fullurl:}} · {{ns:}} –(대시) ‘’(작은따옴표) “”(큰따옴표) ·(가운뎃점) …(말줄임표) ‽(물음느낌표) 〈〉(홑화살괄호) 《》(겹화살괄호) ± − × ÷ ≈ ≠ ∓ ≤ ≥ ∞ ¬ ¹ ² ³ ⁿ ¼ ½ ¾ § € £ ₩ ¥ ¢ † ‡ • ← → ↔ ‰ °C µ(마이크로) Å °(도) ′(분) ″(초) Α α Β β Γ γ Δ δ Ε ε Ζ ζ Η η Θ θ Ι ι Κ κ Λ λ Μ μ(뮤) Ν ν Ξ ξ Ο ο Π π Ρ ρ Σ σ ς Τ τ Υ υ Φ φ Χ χ Ψ ψ Ω ω · Ά ά Έ έ Ή ή Ί ί Ό ό Ύ ύ Ώ ώ · Ϊ ϊ Ϋ ϋ · ΐ ΰ Æ æ Đ(D with stroke) đ Ð(eth) ð ı Ł ł Ø ø Œ œ ß Þ þ · Á á Ć ć É é Í í Ĺ ĺ Ḿ ḿ Ń ń Ó ó Ŕ ŕ Ś ś Ú ú Ý ý Ź ź · À à È è Ì ì Ǹ ǹ Ò ò Ù ù · İ Ż ż ·  â Ĉ ĉ Ê ê Ĝ ĝ Ĥ ĥ Î î Ĵ ĵ Ô ô Ŝ ŝ Û û · Ä ä Ë ë Ï ï Ö ö Ü ü Ÿ ÿ · ǘ ǜ ǚ ǖ · caron/háček: Ǎ ǎ Č č Ď ď Ě ě Ǐ ǐ Ľ ľ Ň ň Ǒ ǒ Ř ř Š š Ť ť Ǔ ǔ Ž ž · breve: Ă ă Ğ ğ Ŏ ŏ Ŭ ŭ · Ā ā Ē ē Ī ī Ō ō Ū ū · à ã Ñ ñ Õ õ · Å å Ů ů · Ą ą Ę ę · Ç ç Ş ş Ţ ţ · Ő ő Ű ű · Ș ș Ț ț 이 문서에서 사용한 틀: 틀:Skin (원본 보기) (준보호됨)틀:각주 (원본 보기) (준보호됨)틀:둘러보기 상자 (원본 보기) (보호됨)틀:둘러보기 상자/핵심 (원본 보기) (보호됨)틀:수론 알고리즘 (편집) 틀:틀바 (원본 보기) (준보호됨)