1699번 - 제곱수의 합
변태 기질이 발동하여 sqrt를 직접 구현해보려고 했다.
double root(double value){ double x=1; for( int i=0; i<=10; i++) { x=(x+(value/x))/2; } return x;}
바빌로니아 법으로 하면 대충 이렇다. for문을 많이 돌리면 많이 돌릴수록 근사된다.
같은 알고리즘을 sqrt와 바빌로니아 법으로 비교해보자
.
1. sqrt - 36ms
2. 직접 구현에서 for문을 100번 돌림 - 128ms
3. 직접 구현에서 for문을 20번 돌림 - 60ms
4. 직접 구현에서 for문을 11번 돌림 - 52 ms
5. 직접 구현에서 for문을 10번 돌림 - 틀렸습니다.
sqrt는 어떻게 구현되어 있을까... 어딜가야 구현부를 볼 수 있는지 아시는분..
알고리즘은 이러하다. 아마 비슷할듯..
https://www.codeproject.com/Ar...
많은 근사화 방법이 있네요.
glibc 에는 이런 식이네요.
https://github.com/lattera/gli...
댓글을 작성하려면 로그인해야 합니다.
artage7 4년 전 1
변태 기질이 발동하여 sqrt를 직접 구현해보려고 했다.
double root(double value)
{
double x=1;
for( int i=0; i<=10; i++)
{
x=(x+(value/x))/2;
}
return x;
}
바빌로니아 법으로 하면 대충 이렇다. for문을 많이 돌리면 많이 돌릴수록 근사된다.
같은 알고리즘을 sqrt와 바빌로니아 법으로 비교해보자
.
1. sqrt - 36ms
2. 직접 구현에서 for문을 100번 돌림 - 128ms
3. 직접 구현에서 for문을 20번 돌림 - 60ms
4. 직접 구현에서 for문을 11번 돌림 - 52 ms
5. 직접 구현에서 for문을 10번 돌림 - 틀렸습니다.
sqrt는 어떻게 구현되어 있을까... 어딜가야 구현부를 볼 수 있는지 아시는분..
알고리즘은 이러하다. 아마 비슷할듯..