{"id":403,"date":"2008-11-14T22:46:44","date_gmt":"2008-11-14T20:46:44","guid":{"rendered":"https:\/\/foton.no-ip.com\/BLOG\/?p=403"},"modified":"2010-04-17T00:18:45","modified_gmt":"2010-04-16T22:18:45","slug":"optimal-coding-5-algorithms-mul","status":"publish","type":"post","link":"https:\/\/foton.szikraistvan.hu\/blog\/?p=403","title":{"rendered":"Optimal Coding 5 &#8211; Algorithms &#8211; Mul"},"content":{"rendered":"<p><a href=\"http:\/\/www.fastcodeproject.org\/\">The Fastcode Project<\/a> is mostly about optimizing for architecture. I was looking for similar project, but sadly i couldn&#8217;t find any. Maybe I wasn&#8217;t usign the right phrases in google.<br \/>\nA few days ago I remembered the <a href=\"http:\/\/libtomcrypt.com\/index.old.html\">LibTom<\/a> Library for C I downloaded a while ago.  The LibTomMath is a multiple precision integer library. I was reading the code of mp_mul function. Then I looked up the referenced algorithms and more&#8230;<\/p>\n<p><a href=\"http:\/\/everything2.com\/title\/Comba%2520multiplication\">Comba multiplication<\/a><br \/>\n<a href=\"http:\/\/everything2.com\/title\/Karatsuba%2520multiplication\">Karatsuba multiplication<\/a><br \/>\n<a href=\"http:\/\/everything2.com\/e2node\/Toom-Cook%2520multiplication\">Toom-Cook multiplication<\/a><br \/>\n<a href=\"http:\/\/everything2.com\/title\/Strassen%2520algorithm%2520for%2520polynomial%2520multiplication\">Strassen algorithm for polynomial multiplication<\/a><br \/>\n<a href=\"http:\/\/everything2.com\/title\/multiplication%2520using%2520the%2520fast%2520Fourier%2520Transform\">Multiplication using the Fast Fourier Transform<\/a><br \/>\n<a href=\"http:\/\/www.cse.psu.edu\/~furer\/Papers\/mult.pdf\">Martin F\u00fcrer FFT algorithm<\/a><\/p>\n<p>the time complexity of conventional long multiplication is O(n^2)<br \/>\nKaratsuba Multiplication: O(n^lg2(3)) or O(n^1.585)<br \/>\nToom-Cook 3-way: O(n^1.464)<br \/>\nFFT: O(n log n)<\/p>\n<p>A promising library: <a href=\"http:\/\/gmplib.org\/\">GNU Multiple Precision Arithmetic Library<\/a><\/p>\n<p>And here is some instruction timings for optimizing for architectures I forgot to put up last time: <a href=\"http:\/\/swox.com\/doc\/x86-timing.pdf\">http:\/\/swox.com\/doc\/x86-timing.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>The Fastcode Project is mostly about optimizing for architecture. I was looking for similar project, but sadly i couldn&#8217;t find any. Maybe I wasn&#8217;t usign the right phrases in google. A few days ago I remembered the LibTom Library for &hellip; <a href=\"https:\/\/foton.szikraistvan.hu\/blog\/?p=403\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_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":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[32],"tags":[71,70],"class_list":["post-403","post","type-post","status-publish","format-standard","hentry","category-cooding","tag-develop","tag-programozas"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p3E7AZ-6v","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/foton.szikraistvan.hu\/blog\/index.php?rest_route=\/wp\/v2\/posts\/403","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/foton.szikraistvan.hu\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/foton.szikraistvan.hu\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/foton.szikraistvan.hu\/blog\/index.php?rest_route=\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/foton.szikraistvan.hu\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=403"}],"version-history":[{"count":8,"href":"https:\/\/foton.szikraistvan.hu\/blog\/index.php?rest_route=\/wp\/v2\/posts\/403\/revisions"}],"predecessor-version":[{"id":720,"href":"https:\/\/foton.szikraistvan.hu\/blog\/index.php?rest_route=\/wp\/v2\/posts\/403\/revisions\/720"}],"wp:attachment":[{"href":"https:\/\/foton.szikraistvan.hu\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=403"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/foton.szikraistvan.hu\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=403"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/foton.szikraistvan.hu\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=403"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}