[작성자:] snowall

  • 푸리에 변환으로 곱셈 계산하기


    http://en.wikipedia.org/wiki/Multiplication_algorithm#Fourier_transform_methods

    이런게 있다.

    번역을 해 보자.

    Strassen의 아이디어다. (1968년)

    가장 큰 정수 w를 고른다. w는 오버플로우는 내지 않도록 한다.

    곱해야 할 두 수를, w비트인 m개의 그룹으로 나눈다.




    그럼, 이제 이게 된다.



    m보다 큰 i, j에 대해서 a와 b를 0으로 놓고, c는 a와 b의 convolution으로 놓는다.

    convolution 정리에 따르면,

    1.a와 b에 대해서 빠른 푸리에 변환을 한다.

    2.두 계산 결과를 각각의 항 별로 곱한다

    3.푸리에 역 변환을 계산한다

    4.2^w보다 큰 c_k를 c_{k+1}에 더한다

    이 계산 방법은 2007년 Furer에 의해 조금 개선되어서, 현재까지는 가장 빠른 곱셈법으로 알려져 있다.

    Strassen의 원래 아이디어의 계산 복잡도는 대략 $\theta(n*ln(n)*ln(ln(n)))$정도이고, Furer 방법의 계산 복잡도는 $\theta(n*ln(n)*2^{(\theta(ln(n))})$ 정도라고 한다.

    봐도 모르겠다…

    나중에 논문 찾아서 읽어봐야지.

    mult.pdf에 액세스하려면 클릭하세요.



    Furer의 논문이다. Strassen 알고리즘의 논문은 독일어 저널에 독일어 제목으로 실려 있는 것 같아서…보고싶지 않다…



  • 실험실이란…

    7월에 있을 실험을 준비하느라 요즘은 계속 하루종일 실험실 안에서 일한다.

    일하는건 뭐 할만한데…

    유일한 고충이라면, 습진…

    하루종일 고무장갑을 끼고 일한다. 내 손이 아니라 장비의 보호를 위해서 -_-;

    워낙에 고가의 장비라 지문도 묻으면 안된다. 사실은 입김도 묻으면 안되기 때문에 마스크도 써야 하지만 그건 나름 집시법 위반이므로…

    하루종일 고무장갑을 끼고 일하다 보니 손에 습진이 생기고 있다. 아마 난 결혼해서 설겆이 전담을 하더라도 한겨울에 온수가 안나오더라도 고무장갑은 안 낄 것 같다.

  • 오픈웹 항소심 선고 판결문

    스캔된 PDF를 옮겼다.

    14번째 페이지부터는 손가락이 저리네…

    해피해킹도 너무 오래쓰면 아프구나.

  • 들어라

    광장에 다시 사람들이 모이고 있다. 왜 모일까? 자신의 의견을 말하기 위해서다. 그게 불법일지도 모른다. 하지만 사람들이 많이 모였다. 누가 선동했을지도 모른다. 하지만 사람들이 너무 많이 모였다. 그 사람들이 모두 한 목소리를 내고 있다.

    들으라는 거다.

    공무원은 국민의 머슴이라던 자가 국민을 탄압한다. 불법을 저지른 것이 나쁘니까 듣지 않아도 된다는 것인가. 하지만 대한민국 헌법엔 집회, 결사, 언론의 자유가 보장되어 있다. 하위법이 헌법을 이길수는 없다. “공익”이라는 것을 위해서 어느정도는 자유를 제한할 수 있을 것이다. 하지만 이 경우의 “공익”이란 자유를 제한하지 않아야 보장된다.

    사람들이 많이 모였다.

    왜 모였는지는 생각 안하나? 정치라는 것이 국민을 행복하게 하는 것이라 하자. 광장에 모인 10만명은 불법을 저지른 사람들로 간주해서 국민으로 생각 안하나? 행복하지 않아도 되나? 아니면, 그들이 그토록 반대하는 각종 정책들이, 광장에 모인 사람들이 몰라서 그렇지 사실은 그들을 행복하게 할 수 있을 거라고 철썩같이 믿고 있는 것인가? 그렇다 치자. 그게 정말 좋은 정책이고, 광장에 모인 사람들이 전부 바보라 하자. 그렇다 하더라도 반대하는 이유가 있을 것이고, 그 이유를 설득해서 그들을 찬성하는 사람들로 만든 다음에 일을 진행하는 것이 정말 머슴의 태도라 할 수 있을 것이다. 주인이 시키지도 않은 일을 시켰다고 우기면서 추진하는 머슴이야말로 바보다.

    “설득”이라는 것을 모르면 배워라. “소통”이라는 것을 모르면 배워라.

    그래. 많이 양보해서, 모든것이 정부의 뜻대로 되었을 때 국민들이 행복할 수 있다고 치자. 그것은 국민이 원하는 행복일까? 주가지수가 5천을 달리고, 운하 위에서 유람을 즐기며, 국민소득이 4만달러가 넘어간다면, 그게 국민이 그토록 바라는 행복일까?

    사람들이 원하는 것은 지극히 단순하다. 저기 위에서 통치하는 위정자들께서 보기에 굉장히 계몽이 필요하고 잘못 배우고 세뇌당한 것 같아 보이는 일반 대중들이 바라는 것은 오직 하나. 작은 집 한채에서, 가족들과 함께, 배부르게 밥 먹으면서 사는 것이다. 그 행복을 바라는 것이 못배워서, 잘못배워서, 세뇌당해서 그런건가? 그 일반 대중은 이제 성인이고, 박정희, 전두환, 노태우, 김영삼, 이런 사람들이 대통령 할 적에 학교를 다녔다. 그 학교에서 잘못 배웠나? 그 학교에서 세뇌당했나? 아니면, 전부 학교 교육과 담 쌓고 살았기 때문에 그런 행복을 누리지 못하는 건가? 근데, 학교에서 잘못 배웠든 학교 교육과 담 쌓았든 그건 정부 책임 아닌가? 아니면, 학교에서 잘 배웠다고 한다면 그런식으로 행복하지 않은건 또한 정부 책임 아닌가?

    부동산, 집값 올라가고 있지요…

    실업률 올라가고 있지요…

    최저임금 깎이고 있지요…

    물가 인상되고 있지요…특히 MB지수라 불리우는 생필품들…

    교육비 인상되고 있지요…

    정리해고도 가속화 되고 있지요…

    비정규직 늘어나지요…

    이중에 아니라고 말할 수 있는게 있다면 말해줘라…

    이중에 일반 대중들이 말하는 그 행복에 도움이 되는게 있다면 말해줘라…

    이 모든게 바로 지난번 대통령이 잘못해서 그 결과를 지금의 대통령이 뒤집어 쓰고 있는 것이라 하자.(많이 양보했다.) 1년 반이나 지났는데 여전히 그모양이면 아마추어도 아닌 경제 전문가 치고는 초라한 성적이다. 임기를 끝까지 채운다 하더라도 그다지 희망이 없다고 생각한다.

    불법집회가 민주주의를 왜곡하는가?

    글쎄. 이만하면 꽤 괜찮은 민주주의 시민의식이라는 생각이 든다.

    설마. 그대는 아마추어인가?

    한강의 기적은 괜히 나온 기적이 아니다. 97년도의 IMF를 최단시간에 빠져나온 것도 괜히 나온 기록이 아니다. 황영조, 박세리, 박지성, 김연아, 박태환, 그 외에 잘 기억나지 않는 수많은 사람들이 세계 1등을 하고 있는 것이 괜히 하는게 아니다. 그런데 그건 사실 기적이다. 아마 국가 지원을 제대로 받기 시작한건 세계 1등을 하고 나서부터일 것이다. 세계 1등이 될 싹들을 지원하는게 아니라, 알아서 잘 큰 다음에 세계 1등을 하면 그때부터 생색내기 시작한다. 언제까지나 그런 행운만을 기대할 것인가.

    내가 매인몸만 아니면 매일 광장으로 나갔을 것이다.

  • 윈도우즈 업데이트

    오늘 윈도우즈에서 13개나 업데이트를 했다.

    근데, 방금 생각난 건데. 윈도우즈 업데이트는 UAC의 적용을 받지 않는다. 즉, 보안 구멍이라는 뜻.

    왜 이런데 구멍이 있지?

  • 운명

    친구가 나에게 “만약 애인이 있는데, 다른 사람이 자신의 운명적인 만남이라는 느낌이 든다면 어떤 선택을 할거냐?”라고 물어보았다.

    그런 고민이라면 애인이 생긴 다음에 하는게 원칙이지만…

    난 운명이나 신, 또는 유전자에 의한 필연적인 결과라든가 하는것을 신경쓰지 않는다.

    미래가 정해져 있다면 내가 어떤식으로 선택하든 그것은 “정해진 결과”이다. 즉, 나는 내 맘대로 선택했지만 그것은 이미 정해진 결과였다는 것이다.

    미래가 정해져있지 않다면 내가 무언가를 선택하였다면 그건 “내가 만들어낸 결과”이다.

    나는 내 맘대로 선택했지만 그것을 부르는 이름이 달라질 뿐이다. 본질은 결국 내 맘대로 선택했다는 것 뿐.

    그런 고민은 역시 애인이 생긴 다음에…

  • Snakes on a plane

    케이블TV에서 하기에 봤다.

    누군가 비행기에 뱀을 실었다.

    사람들 많이 죽는 테러+재난 영화.

    막판에 반전인줄 알았던 장면이 반전이 아니라는 반전이 있음.

  • 기사 감상하기


    http://www.asiae.co.kr/uhtml/read.php?idxno=2009060908121874612

    기사 본문 중 인상깊은 대목

    물리학과 여학생 로지 배티(20)
  • 파이어폭스와 인터넷 익스플로러의 차이

    파이어폭스는 무심코 마우스 휠을 굴리다 보면, 마우스 커서가 플래시 위에 있는 경우에는 휠이 작동하지 않는다.

    물론 인터넷 익스플로러는 된다. 왜그럴까?

    실험을 하나 해 보자.

    스크롤 바가 생기는 파이어폭스 창 2개를 띄워둔다. 하나는 내가 포커싱을 해 두고, 다른 하나는 그냥 그 내용이 보이도록 해 둔다. 그리고, 내가 포커싱 하지 않은 파이어폭스 창 위에서 휠을 굴려보자. 아마 그 창은 스크롤이 될 것이다.

    이것은, 클릭하지 않아도 마우스 커서가 위에 있기만 하면 해당 창으로 마우스 제어를 넘겨주기 때문이다. 물론 이것은 파이어폭스끼리만 되며, 다른 종류의 창에서는 되지 않는다.

    플래시는 다른 종류의 창으로 인식하기 때문에, 휠을 굴릴 때 자동으로 제어가 넘어가서 플래시를 스크롤하려고 하는 것이며, 플래시에는 스크롤이 없기 때문에 휠이 작동하지 않는 것처럼 보이는 것이다.

    이런 기능은 리눅스 데스크탑에서는 대부분 된다. 하지만 윈도우에서는 안된다. (파이어폭스처럼 자체적으로 지원하지 않는 한…)

    그래서 난 파이어폭스가 더 좋다. 밑에 있는 창을 스크롤하기 위하여 굳이 클릭할 필요가 없기 때문이다.

  • 공감

    2008년 2월 6일. 휴대폰 메모.

    난 너의 행동을 이해할 수가 없어

    그럼 넌 자신의 행동은 스스로 이해할 수 있다는 거야?

    인간은 자신의 행동조차도 스스로 이해하지 못해

    나는 할 수 있어

    거짓말이야, 그건 착각에 불과해. 자기 자신을 이해한다면 자신을 속여가면서까지 살아야 하는 걸까?

    자신을 이해하는 것은 타인을 이해하는 것 만큼이나 어려운 일이야. 대체 인간을 이해한다는 것은 무슨뜻일까?

    이해한다는 것은 그사람의 실존을 부정하지 않는다는 거라고 생각해

    하지만 이해하지 못했다고 실존을 부정하는건 아니잖아?

    설명이 부족했군. 만약 내가 어떤 인간의 행동을 이해되지 않는다고 하면 그 사람의 행동은 내게 아무런 의미가 없겠지. 그것은 그 사람의 존재 중에서 적어도 그 행동에 관련된 부분은 내게 존재하지 않는거야. 그것이 실존이지. 그렇지만 그 행동은 그 행위자에게는 의미가 있었잖아?

    문제는, 이해하는 행위의 주체는 나라는 점이지. 내가 이해하지 못했는데 어째서 그의 시각으로 바라봐야 하지?

    그냥 넘어갈 수는 없는거야?

    그러기엔 타인을 이해하지 못한 경우에 생길 수 있는 위험이 큰데

    그렇게 이해 못한다고 계속 걸고 넘어지다간 언젠가 인간관계에서 실패할 것 같은데?