O(1) 거듭제곱과 바빌로니아 법 알고리즘의 해석

 

오랜만에 올리는 글인데, 별로 실용성이 없는글이기도하고 시간이 많지 않기때문에 빠르게 설명만 하겠습니다.

우선 이에 대한 이야기는 2년전에 올렸었는데요.

이에 대해서 좀더 보완되고 해석적인 방법을 통해 설명드리려고 왔습니다.

https://mawile.tistory.com/183

제곱, 제곱근 구현하기

 

O(1) 거듭제곱 구현 알고리즘

우선 거듭제곱의 구현은 자연로그의 성질을 이용해서 O(1)로 구현이 가능합니다.

 

 

다음 a의 b제곱인 수 k가 있다고 가정해봅시다.

우리가 결과적으로 얻기 원하는 수는 k입니다.

따라서 무조건 k에 관하여 풀어야 합니다.

 

우선 자연로그 성질중에 자연로그와 자연상수를 양변에 곱하면 등식이 되는 성질이 있습니다.

이 성질을 이용해서 다음과 같은 식으로 정리해줍니다.

log의 성질중 하나가 제곱인 수를 밖으로 꺼내올수있었습니다.

따라서 다음과 같은식으로 정리가 가능합니다.

이를 C++코드로 구현하면 다음과 같이 구현할수 있습니다.

#include <iostream>
#include <cmath>

double mypow(double a, double b)
{
	return std::exp(b * std::log(a));
}

int main()
{
	std::cout << mypow(5.0, 3.0) << std::endl;
}

 

바빌로니아 법 알고리즘의 해석

다음은 제곱근의 근사값을 얻을 수 있는 알고리즘인 바빌로니아 법 알고리즘에 관하여 알아보겠습니다.

우선 바빌로니아 법 알고리즘은 Newton-Raphson법을 통해 값을 도출해낼 수 있습니다.

 

우선 우리가 구해야 할 수는 아래와 같이 어떠한 수 S를 제곱근한 값인 x를 구하는것입니다.

예를들어서 S가 2라면 루트 2 이므로 x는 1.414...가 된다는것을 알수있으실겁니다.

 

그다음 우리가 알아봐야 할 식은 뉴턴-랩슨법의 전개식입니다.

아래 식은 그래프를 보시면 아시겠지만,

x0에서의 y값 fx0을 가진다면 다음 x1의 값은 x0에서의 기울기분의 fx0값을 뺀 식이 됩니다.

https://www.geeksforgeeks.org/newton-raphson-method/

 

그러면 우리가 구해야할 식을 방정식으로 고친후,

 

뉴턴-랩슨 전개식에 대입하면 다음과 같이 정리가 가능합니다.

 

따라서 이를 C++ 코드로 구현하면 다음과 같이 만들 수 있습니다.

#include <iostream>

double mysqrt(double S, double epsilon = 10)
{
	double x = 1;
	
	for(int i = 0; i < epsilon; ++i)
	{
		x = 0.5 * (x + (S / x));
	}
	
	return x;
}

int main()
{
	std::cout << mysqrt(2.0) << std::endl;
}

 

@ 추가해석

여기서 추가로 일반적인 제곱근이 아닌 n제곱근을 구하려면 어떻게 해야하는지 궁금해서 규칙을 찾아봤습니다.

규칙이 보이시나요?

아래와 같은 규칙을 가집니다.

당연히 제곱근의 성질에 의해 S >= 0여야 하며, 분수성질때문에 p > 0 여야합니다.

 

C++코드로 구현하면 다음처럼 짤수 있겠습니다.

[최적화 팁] 

mysqrt식의 p의 역수값을 변수에 저장한다음

반복문에서 매번 나누지말고 저장해놓은값을 갔다쓰면 조금더 빠를것입니다.

 

#include <iostream>
#include <cmath>

double mypow(double a, double b)
{
	return std::exp(b * std::log(a));
}

double mysqrt(double S, double p, double epsilon = 15)
{
	double x = 1;
	const double p_1 = p - 1;
	
	for(int i = 0; i < epsilon; ++i)
	{
		x = (1 / p) * (p_1 * x + (S / mypow(x, p_1)));
	}
	
	return x;
}

int main()
{
	std::cout << mysqrt(49.0, 2.0) << std::endl;
}

 

 

마무리

다른공부하러가봐야해서 후다닥썼는데 오랜만에 쓰기도했고, 뭔가 글실력이 줄어든것같아서 아쉽지만 오늘은 여기에서 마무리하겠습니다.

다음 포스팅은 언제가 될지 모르겠네요.

 

음.. 내년2월달되면 본격적으로 프로그래밍쪽 재활을 시작할텐데, 제가 생각하기에 컴퓨터그래픽스는 좀 더 깔끔하게 지식을 다듬고 글을 쓸예정이고, 아마 수학이랑 자연과학쪽분야로 글을 쓰는시도가 생기지 않을까 예상해봅니다.