나의 큰 O는 log x야

가끔씩 정수의 제곱근을 구해야할 경우가 가끔씩 있는데, 이때 가장 편한 해결책은 float로 캐스팅해서 sqrt()함수에 넣은뒤 다시 int로 캐스팅하는 것입니다. 요즘 CPU들은 워낙 좋아서 부동소수점 제곱근 연산은 뚝딱 해치우니 속도 걱정은 할 필요가 없지요. 다만... 부동소수점 연산이 잘 지원안되는 환경에서 코딩을 하는 경우에는 정수 제곱근을 구하기위해 선뜻 sqrt함수를 쓰기가 꺼려집니다. 그래서 간단한 연산을 통해 정수 제곱근을 구해내는 함수를 구현해보도록 하겠습니다. int isqrt(int n) { if(n = 0;++i) { n -= 2*i + 1; } return i-1; } 정수 제곱근..

프로그래밍/테크닉 2012. 10. 11. 03:10

우리가 프로그래밍을 하면서 자주 사용하는 여러 수학 함수들이 있다. 할일 없는 사람들은 이 함수들이 어떻게 작동하는지 정말 궁금해할지도 모른다. (물론 나도 그런 할 일 없는사람이다.) 한 번 내가 알고 있는 것들을 글로 써보며 생각을 정리해보고자 한다. 수학함수를 구현할때 가장 중요한 점은 정밀도와 속도이다. 늘상 있는 일이지만 프로그래머는 정확성과 속도 사이를 잘 조율해야한다. 필요이상의 정밀도는 시간 낭비일뿐이다. 먼저 수학함수 중에서 가장 인기가 높은 제곱근 함수 (sqrt함수) 거리 구할때를 비롯하여 안 쓰이는 곳이 없는 인기 좋은 함수이다. 한번 float sqrt(float x)를 구현해보자. 부동소수점 데이터는 꼴로 표현된다. (음수일 경우와 0일 경우는 무시했다.) 여기서 두 가지 경우로..

프로그래밍/테크닉 2008. 11. 26. 00:45