{"id":1043,"date":"2014-02-02T03:37:32","date_gmt":"2014-02-02T01:37:32","guid":{"rendered":"http:\/\/antoine.wojdyla.fr\/blog\/?p=1043"},"modified":"2015-01-12T07:21:18","modified_gmt":"2015-01-12T05:21:18","slug":"three-algorithms","status":"publish","type":"post","link":"http:\/\/antoine.wojdyla.fr\/blog\/2014\/02\/02\/three-algorithms\/","title":{"rendered":"Three algorithms"},"content":{"rendered":"<p>Here are three algorithms that I found pretty funny, and that make you think, while I was trying to find elegant solutions to some problem I faced.<\/p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter\" src=\"http:\/\/imgs.xkcd.com\/comics\/travelling_salesman_problem.png\" alt=\"\" width=\"512\" height=\"226\" \/><\/p><!--more--><\/p>The first algorithm is the <a href=\"http:\/\/www.uvm.edu\/~kspartal\/Physlets\/Lecturedemo\/LambdaToRGB.html \" onclick=\"_gaq.push(['_trackEvent', 'outbound-article', 'http:\/\/www.uvm.edu\/~kspartal\/Physlets\/Lecturedemo\/LambdaToRGB.html ', 'Bruton algorithm']);\" title=\"Bruton's algorithm\">Bruton algorithm<\/a>, that allows you to convert a wavelength into the RGB space.<br \/>\nThis is where I found that the equivalent color for a He-Ne laser is 255\/66\/0 !<br \/>\nApparently, this algorithm is more or less heuristic, but there&#8217;s the fun with <a href=\"http:\/\/www.fourmilab.ch\/documents\/specrend\/\" onclick=\"_gaq.push(['_trackEvent', 'outbound-article', 'http:\/\/www.fourmilab.ch\/documents\/specrend\/', 'playing with color spaces']);\" title=\"Fourmilab\">playing with color spaces<\/a> !<\/p>The second algorithm is the <a href=\"http:\/\/en.wikipedia.org\/wiki\/Goertzel_algorithm\" onclick=\"_gaq.push(['_trackEvent', 'outbound-article', 'http:\/\/en.wikipedia.org\/wiki\/Goertzel_algorithm', 'Goertzel algorithm']);\" title=\"Goertzel algorithm - Wikipedia\">Goertzel algorithm<\/a>, which is a way to extract a single frequency component from s signal using a discrete time digital filters (this is an online method to detect a tone ! wow !)<\/p>The third algorithm is the <a href=\"http:\/\/en.wikipedia.org\/wiki\/Midpoint_circle_algorithm\" onclick=\"_gaq.push(['_trackEvent', 'outbound-article', 'http:\/\/en.wikipedia.org\/wiki\/Midpoint_circle_algorithm', 'Bresenham&#8217;s circle algorithm']);\" title=\"Midpoint circle algorithm - Wikipedia\">Bresenham&#8217;s circle algorithm<\/a>, that allows you to discretize in the most efficient way a circle on a set of pixels.<\/p>There is an algorithm that I like, because it cannot be implemented but is yet the most efficient way to sort a list (in time O(N) instead of O(Nlog(N)) for the famous Quicksort) : the <a href=\"http:\/\/en.wikipedia.org\/wiki\/Spaghetti_sort\" onclick=\"_gaq.push(['_trackEvent', 'outbound-article', 'http:\/\/en.wikipedia.org\/wiki\/Spaghetti_sort', 'spaghetti sort algorithm']);\" title=\"Spaghetti sort - Wikipedia\">spaghetti sort algorithm<\/a>, that I discovered through <a href=\"http:\/\/www.drgoulu.com\/2008\/11\/22\/tri\/\" onclick=\"_gaq.push(['_trackEvent', 'outbound-article', 'http:\/\/www.drgoulu.com\/2008\/11\/22\/tri\/', 'Dr Goulu&#8217;s']);\" title=\"Spaghetti sort - Dr Goulu\">Dr Goulu&#8217;s<\/a> blog. Would it work with parallel computers ?<\/p>There&#8217;s another algorithm that I don&#8217;t like, it&#8217;s the <a href=\"http:\/\/en.wikipedia.org\/wiki\/Shor%27s_algorithm\" onclick=\"_gaq.push(['_trackEvent', 'outbound-article', 'http:\/\/en.wikipedia.org\/wiki\/Shor%27s_algorithm', 'Shor&#8217;s algorithm']);\" title=\"Shor's algorithm - Wikipedia\">Shor&#8217;s algorithm<\/a> for factorization, since it tries to define the properties of something that doesn&#8217;t yet exist, quantum computers. Interestingly, Google and NASA have <a href=\"http:\/\/pando.com\/2014\/01\/14\/d-wave-quantum-computing-or-quantum-scam\/\" onclick=\"_gaq.push(['_trackEvent', 'outbound-article', 'http:\/\/pando.com\/2014\/01\/14\/d-wave-quantum-computing-or-quantum-scam\/', 'published the results the benchmark']);\" title=\"D-Wave, Google NASA benchmark - Pando daily\">published the results the benchmark<\/a> they&#8217;ve made obntheir D-Wave so called quantum computer. I don&#8217;t know what to think about the results&#8230;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Here are three algorithms that I found pretty funny, and that make you think, while I was trying to find elegant solutions to some problem I faced.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[11,6,5],"tags":[],"class_list":["post-1043","post","type-post","status-publish","format-standard","hentry","category-english","category-mood","category-science-life"],"_links":{"self":[{"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/posts\/1043","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/comments?post=1043"}],"version-history":[{"count":6,"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/posts\/1043\/revisions"}],"predecessor-version":[{"id":1224,"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/posts\/1043\/revisions\/1224"}],"wp:attachment":[{"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/media?parent=1043"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/categories?post=1043"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/tags?post=1043"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}