글 읽기 - math.h sqrt 구현부 어디서 보나요? [ sqrt vs 직접구현]

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는 어떻게 구현되어 있을까... 어딜가야 구현부를 볼 수 있는지 아시는분..

알고리즘은 이러하다. 아마 비슷할듯..

#include <iostream>
#include <cstdio>
#include <cstring>
#include <math.h>
using namespace std;


int N;
int dp[100001];

double root(double value)
{
	double x=1;
	for( int i=0; i<10; i++)
	{
		x=(x+(value/x))/2;
	}
	return x;
}

int getLessSquareSumLength(int index)
{
	if( index<1 ) return 0;
	if( index==1 ) return 1;
	if( dp[index] != -1 ) return dp[index];

	int rootIndex = (int)root((double)index);  
	//int rootIndex = (int)sqrt(index);
	int temp=999999999;
	for( int i=rootIndex; i>=1; i--)
	{
		
		temp =min(temp, 1+getLessSquareSumLength(index-(i*i)) );
	}
	return dp[index] = temp;
}


int main()
{
	//freopen("sample.txt","r",stdin);
	memset(dp,-1,sizeof(dp));
	scanf("%d",&N);
	printf("%d",getLessSquareSumLength(N));

	return 0;
}

seico75 4년 전 1

https://www.codeproject.com/Ar...

많은 근사화 방법이 있네요.

glibc 에는 이런 식이네요.

https://github.com/lattera/gli...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

math.h sqrt 구현부 어디서 보나요? [ sqrt vs 직접구현]

artage7 4년 전 1

seico75 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말