나의 큰 O는 log x야

페이스북에 뭔가 연동해서 앱 만들겠다는 생각은 작년에 웹시개 과제하면서 조원의 아이디어로 하게 된건데,생각보다 재미난걸 많이 할수 있죠~근 사흘간 여러가지 시도를 해봤는데, 생각보다 페이스북 연동 관련해서 정책이 까다롭더군요.혹시나 연동하는 어플 개발하시는 분들은 참고하시길 바래요. * FQL 과다하게 날리면 페이스북은 그 앱을 악성앱으로 판단하고, 그 앱뿐만 아니라 앱 소유자 계정까지 일시정지시켜버립니다. 악성앱이 아니었음에도 이용자가 폭주해서 쿼리가 많을 경우도 차단당할 수 있어요. (이렇게 차단당하는 경우 그 앱은 아예 삭제당합니다.) * 사용자의 허락 없이 무단으로 게시물이나 사진을 올리거나 태그, 댓글 등을 달면 안됩니다. 이게 발견되면, 페이스북에서 그 앱의 publish_stream 권한을 ..

프로그래밍 2014. 3. 23. 04:28

생각해보니, 추상문법트리에서 실제 바이트 코드를 생성하는 부분은 글을 안 썼었군요... 왜 다 끝냈다고 착각하고 있었지... 짬나는대로 정리해서 올리도록 하겠습니다~ㅠㅠ

프로그래밍/PG어 2014. 3. 21. 04:40

곱셈은 앞서(http://bab2min.tistory.com/405)에서 이미 구현했습니다. 다 좋은데 시간복잡도가 O(n^2)이라 숫자가 커지면 커질수록 너무 느려진다는 단점이 있죠. 하지만 이런 문제를 겪을줄 알았는지 이미 일찍이 수학자들이 여러 가지 빠른 곱셈 알고리즘을 발명해 놓았습니다. 여기에서는 곱셈 알고리즘 중 두번째로 구현이 간단한(그 댓가로 뒤에서 두번째로 빠른) 카라슈바 알고리즘(Karatsuba Algorithm)을 구현해보도록 할것입니다. 카라슈바 알고리즘의 개요는 다음과 같습니다. 2자리수 간의 곱을 계산하려면 일반적인 곱셈법으로는 한 자릿수 곱셈이 총 4번이 필요한데, 카라슈바는 한 자릿수 곱셈을 3번만 하고, 덧셈/뺄셈으로 나머지 부분의 결과를 구해내는 아이디어를 떠올립니다. ..

프로그래밍/Multi precision 2014. 3. 11. 23:54

앞서서 곱셈을 구현했으니, 이제 나눗셈을 구현할 차례겠죠?근데 문제는 나눗셈을 구현하는게 생각보다 까다롭다는거지요. 일반적으로 우리가 학교에서 배우는 나눗셈 방법은 장제법(long division)이라고 하는데,이게 얼마나 어려운지는 초등학생들이 더 잘 압니다.http://bab2min.tistory.com/54 자세한 알고리즘에 대한 설명은 위 페이지로 대신합니다.우리가 나눗셈을 할때 나누는 수랑 나눠지는 수 자리를 맞춰서 계산하죠. 자리 맞추기 위해 숫자들을 왼쪽으로 옮기고 오른쪽으로 옮기고 하는데, 2진법에서 이것과 근본적으로 같은 연산이 비트 시프트 연산입니다.다른말로 하면 나머지를 구하는 나눗셈 연산을 위해서는 먼저 시프트 연산을 구현할 필요가 있다는 거지요. void xl_setnan(PXLA..

프로그래밍/Multi precision 2014. 3. 2. 02:34

최근 너무 바빠서 포스팅할 여력이 없었습니다.개발을 아예 관두거나 그런건 아니구요 짬짬히 개발하고 있는데 생각보다 밖으로 드러나보이는 결과물을 없어서 포스팅을 못하고 있었습니다.최근에는 엔진을 최적화하는 작업을 하고 있습니다. 이곳저곳 정보를 수집하다보니 DOD(Data Oriented Design)에 대한 이야기를 듣고, 이녀석이 멀티스레드와 캐시 적중률에 아주 좋더라! 하는 이야기를 듣고 내부 구조를 개선하는데 시간을 보내고 있어요. DOD에 대해서 간단히 설명하자면, 일반적으로는 Object Oriented하게 프로그램을 작성하죠. 직관적이기도 하구요, 많은 프로그래머들이 이렇게 코드를 작성하도록 교육을 받았기 때문이죠. OOP의 유용성에 대해서는 다시 논할 필요는 없을것 같고, 어떤 점에서 한계가..

프로그래밍/포니게임개발 2014. 2. 15. 12:28

▲ FXAA 적용 전 ▲ FXAA 적용 후 ▲ FXAA 적용 전(확대) ▲ FXAA 적용 후(확대) 간단하게 계단현상 방지 부분을 업그레이드하였습니다. FXAA 적용은 상당히 간단하더라구요. http://www.gamedevforever.com/46여기서 나온대로 그대로 적용했습니다.사실 셰이더 손보고 싶은 부분이 많은데 지금 코드가 너무 난장판으로 산으로 가는 중이라 어디서부터 손봐야할지 고민중입니다.

프로그래밍/포니게임개발 2013. 12. 21. 04:19

한동안 과제철에 선거철에 이 일 저 일하느라 블로그를 신경쓰지 못했습니다. 오늘 내용은 JSP를 이용해 페이스북을 연동하는 방법에 대한것입니다. 원래는 학교 과제로 만들게 된 것인데, 생각보다 어렵지도 않고 재미도 있더라구요. 준비물은 다음과 같습니다.* 멀쩡한 톰캣 서버* JSP를 할줄 아는 프로그래머* 페이스북 앱 ID* Facebook4J 앞의 두개는 알아서 준비하시구요, 여기서는 아래꺼에 대해서 설명해드립니다. https://developers.facebook.com/apps여기에 들어가면 페이스북 앱을 만들수가 있습니다. [새 앱 만들기]를 누르면 위와 같은 대화상자가 나오는데, 여기서 앱 이름과 카테고리를 설정하시면 됩니다. 네임스페이스는 필수는 아니니 생략해도 됩니다. 하면 짜잔! 위와 같이..

프로그래밍 2013. 12. 9. 01:04

앞서서 덧셈과 뺄셈을 구현해보았는데요, 이미 둘을 구현했다면 곱셈을 구현하는 것은 생각보다 간단합니다. 알고리즘에 대해서는 다음을 참조하시면 됩니다. 2012/10/18 - [프로그래밍/Multi precision] - BigFloat로 Pi를 구해보자-3. 곱셈 구현 + 10진수로 출력하기 제일 단순한 방법으로 곱셈을 구현하면 n길이인 정수에 대해 O(n^2) 시간에 계산을 완료할 수 있습니다. 더 빠른 알고리즘 구현은 일단 추후로 미루고ㅋ 당연하겠지만 지수부와 정수배열로 표현된 두 수의 곱은 정수배열끼리는 곱하고 지수부는 더하면 됩니다. 부호연산은 자명하니 설명이 필요없구요. 바로 코드를 보시죠. // xl_mul : a와 b의 곱을 구하여 dest에 저장한다 void xl_mul(PXLARGE de..

프로그래밍/Multi precision 2013. 11. 26. 12:05