나의 큰 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

초등학생 때 집에 학생백과사전이 열 몇 권 있었다. 이 백과사전이 우리집에 오게 된 경위는 참으로 오묘하고, 나에게 미친 영향 역시 더 오묘하기 때문에 언급하지 않고 넘어갈 수가 없다. 부모님은 뭐 하나 가진것 없이 나셔서 결혼하신거라, 신혼초부터 사실 매우 생활이 빡빡했다고 하셨다. 엎친데 덮친 격으로 내가 초등학교에 입학한 98년은 IMF 직후라 두 집 건너 한 집마다 직장을 잃은 가장들이 보이던 그런 시기였다. 우리 집도 IMF 사태에서 자유로울 순 없어서 줄어든 수입을 메꾸기 위해서 어머니께서는 뭐라도 했어야했다. 그래서 어머니는 집에서 공부방을 운영하셨는데, 처음에는 학생이 별로 없었지만, 옆 동에 살던 친구 한 명의 받아쓰기 성적을 급상승시킴으로써(!) 공부방은 입소문을 타게 됐고, 동네에서 ..

적분史 2014. 4. 12. 23:42

세미나라는 단어가 언젠가부터 많이 사용되기 시작했어요! 언제 무슨 세미나를 하니깐 꼭 참여하라거나, 이번 세미나 주제는 ~라거나 하는식으로요. 근데 정작 세미나의 뜻이 뭐냐고 물어보면 다들 우물쭈물해버리고 맙니다. 그런데 보통 다음의 이미지를 떠올리는건 확실한 듯합니다. * 그냥 스터디는 아니다. 뭔가 스터디보다는 고급스러운 공부방법* 일방적인 강의 형식이 아니라 발표나 토론이 가미된 복합적인 수업 이런 정도의 뉘앙스를 가지고 있기에 (또 스터디라고 하면 싸보이지만 세미나라고 하면 뭔가 있어보여서) 여러 곳에 사용되는것일지도 모릅니다. 사전에 의하면 세미나는 교수의 지도 아래 학생들이 모여 연구 발표나 토론 등을 통하여 하는 공동 연구를 가리킨다고 합니다. 그런데! 이 세미나가 위의 사진에 나오는 못자리..

언어/어원 이야기 2014. 4. 12. 15:03

http://bab2minj.cafe24.com/ex 페북 앱 좋아요b의 버그 및 건의사항을 제보 받아요.원래는 기말과제로 만들었던걸 손봐서 보강해서(어차피 호스팅 결제했으니깐...) 운영하고 있는거라 미흡한 점이 많습니다. 예상처럼 작동하지 않는 경우가 있을 수 있으니 댓글로 버그 제보 부탁드려요.또한 재미난 아이디어 있으신 분들 건의사항도 받습니다~!

잉여 2014. 4. 8. 02:49

초3 남학생의 인생을 바꾼 두 번째 사건이 있었으니 그것은 스타크래프트였다. 98년 발매된 스타크래프트는 대대적인 인기몰이를 하며 한국에 상륙했는데 그 덕에 당시 동네 컴퓨터집에서 산 컴퓨터라면 어딜가나 립버전 스타크래프트가 들어있었다. 다만 문제는 내가 영어를 초3때 간신히 배우기 시작했다는거고(당시 교육과정을 따르면 초3때 처음으로 영어가 주3시간 포함되게 되어있었다.) 스타크래프트라는 게임이 있다는 사실조차도 몰랐다는것이다. 친척이었는지 이웃집 형이었는지는 정확하게 기억이 안나는데 아무튼 어떤 형이 놀러왔었다. 90년대 말, 2000년대 초부터 컴퓨터가 집집마다 보급되면서, 친구나 친한 사람 집에 놀러가면 서로 각자 집에 깔린 게임을 보여주는게 통과의례처럼 되어있었다. 나랑 동생도 당연히 놀러온 형..

적분史 2014. 4. 8. 01:04

안 하다가 하려니깐 생각보다 가물가물한게 많아서 쉽지가 않네요. 그래도 포기하면 아예 다 잊어먹을거같아서 틈 날때마다 공부했던거 복습도 할겸 Latina Vivens에 정리해서 올리고 있습니다. 최근에 한 일은... * 갈리아 전기 번역 도저언!http://latina.bab2min.pe.kr/xe/gallico_board라틴어2였나 3였나 마지막 수업 즈음 교수님께서 시간되면 같이 한번 강독해보자고 갈리아 전기 pdf본을 보내주셨는데... 이놈의 시간이 너무나도 부족해서 못하고 끝난게 그렇게 아쉬울수가 없었죠. 이젠 같이 강독해주실 교수님은 안 계시지만 아쉬움을 달래보고자 도전. * 옥스포트 라틴 코스 해석http://latina.bab2min.pe.kr/xe/oxford1가끔 심심할때마다 심심풀이로 ..

언어/라틴어 2014. 4. 6. 09:01