pow 함수의 내부 구현에 대해...

지수함수(pow) 즉 

 

$$x^y$$

 

의 시간복잡도는 얼마나 될까?

 

y를 N이라고 한다면 일반적으로는 분할정복을 통해 구현한 O(logN) 이다.(x의 크기에 종속적이지 않다고 가정하자)

 

그렇다면 pow(5, 1) 과 pow(5, 64)의 실행시간을 측정해보면 이론적으로는 8배, 자잘한 로직처리까지 생각해도 의미있는 차이가 있어야 한다.

 

실제로 코드를 돌려보면

 

다음과 같은 측정결과를 볼 수 있다.(각각 1000만회씩 루프를 돌렸다)

 

놀랍게도 유의미한 차이가 나지 않는다.

 

그 이유는 pow함수는 내부적으로 x86과 이를 계승한 amd64 아키텍처에 포함된 FYL2X 명령어를 통해 구현되어 있기 때문이다.

 

여기서 잠깐 FYL2X명령어가 어떤것인지 보고가자. (출처 : https://c9x.me/x86/html/file_module_x86_id_130.html)

 

단순하게 얘기하면 

$$y{\log_2{x}}$$

의 값을 계산해주는 어셈블리 명령어다.

 

이 명령어의 실행시간은 일정 범위내의 x, y 값에 대해서 상수시간이 보장된다고 한다.

 

$$x^y = 2^{y{\log_2{x}}}$$

 

우리가 구하고자 하는식은 위와 같이 변형될 수 있고 2의 지수승은 비트연산으로 상수시간에 구할 수 있기에 pow의 실행시간은 상수시간임이 보장되고 위의 측정결과가 나오게 된 것이다.

 

하지만 반대로 일정범위 밖의 연산을 pow함수로 실행하게 되면

 

 

위와 같이 유의미한 차이를 볼 수 있다.

 

(64비트 아키텍처 기준이라 65승 이후로 유의미한 차이를 내지 않을까 싶었는데 측정결과 비슷했다, 정확한 범위를 알려면 어셈블리와 명령어에 대한 추가적인 이해가 필요할듯)

 

오늘의 결론

 

일반적인 숫자범위 내에서 pow의 실행시간은 상수시간이다.

 

수학 라이브러리들 함부로 최적화한다고 나대지 말자(?)