나의 큰 O는 log x야

수업시간에 연습문제로 던져진 거였는데, 생각보다 흥미로워서 아름답게 짜보려고 끊임없이 시도했다. 최종결과물. def int2roman(num): def to(n, d): if n == 9 : return d[0] + d[2] if n >= 5 : return d[1] + to(n - 5, d) if n == 4 : return d[0] + d[1] if n >= 1 : return d[0] + to(n - 1, d) return '' def i2rd(n, d): if n == 0: return '' return i2rd(n // 10, d[2:]) + to(n % 10, d) digit = 'IVXLCDMF' return i2rd(num, digit) 요즘 함수형 프로그래밍에 딱히 맛들린것도 아닌데, 반..

프로그래밍 2012. 10. 23. 20:57

시험기간이라 그런지 잉여력이 폭발해서 c 템플릿을 이용해서 반복문을 대신해보면 재밌겠다는 생각이 들었다. 상수번 반복하는 데 굳이 for문에 제어변수까지 쓰기 싫어서 ㅋ #include #include template void doLoop(std::function f) { f(); doLoop(f); } template void doLoop(std::function f) { } int main() { doLoop([](){ printf("Yay!\n"); }); return 0; } 아... c 11이 아니라면 좀 곤란함.ㅋ 템플릿은 재밌져!

프로그래밍/테크닉 2012. 10. 22. 20:16

저번 글에서는 간단하게 덧셈과 곱셈을 구현해보았는데요, 이번에는 곱셈을 구현해보고 합니다. 이번에도 곱셈을 처음배우는 아이에게 곱셈을 가르쳐주듯, 컴퓨터에게 차근차근 가르쳐봅시다.a = a_0 . a_1 a_2b = b_0 . b_1 b_2 라고 했을때 이 두 수의 곱셈은 다음과 같이 계산됩니다. 예전에 곱셈공부할때가 새록새록 생각나지요??c = ab라고 하면,c_0 = a_0 b_0c_1 = a_0 b_1 + a_1 b_0c_2 = a_0 b_2 + a_1 b_1 + a_2 b_0c_3 = a_1 b_2 + a_2 b_1c_4 = a_2 b_2가 됩니다. (편의상 각 자리에서 일어나는 받아올림은 생략했습니다... 만 물론 당연히 이것도 계산해주어야겠지요.) n자리 짜리 두 수를 곱하는데는 총 n*n번의..

프로그래밍/Multi precision 2012. 10. 18. 01:24

(짤방은 그냥 재미로...) BigFloat에서 덧셈과 뺄셈을 구현하기 위해서는 초등학교 다닐때의 마음으로 되돌아가서, 컴퓨터에게 받아올림과 받아내림을 알려줘야합니다.ㅋ (p = 2^32) c2 = (a2 + b2)를 p로 나눈 나머지 c1 = (a1 + b1 + 받아올림)을 p로 나눈 나머지 c0 = (a0 + b0 + 받아올림)을 p로 나눈 나머지 이런식으로 계산이 되지요. 다행히도 우리는 구현할때 a_n + b_n을 2^32으로 매번 나눠줄 필요가 없습니다. 32비트 CPU에서는 2^32를 넘어가는 숫자는 자동으로 오버플로우되어 버리기 때문이지요. 그러면 받아올림이 일어났는지는 어떻게 알수 있을까요? 실제로 CPU 어셈블리 상에서는 add연산에서 오버플로우가 발생하면, 캐리플래그(CF)가 세트되어서..

프로그래밍/Multi precision 2012. 10. 16. 01:51

기초적인 BigFloat의 수학적 원리는 다음과 같아요~ 십진법은 위와 같은 규칙으로 표현됩니다. 십진법에서의 덧셈은 각 자리수에 해당하는 숫자들끼리 더해서 받아올림을 함으로써 연산됩니다. 이를 32비트 컴퓨터에서 효율적으로 구현하기 위해서는 10진법보다는진법을 사용하는것이 좋겠지요. 이런 모양으로 실수를 표현할수 있을겁니다. 일단 이번 연재의 궁극적인 목표는 Pi값의 계산이니만큼 정수부분이 무지막지하게 큰 정수를 표현해야할 필요는 없습니다. a, b부분은 쳐내고, 다음과 같은 모양으로 표현하는게 괜찮겠네요. a0은 정수부분을 표현하는 데이터로, a1부터는 소수점 이하를 표현하는 데이터로 활용하면 될것입니다. 자 이제 이걸 바탕으로 우리의 BigFloat자료형이 될 RealReal구조체를 짜봅시다. ty..

프로그래밍/Multi precision 2012. 10. 16. 00:45

오랜만에 프로그래밍 글을 쓰네요~! 예전에 BigInt를 구현해보는 연재를 잠깐했었는데요, 이번에는 BigInt를 실수범위로 확장시킨것이라고 할 수 있는 BigFloat, 즉 메모리 용량이 허용하는 내로 무한한 소수점을 표현할 수 있는 자료형을 구현해보려고 합니다. (이전 연재: 2009/03/29 - [프로그래밍/Multi precision] - BigInteger를 구현해보자 - 1. BigInteger의 개요) BigInt 구현의 최대떡밥이 팩토리알을 계산하는것이라면, BigFloat의 최대떡밥은 Pi를 계산해내는것입니다. 그래서 이번 연재에서는 BigFloat를 구현하고, 여러가지 수치를 연산하는 방법을 탐구해보고, 궁극적으로는 Pi값을 구해내는것을 목표로 하고 있습니다. 예전에는 부동소수점 방식..

프로그래밍/Multi precision 2012. 10. 16. 00:43

고정소수점은 우리가 흔히 사용하는 float나 double과는 달리 소수점 자리가 늘 고정한 채로 실수를 표현하는 방식을 말합니다. 표현범위가 넓지 않아서 자주 쓰이지는 않지만, 정밀도가 그다지 필요없는 경우, 단순한 실수연산을 위해서 사용할수가 있습니다. 대표적인 예로 스타크래프트2 트리거나 게임 데이터에서 사용되는 실수가 고정소수점이라고 판단되는데요, 예를 들어 유닛의 체력과 같은 경우, 그냥 정수형 데이터가 사용될거 같지만, 실제로는 고정소수점 포맷을 사용하는거 같습니다.(제가 개발자가 아니라 정확히는 모르지만... 여러가지 정황을 보고 추측하는 것입니다.) 저그 유닛은 초당 체력이 0.24씩 회복이 되어야하니 정수형 데이터를 쓰기에는 좀 뭐시기하지요. 부동소수점형을 쓰기엔 연산 부하가 많이 걸릴거..

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

가끔씩 정수의 제곱근을 구해야할 경우가 가끔씩 있는데, 이때 가장 편한 해결책은 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