나의 큰 O는 log x야

앞서 O(nm) 시간에 수행되는 나눗셈 알고리즘에 대해서 다뤄봤는데요, 이번엔 분할정복(Divide and Conquer)을 사용하여 나눗셈 속도를 끌어올리는 방법에 대해서 알아봅시다. 이 알고리즘은 앞서 소개했던 1998년 [Fast Recursive Division]이라는 논문에 제시된것으로, 4n by 2n 나눗셈과 3n by 2n 나눗셈으로 이뤄져있습니다. 알고리즘에 들어가기에 앞서 표기법을 정리하도록하죠. 위치기수법으로 [a3, a2, a1, a0]는 a3*X^3 + a2*X^2 + a1*X + a0 를 나타낸다고 약속합시다. 즉 10진법으로 [3, 6, 8, 7]이라는 건 3687를 나타낸다는거죠.간편한설명을 위하여 나누는 수 B는 정규화되어있다고 가정했습니다. 알고리즘 I. 4n자리 수 A를..

프로그래밍/Multi precision 2014. 4. 16. 17:23

http://bab2min.tistory.com/227http://bab2min.tistory.com/408 앞서 여러 글에서 나눗셈이 생각보다 복잡한 일이라는 걸 반복해서 언급했었는데요, 그렇다고 해서 빠르게 나눗셈을 계산하는 방법이 없다던가 그런것은 아닙니다. 곱셈을 빠르게 하는것처럼 나눗셈 역시 빠르게 계산하는 알고리즘이 존재합니다. 이 포스팅은 다음 글들을 참조해서 작성되었음을 명시하는 바입니다. * 도널드 크누스, [[컴퓨터 프로그래밍의 예술 - 2. 준수치적 알고리즘]]* Christoph Burnikel Joachim Ziegler, [Fast Recursive Division] 우리가 긴 나눗셈을 할때 제일 처음 하는 것은 몫으로 어떤 숫자가 들어갈지를 적당히 추측해내는것입니다. 뭐 사람은..

프로그래밍/Multi precision 2014. 4. 16. 03:54

저번의 좋아요b에 이어서, 페북앱으로 페북검정시험을 개발해봤습니다. 애초에 JQuery Mobile 사용해서 모바일에서 깔끔하게 돌아가도록 해놨구요, 온라인 상에서 단어 시험 등을 보고 이를 공유할수 있는 앱입니다. (원래는 라틴어 공부용으로 개발했던 Blink Memory이 원조였죠. 이걸 예전에 SimpleWebple 운영했을때 웹으로 올렸었다가, 이번엔 아예 자바로 포팅해서 JSP서버에서 원활하게 돌리게 했습니다.) 아래는 예전에 개발했던 BlinkMemory구요, 이걸 온라인으로 포팅한거죠.2011/12/03 - [프로그래밍] - 단순 암기 도우미 BlinkMemory (Oxford Latin Course 포함) 좋아요b http://bab2minj.cafe24.com/ex페북검정시험 http:/..

프로그래밍 2014. 4. 15. 01:11

카라슈바 알고리즘까지는 쉽게 이해했는데,톰-쿡 알고리즘은 괜히 어려워 보여서 그동안 접근하지 못했는데 사실 알고보면 단순한 거였슴다! 일반적인 곱셈 방법으로는 n자리 수 간의 곱셈을 수행하게 되면 총 n^2번의 곱셈이 필요하게 된다. 당연한 말씀.예를 들어을 곱하고자 한다면 각 자리수마다 한 번씩 곱셈을 해야하니 총 36번의 곱셈을 해야겠지요.. 근데 안드레이 톰과 스테픈 쿡이라는 학자가 발상의 전환을 했어요. (카라슈바마냥ㅋ) 숫자를 다항식으로 보고, 다항식끼리 곱하는거야 (그나마 간단한 톰-3 알고리즘을 중심으로 설명할게요.) 숫자 n과 m을 다항식으로 바꾸기 위해 3조각으로 나누도록하겠습니다. 한 조각의 단위는 100으로 잡으면 되겠네요. 자 이 조각을 계수로 이용해서 다항식을 만들어봅시다. 참 쉽..

프로그래밍/Multi precision 2014. 3. 30. 05:49

페이스북에 뭔가 연동해서 앱 만들겠다는 생각은 작년에 웹시개 과제하면서 조원의 아이디어로 하게 된건데,생각보다 재미난걸 많이 할수 있죠~근 사흘간 여러가지 시도를 해봤는데, 생각보다 페이스북 연동 관련해서 정책이 까다롭더군요.혹시나 연동하는 어플 개발하시는 분들은 참고하시길 바래요. * 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