피보나치 수를 행렬로 구하는 것과 관련된 것들

슬랙에서 피보나치 수를 행렬로 구하는 것에 대해 이야기가 나왔는데,



12850번 본대 산책2 문제를 봤는데, 잘 모르겠어서 피보나치 수를 행렬로 나타내는 것을 찾아봤는데, Baekjoon Online Judge blog에  https://www.acmicpc.net/blog/view/28 가 있었다. 나중에 한 번 자세히 봐야지 하면서 훑어보고 있었는데, 중간에 1629번 곱셈이라는 문제가 나와있었다.



문제는 A를 B번 곱한 수를 구하는 것인데, 즉 A의 B제곱을 구하는 문제인데, A, B의 범위가 무려 2,147,483,647...
바로 질문게시판의 질문들과 답변들을 봤는데 다행히 어느정도 설명되어 있었다.

일단 핵심 아이디어는 이것이다.
짝수의 제곱 같은 경우에서 곱셈 횟수를 단축시킬 수 있는데, 예를 들면 8제곱 같은 경우는 4제곱의 제곱이다. 그리고 재귀를 이용해서 필요한 경우만 계산하도록 하여 더 연산횟수를 줄인 것 같다. 역시 알고리즘은 아름답고 멋지고 재미있는 것 같다. 아직까진 어려운 부분이 많긴 하지만...

그리고 이것을 찾아보라는 말도 있었다. : repeated squaring algorithm