제곱근 Square root : 바빌로니아 법 (The Babylonian Method)

C, C++ 전체 링크

 

바빌로니아 법은 임의의 수의 제곱근에 빠르게 수렴하는 수열을 만들어 근삿값을 구하는 방법이다.

 

이 수열을 계속해서 반복하면 x가 √a가 된다.

 

먼저 PRECISION_COUNT를 5로 정의하고, 바빌로니아 법을 5번 반복해보자.

printf에 .[Number]f로 옵션을 주면 Number의 자릿수만큼 소수점을 출력할 수 있다.

#include <stdio.h>

#define PRECISION_COUNT (5) 

double sqrt(int num)
{
	double x = num / 2.0;

	for (int i = 0; i < PRECISION_COUNT; i++)
	{
		x = (x + (num / x)) / 2; /* xn+1 = (xn + (num / xn)) / 2 */
	}

	return x;
}

int main()
{
	printf("%.15f\n", sqrt(2) * sqrt(2));
	printf("%.15f\n", sqrt(3) * sqrt(3));
	printf("%.15f\n", sqrt(20) * sqrt(20));
	printf("%.15f\n", sqrt(99) * sqrt(99));
	printf("%.15f\n", sqrt(999) * sqrt(999));

	return 0;
}

 

PRECISION_COUNT를 5에서 10으로 늘리면 조금 더 나은 결과가 나온다.

#define PRECISION_COUNT (10) 

 

하지만 무작정 COUNT를 올릴 수는 없으므로,

원하는 정밀도를 정해서 만족할 때 까지 while문을 이용해 반복하는 방법으로 함수를 바꿀 수 있다.

 

return되는 X에 대해

X² - precision < NUMBER < X² + precision 을 만족한다면 반복을 종료한다.

#include <stdio.h>

//#define PRECISION_COUNT (10) 

double sqrt(int num, double precision)
{
	double x = num / 2.0;
	double x2 = x * x;
	double comp_x2 = (double)num;

	while (!(comp_x2 - precision < x2 && x2 < comp_x2 + precision))
	{
		x = (x + (num / x)) / 2;
		x2 = x * x;
	}

	return x;
}

int main()
{
	double precision = 0.00000001;

	printf("2   : %.15f\n", sqrt(2, precision) * sqrt(2, precision));
	printf("3   : %.15f\n", sqrt(3, precision) * sqrt(3, precision));
	printf("20  : %.15f\n", sqrt(20, precision) * sqrt(20, precision));
	printf("99  : %.15f\n", sqrt(99, precision) * sqrt(99, precision));
	printf("999 : %.15f\n", sqrt(999, precision) * sqrt(999, precision));

	return 0;
}

모든 결과가 정밀도에 대해 알맞은 제곱근을 구한 것을 알 수 있다.