C++과 테일러 급수로 sin(x), cos(x), e^x 값 계산해보기
이번 글을 통해 배워갈 내용
- 팩토리얼을 C++로 구현
- 승수를 C++로 구현
- 테일러 급수를 C++로 구현
- sin(x), cos(x) 그리고 e^x 를 CPP로 구현
- horner의 법칙으로 O(n) 복잡도로 구해보기
1.팩토리얼을 C++로 구하기
팩토리얼은 다들 알고 계시듯
5! = 5 * 4 * 3 * 2 * 1 = 120 입니다.
따라서 다음과 같이 재귀적으로 구현 했습니다.
int FnFactorial(int n)
{
if (n == 0)
{
return 1;
}
return FnFactorial(n - 1) *n;
}2.Power를 C++로 구하기
승수(Power) 도 다음과 같습니다
2^3 = 8, 5^3 = 125
따라서 다음과 같이 재귀적으로 쉽게 구현이 가능합니다.
int FnPower(int m, int n)
{
if (n == 0)
{
return 1;
}
if (n % 2 == 0)
{
return FnPower(m * m, n / 2);
}
return m * FnPower(m * m, (n - 1) / 2);
}
3. 테일러 급수 설명 및 C++ 응용해보기
테일러 급수(Taylor Series)는 매클로우린 급수(Maclaurin series)라고도 불리며
미적분학을 이용해서 근사치를 구하는데 매우 유용하게 사용됩니다.
재귀적으로 일정한 패턴이 있기 때문에 케이스 별로 쉽게 C++로 구현 하였습니다.
몇가지 케이스들을 설명하면서 재귀적으로 표현해보겠습니다.
sin(x)
sin(x) 의 경우
x - (x^3)/3! + (x^5)/5! ... 으로 패턴이 진행됩니다.
따라서 아래와 같이 구현하였습니다.
#include <iostream>
using namespace std;
# define M_PIl 3.141592653589793238462643383279502884L
double FnFactorial(int n)
{
if (n == 0)
{
return 1;
}
return FnFactorial(n - 1) *n;
}
double FnPower(int m, int n)
{
if (n == 0)
{
return 1;
}
if (n % 2 == 0)
{
return FnPower(m * m, n / 2);
}
return m * FnPower(m * m, (n - 1) / 2);
}
double FnFindApproxSinX(double x, int n)
{
if(n == 0)
{
return x;
}
double tempVal = FnPower(-1, n) * FnPower(x, (1 + (2*n))) / FnFactorial(1 + (2*n));
return (FnFindApproxSinX(x, (n-1)) + tempVal);
}
double Sin(double x)
{
FnFindApproxSinX(x, 15);
}
int main()
{
cout<<Sin(1) << endl;
return 0;
}
정확도는 FnFindApproxSinX(x, 15);에 15라 써진곳을 크게 하면 더 크게 올라갑니다.
cos(x)
cos(x) 도 C++을 이용해 테일러 급수로 근사값을 구했으며 방법은 위와 동일합니다
double FnFindApproxCosX(double x, int n)
{
if(n == 0)
{
return 1;
}
double tempVal = FnPower(-1, n) * FnPower(x, (2 * n)) / FnFactorial(2 * n);
return (FnFindApproxCosX(x, (n-1)) + tempVal);
}
double Cos(double x)
{
FnFindApproxCosX(x, 20);
}e^x
e^x 도 C++을 이용해 테일러 급수로 근사값을 구했으며 방법은 위와 동일합니다
double FnFindApproxE(double x, int n)
{
if(n == 0)
{
return 1;
}
double tempVal = FnPower(x, n) / FnFactorial(n);
return (FnFindApproxE(x, (n-1)) + tempVal);
}
double e(double x)
{
FnFindApproxE(x, 20);
}
전체 코드
#include <iostream>
using namespace std;
# define M_PIl 3.141592653589793238462643383279502884L
double FnFactorial(int n)
{
if (n == 0)
{
return 1;
}
return FnFactorial(n - 1) *n;
}
double FnPower(int m, int n)
{
if (n == 0)
{
return 1;
}
if (n % 2 == 0)
{
return FnPower(m * m, n / 2);
}
return m * FnPower(m * m, (n - 1) / 2);
}
///////////////////////////
double FnFindApproxSinX(double x, int n)
{
if(n == 0)
{
return x;
}
double tempVal = FnPower(-1, n) * FnPower(x, (1 + (2*n))) / FnFactorial(1 + (2*n));
return (FnFindApproxSinX(x, (n-1)) + tempVal);
}
double Sin(double x)
{
FnFindApproxSinX(x, 15);
}
///////////////////////////
double FnFindApproxCosX(double x, int n)
{
if(n == 0)
{
return 1;
}
double tempVal = FnPower(-1, n) * FnPower(x, (2 * n)) / FnFactorial(2 * n);
return (FnFindApproxCosX(x, (n-1)) + tempVal);
}
double Cos(double x)
{
FnFindApproxCosX(x, 20);
}
///////////////////////////
double FnFindApproxE(double x, int n)
{
if(n == 0)
{
return 1;
}
double tempVal = FnPower(x, n) / FnFactorial(n);
return (FnFindApproxE(x, (n-1)) + tempVal);
}
double e(double x)
{
FnFindApproxE(x, 20);
}
///////////
int main()
{
cout<<Sin(1) << endl; // 0.841471
cout<<Cos(3) << endl; // -0.989992
cout<<e(3) << endl; // 20.0855
return 0;
}
결론
테일러 함수로 구해보았지만
e를 구하는 함수 외에 나머지 삼각 함수를 구하는 함수들은 double의 데이터 크기 리밋 때문인지 몰라도 생각보다 정확하지 않아서 아쉬웠습니다.
복잡도 계산을 해봤는데
약 O(n^2) 정도 됩니다.
어떻게 해결해볼 방안이 없나 검색을 하던 도중
horner의 법칙을 알게 되었습니다(하단 링크 참조)
이 법칙을 이용해 다시 계산해보겠습니다.
sin(x)
double FnFindApproxSinX(double x, int n, int m)
{
double tempVal = (x*x)/((m * 2 + 1) * (m * 2));
if(n == 1)
{
return tempVal;
}
return (1 - tempVal * (FnFindApproxSinX(x, (n-1), (m+1))));
}
double Sin(double x)
{
x * FnFindApproxSinX(x, 15, 1);
}sin(x)를 이제 O(n)으로 구할수 있습니다.
cos(x)
double FnFindApproxCosX(double x, int n, int m)
{
double tempVal = (x*x)/((m * 2) * (m * 2 -1));
if(n == 1)
{
return tempVal;
}
return (1 - tempVal * (FnFindApproxCosX(x, (n-1), (m+1))));
}
double Cos(double x)
{
FnFindApproxCosX(x, 15, 1);
}cos(x)를 이제 O(n)으로 구할수 있습니다.
e^(x)
double FnFindApproxE(double x, int n, int m)
{
double tempVal = (x)/(m);
if(n == 1)
{
return tempVal;
}
return (1 + tempVal * (FnFindApproxE(x, (n-1), (m+1))));
}
double e(double x)
{
FnFindApproxE(x, 20, 1);
}e^x 를 이제 O(n)으로 구할수 있습니다.
전체 코드는 다음과 같습니다
#include <iostream>
using namespace std;
# define M_PIl 3.141592653589793238462643383279502884L
double FnFactorial(int n)
{
if (n == 0)
{
return 1;
}
return FnFactorial(n - 1) *n;
}
double FnPower(int m, int n)
{
if (n == 0)
{
return 1;
}
if (n % 2 == 0)
{
return FnPower(m * m, n / 2);
}
return m * FnPower(m * m, (n - 1) / 2);
}
///////////////////////////
double FnFindApproxSinX(double x, int n, int m)
{
double tempVal = (x*x)/((m * 2 + 1) * (m * 2));
if(n == 1)
{
return tempVal;
}
return (1 - tempVal * (FnFindApproxSinX(x, (n-1), (m+1))));
}
double Sin(double x)
{
x * FnFindApproxSinX(x, 15, 1);
}
///////////////////////////
double FnFindApproxCosX(double x, int n, int m)
{
double tempVal = (x*x)/((m * 2) * (m * 2 -1));
if(n == 1)
{
return tempVal;
}
return (1 - tempVal * (FnFindApproxCosX(x, (n-1), (m+1))));
}
double Cos(double x)
{
FnFindApproxCosX(x, 15, 1);
}
///////////////////////////
double FnFindApproxE(double x, int n, int m)
{
double tempVal = (x)/(m);
if(n == 1)
{
return tempVal;
}
return (1 + tempVal * (FnFindApproxE(x, (n-1), (m+1))));
}
double e(double x)
{
FnFindApproxE(x, 20, 1);
}
///////////
int main()
{
cout<<Sin(1) << endl; // 0.841471
cout<<Cos(3) << endl; // -0.989992
cout<<e(3) << endl; // 20.0855
return 0;
}
시간복잡도는 줄였지만 삼각함수의 경우 값이 커지면 오버플로우가 납니다
이는 조금 생각해봐야 할 문제인것 같습니다.
뭔가 생각과 아이디어를 얻어 가셨기를 바라며
오늘도 즐거운 코딩하시길 바랍니다 ~ :)
참조 및 인용
https://stackoverflow.com/questions/10168176/horners-rule-c-c-using-recursion
https://stackoverflow.com/questions/22416710/in-c-finding-sinx-value-with-taylors-series
https://en.wikipedia.org/wiki/Taylor_series
C++ Primer