BiscuitWiki: SQRT

?Joinc에서 보다가, 개조해보기로 맘먹었음

원문 #

#include <stdio.h> 
#include <unistd.h> 
#include <math.h> 

float mysqrt(int); 
float guess(float *, int); 
void sqrt_iter(float, int); 

int main(int argc, char **argv) 
{ 
    mysqrt(atoi(argv[1])); 
    printf("%f\n",sqrt(atoi(argv[1]))); 
} 

float mysqrt(int inputnum) 
{ 
    sqrt_iter (1, inputnum); 
} 

void sqrt_iter(float fguess, int inputnum) 
{ 
    float value; 
    value = guess(&fguess, inputnum); 
//    printf("return %.8f\n", value); 
} 

float guess(float *fguess, int inputnum) 
{ 
    float re_fguess; 
    re_fguess = ((inputnum/(*fguess))+*fguess)/2; 
    if (re_fguess != *fguess) 
    { 
//        printf("%.8f %.8f\n", re_fguess, fguess); 
        return guess(&re_fguess, inputnum); 
    } 
    return re_fguess; 
}

생각들 #

재귀호출을 쓰지 않고, 루프로 해결한다.

코딩 #

float biscuit_sqrt(double a)
{
    float guess = 1, re_guess = (a/2 + 2)/2;

    while(re_guess != guess){
        guess   = re_guess;
        re_guess = ((a/guess) + guess ) / 2;
    }

    return re_guess;
}

Taylor 전개 #

f(x_i+1) = f(x_i) + f'(x_i)(x_i+1 - x_i) + f''(x_i)(x_i+1 - x_i)^2 / 2! + ....
정리하면,
x_i+1 = x_i - f(x_i) / f'(x_i)

즉,
x2 = x1 - f(x1) / f'(x1)
x3 = x2 - f(x2) / f'(x2)
...

적용하기 위해, 문제를 다시 살펴보면,

x = 루트2 ; 
양변에 제곱을 하면
x^2 = 2; 

정리하면,
x^2 - 2 = 0;

미분하면,
f'(x) = 2x;

즉, f(x) = x^2 - 2; f'(x) = 2x 를 얻는다. 초기값 x1 을 1.5라 하면,

x2 = x1 - f(x1)/f'(x1)
   = 1.5 -  (1.5^2 - 2) / 3
   = 1.416667

x3 = x2 - f(x2)/f'(x2)
   = 1.414216

...

계산을 계속 할수록 점점 값이 정확해져 간다. 만약 x = 루트3 의 경우라면,

x = 루트3 ; 
양변에 제곱을 하면
x^2 = 3; 

정리하면,
x^2 - 3 = 0;

미분하면,
f'(x) = 2x;

즉, 
f(x) = x^2 - 3; (2만 3으로 바뀌었다!)
f'(x) = 2x; (변함없다!)

일반화하면,

f(x) = x^2 - N;
f'(x) = 2x;

Taylor 전개 코딩 #

float sqrt_taylor(float a)
{
    float guess = 0, x = a/2; // 초기값

    while(guess != x){ 
        guess = x;
        x = x - (x*x - a) / (x*2);
    }
    return x;
}

고찰 #

원본처럼 재귀호출로 구하는 경우, 새 함수로 구하는 경우, 표준함수 math.h의 sqrt를 이용하는 경우를 비교해 보았다. 각각 1만번 수행, 시간단위는 us

구하는값	표준함수 sqrt	재귀호출 mysqrt	비스킷방법sqrt	테일러전개 sqrt
2	1978	5831	5329	6013
7	1981	6938	5355	6535
2002	1980	11854	10246	10829