{"id":8547,"date":"2009-06-11T15:45:00","date_gmt":"2009-06-11T15:45:00","guid":{"rendered":"http:\/\/melotopia.net\/b\/?p=8547"},"modified":"2009-06-11T15:45:00","modified_gmt":"2009-06-11T15:45:00","slug":"%ed%91%b8%eb%a6%ac%ec%97%90-%eb%b3%80%ed%99%98%ec%9c%bc%eb%a1%9c-%ea%b3%b1%ec%85%88-%ea%b3%84%ec%82%b0%ed%95%98%ea%b8%b0","status":"publish","type":"post","link":"http:\/\/melotopia.net\/b\/?p=8547","title":{"rendered":"\ud478\ub9ac\uc5d0 \ubcc0\ud658\uc73c\ub85c \uacf1\uc148 \uacc4\uc0b0\ud558\uae30"},"content":{"rendered":"
\n
\n http:\/\/en.wikipedia.org\/wiki\/Multiplication_algorithm#Fourier_transform_methods
\n <\/a><\/p>\n

\uc774\ub7f0\uac8c \uc788\ub2e4.<\/p>\n

\ubc88\uc5ed\uc744 \ud574 \ubcf4\uc790.
\n
\n Strassen\uc758 \uc544\uc774\ub514\uc5b4\ub2e4. (1968\ub144)
\n
\n \uac00\uc7a5 \ud070 \uc815\uc218 w\ub97c \uace0\ub978\ub2e4. w\ub294 \uc624\ubc84\ud50c\ub85c\uc6b0\ub294 \ub0b4\uc9c0 \uc54a\ub3c4\ub85d \ud55c\ub2e4.
\n
\n \uacf1\ud574\uc57c \ud560 \ub450 \uc218\ub97c, w\ube44\ud2b8\uc778 m\uac1c\uc758 \uadf8\ub8f9\uc73c\ub85c \ub098\ub208\ub2e4.<\/p>\n


\n
\n
\n \uadf8\ub7fc, \uc774\uc81c \uc774\uac8c \ub41c\ub2e4.<\/p>\n


\n
\n m\ubcf4\ub2e4 \ud070 i, j\uc5d0 \ub300\ud574\uc11c a\uc640 b\ub97c 0\uc73c\ub85c \ub193\uace0, c\ub294 a\uc640 b\uc758 convolution\uc73c\ub85c \ub193\ub294\ub2e4.
\n
\n convolution \uc815\ub9ac\uc5d0 \ub530\ub974\uba74,
\n
\n 1.a\uc640 b\uc5d0 \ub300\ud574\uc11c \ube60\ub978 \ud478\ub9ac\uc5d0 \ubcc0\ud658\uc744 \ud55c\ub2e4.
\n
\n 2.\ub450 \uacc4\uc0b0 \uacb0\uacfc\ub97c \uac01\uac01\uc758 \ud56d \ubcc4\ub85c \uacf1\ud55c\ub2e4
\n
\n 3.\ud478\ub9ac\uc5d0 \uc5ed \ubcc0\ud658\uc744 \uacc4\uc0b0\ud55c\ub2e4
\n
\n 4.2^w\ubcf4\ub2e4 \ud070 c_k\ub97c c_{k+1}\uc5d0 \ub354\ud55c\ub2e4<\/p>\n

\uc774 \uacc4\uc0b0 \ubc29\ubc95\uc740 2007\ub144 Furer\uc5d0 \uc758\ud574 \uc870\uae08 \uac1c\uc120\ub418\uc5b4\uc11c, \ud604\uc7ac\uae4c\uc9c0\ub294 \uac00\uc7a5 \ube60\ub978 \uacf1\uc148\ubc95\uc73c\ub85c \uc54c\ub824\uc838 \uc788\ub2e4.
\n
\n Strassen\uc758 \uc6d0\ub798 \uc544\uc774\ub514\uc5b4\uc758 \uacc4\uc0b0 \ubcf5\uc7a1\ub3c4\ub294 \ub300\ub7b5 $\\theta(n*ln(n)*ln(ln(n)))$\uc815\ub3c4\uc774\uace0, Furer \ubc29\ubc95\uc758 \uacc4\uc0b0 \ubcf5\uc7a1\ub3c4\ub294 $\\theta(n*ln(n)*2^{(\\theta(ln(n))})$ \uc815\ub3c4\ub77c\uace0 \ud55c\ub2e4.
\n <\/p>\n

\n

\ubd10\ub3c4 \ubaa8\ub974\uaca0\ub2e4…
\n
\n \ub098\uc911\uc5d0 \ub17c\ubb38 \ucc3e\uc544\uc11c \uc77d\uc5b4\ubd10\uc57c\uc9c0.
\n
\n<\/p>\n

mult.pdf\uc5d0 \uc561\uc138\uc2a4\ud558\ub824\uba74 \ud074\ub9ad\ud558\uc138\uc694.<\/a><\/p>\n

<\/a>
\n
\n Furer\uc758 \ub17c\ubb38\uc774\ub2e4. Strassen \uc54c\uace0\ub9ac\uc998\uc758 \ub17c\ubb38\uc740 \ub3c5\uc77c\uc5b4 \uc800\ub110\uc5d0 \ub3c5\uc77c\uc5b4 \uc81c\ubaa9\uc73c\ub85c \uc2e4\ub824 \uc788\ub294 \uac83 \uac19\uc544\uc11c…\ubcf4\uace0\uc2f6\uc9c0 \uc54a\ub2e4…<\/p>\n<\/div>\n

\n<\/div>\n
\n
\n
\n\"\uc2e0\uace0\"
\n<\/a>\n<\/div>\n<\/div>\n

<\/img>
\n<\/img>
\n<\/img>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

http:\/\/en.wikipedia.org\/wiki\/Multiplication_algorithm#Fourier_transform_methods \uc774\ub7f0\uac8c \uc788\ub2e4. \ubc88\uc5ed\uc744 \ud574 \ubcf4\uc790. Strassen\uc758 \uc544\uc774\ub514\uc5b4\ub2e4. (1968\ub144) \uac00\uc7a5 \ud070 \uc815\uc218 w\ub97c \uace0\ub978\ub2e4. w\ub294 \uc624\ubc84\ud50c\ub85c\uc6b0\ub294 \ub0b4\uc9c0 \uc54a\ub3c4\ub85d \ud55c\ub2e4. \uacf1\ud574\uc57c \ud560 \ub450 \uc218\ub97c, w\ube44\ud2b8\uc778 m\uac1c\uc758 \uadf8\ub8f9\uc73c\ub85c \ub098\ub208\ub2e4. \uadf8\ub7fc, \uc774\uc81c \uc774\uac8c \ub41c\ub2e4. m\ubcf4\ub2e4 \ud070 i, j\uc5d0 \ub300\ud574\uc11c a\uc640 b\ub97c 0\uc73c\ub85c \ub193\uace0, c\ub294 a\uc640 b\uc758 convolution\uc73c\ub85c \ub193\ub294\ub2e4. convolution \uc815\ub9ac\uc5d0 \ub530\ub974\uba74, 1.a\uc640 b\uc5d0 \ub300\ud574\uc11c \ube60\ub978 \ud478\ub9ac\uc5d0 \ubcc0\ud658\uc744 \ud55c\ub2e4. […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_crdt_document":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[2],"tags":[],"class_list":["post-8547","post","type-post","status-publish","format-standard","hentry","category-academic"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p8o6gA-2dR","jetpack-related-posts":[],"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/melotopia.net\/b\/index.php?rest_route=\/wp\/v2\/posts\/8547","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/melotopia.net\/b\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/melotopia.net\/b\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/melotopia.net\/b\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/melotopia.net\/b\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=8547"}],"version-history":[{"count":0,"href":"http:\/\/melotopia.net\/b\/index.php?rest_route=\/wp\/v2\/posts\/8547\/revisions"}],"wp:attachment":[{"href":"http:\/\/melotopia.net\/b\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=8547"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/melotopia.net\/b\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=8547"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/melotopia.net\/b\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=8547"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}