{"id":594,"date":"2014-11-10T17:55:36","date_gmt":"2014-11-10T17:55:36","guid":{"rendered":"http:\/\/www.dyalog.com\/blog\/?p=594"},"modified":"2018-05-21T13:16:53","modified_gmt":"2018-05-21T13:16:53","slug":"solving-the-2014-apl-problem-solving-competition-its-as-easy-as-1-1-2-3","status":"publish","type":"post","link":"https:\/\/www.dyalog.com\/blog\/2014\/11\/solving-the-2014-apl-problem-solving-competition-its-as-easy-as-1-1-2-3\/","title":{"rendered":"Solving the 2014 APL Problem Solving Competition &#8211; it&#8217;s as easy as 1 1 2 3&#8230;"},"content":{"rendered":"<p><a href=\"http:\/\/www.dyalogaplcompetition.com\/\" target=\"_blank\" rel=\"noopener\"><img loading=\"lazy\" decoding=\"async\" class=\"alignleft wp-image-677 \" src=\"http:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2014\/08\/intro-image.png\" alt=\"Competition Logo\" width=\"120\" height=\"139\" \/><\/a>The winners of the <a title=\"2014 Competition Website\" href=\"http:\/\/www.dyalogaplcompetition.com\/\" target=\"_blank\" rel=\"noopener\">2014 APL Problem Solving Competition<\/a> were recognized at the\u00a0<a title=\"Dyalog '14 User Meeting\" href=\"http:\/\/dyalog.com\/user-meetings\/dyalog14.htm\" target=\"_blank\" rel=\"noopener\">Dyalog &#8217;14<\/a>\u00a0user meeting and had a chance to <a title=\"2014 Competition Videos\" href=\"https:\/\/dyalog.tv\/Dyalog14\/?v=Il8bQ29mR34\" target=\"_blank\" rel=\"noopener\">share their competition experiences<\/a>. <a title=\"Emil Brener Orloff\" href=\"http:\/\/www.youtube.com\/watch?v=T1p92O5lMC0\" target=\"_blank\" rel=\"noopener\">Emil Bremer Orloff<\/a> won the student competition and received $2500 USD and an expenses-paid trip to Dyalog &#8217;14, while <a title=\"Iryna Pashenkovska\" href=\"http:\/\/www.youtube.com\/watch?v=r1TApZqn6Y4\" target=\"_blank\" rel=\"noopener\">Iryna Pashenkovska<\/a> took first place among\u00a0the non-student entries and received a complimentary registration to Dyalog &#8217;14. Our congratulations to them for\u00a0their fine efforts! This post is the first\u00a0of a series where we will examine some of the problems selected for this year&#8217;s competition. The problem we&#8217;ll discuss first is Problem 3 from Phase I dealing with the <a title=\"Wikipedia\" href=\"http:\/\/en.wikipedia.org\/wiki\/Fibonacci_number\" target=\"_blank\" rel=\"noopener\">Fibonacci sequence<\/a>.<\/p>\n<p><strong>Problem 3 &#8211; Tell a Fib<\/strong> Write a dfn that takes an integer right argument and returns that number of terms in the Fibonacci sequence. Test cases:<\/p>\n<pre><code class=\"language-apl\">\u00a0 \u00a0   {your_solution} 10\r\n 1 1 2 3 5 8 13 21 34 55\r\n      {your_solution} 1\r\n 1\r\n      {your_solution} 0   \u235d should return an empty vector\r\n<\/code><\/pre>\n<p>Essentially, you start with the sequence 1 1 and concatenate\u00a0the sum of the last 2 numbers to the end and repeat until\u00a0the sequence has the correct number of terms. In Python, a solution might look something like this:<\/p>\n<pre><span class=\"k\" style=\"font-weight: bold; color: #007020;\">def<\/span> <span class=\"nf\" style=\"color: #06287e;\">fib<\/span><span class=\"p\">(<\/span><span class=\"n\">n<\/span><span class=\"p\">):<\/span> <span class=\"c\" style=\"font-style: italic; color: #408090;\"># return the first n elements of the Fibonacci sequence<\/span>\r\n    <span class=\"n\">result<\/span> <span class=\"o\" style=\"color: #666666;\">=<\/span> <span class=\"p\">[]<\/span>\r\n    <span class=\"n\">a<\/span><span class=\"p\">,<\/span> <span class=\"n\">b<\/span> <span class=\"o\" style=\"color: #666666;\">=<\/span> <span class=\"mi\" style=\"color: #208050;\">0<\/span><span class=\"p\">,<\/span> <span class=\"mi\" style=\"color: #208050;\">1<\/span>\r\n    <span class=\"k\" style=\"font-weight: bold; color: #007020;\">while <\/span><span class=\"mi\" style=\"color: #208050;\">0<\/span> <span class=\"o\" style=\"color: #666666;\">&lt;<\/span> <span class=\"n\">n<\/span><span class=\"p\">:<\/span>\r\n        <span class=\"n\">result<\/span><span class=\"o\" style=\"color: #666666;\">.<\/span><span class=\"n\">append<\/span><span class=\"p\">(<\/span><span class=\"n\">b<\/span><span class=\"p\">)<\/span>\r\n        <span class=\"n\">a<\/span><span class=\"p\">,<\/span> <span class=\"n\">b<\/span> <span class=\"o\" style=\"color: #666666;\">=<\/span> <span class=\"n\">b<\/span><span class=\"p\">,<\/span> <span class=\"n\">a<\/span><span class=\"o\" style=\"color: #666666;\">+<\/span><span class=\"n\">b<\/span>\r\n        <span class=\"n\">n<\/span> -<span class=\"o\" style=\"color: #666666;\">=<\/span> <span class=\"o\" style=\"color: #666666;\">1<\/span>\r\n    <span class=\"k\" style=\"font-weight: bold; color: #007020;\">return<\/span> <span class=\"n\">result\r\n<\/span><\/pre>\n<p>You can write nearly\u00a0the same code in APL:<\/p>\n<pre><code class=\"language-apl\">r\u2190fibLooping n;a;b\r\n  r\u2190\u236c\r\n  (a b)\u21900 1\r\n:While 0&lt;n\r\n  r,\u2190b\r\n  (a b)\u2190b,a+b\r\n  n-\u21901\r\n:EndWhile\r\n<\/code><\/pre>\n<p>While it&#8217;s possible to write APL code that looks like Python (or many other languages), one of the judging criteria for the competition is the effective use of APL syntax\u00a0\u2013 in this case, by avoiding\u00a0the explicit loop. Two ways to do this are 1) using recursion and 2) using the power operator (<code class=\"language-apl\">\u2363<\/code>).<\/p>\n<h2>Recursive Solution<\/h2>\n<pre><code class=\"language-apl\">      fibRecursive\u2190{\u2375&lt;3:\u2375\u23741 \u22c4 {\u2375,+\/\u00af2\u2191\u2375}\u2207\u2375-1}<\/code><\/pre>\n<p>The neat thing about recursion is that the function keeps calling itself with a &#8220;simpler&#8221; argument until it reaches a base case and then passes\u00a0the results back up the stack.\u00a0Here the base case occurs when the argument (<code class=\"language-apl\">\u2375<\/code>) is less than 3 and the function returns <code class=\"language-apl\">\u2375\u23741<\/code> \u2013 it&#8217;s either an empty vector, 1, or 1 1 for values of <code class=\"language-apl\">\u2375<\/code> of 0, 1 and 2 respectively. It&#8217;s easy to illustrate the recursive process by adding some code (<code class=\"language-apl\">\u2395\u2190<\/code>) to display information at each level of recursion.<\/p>\n<pre><code class=\"language-apl\">      fibRecursive\u2190{\u2375&lt;3:\u2395\u2190\u2375\u23741 \u22c4 {\u2395\u2190\u2375,+\/\u00af2\u2191\u2375}\u2207\u2395\u2190\u2375-1}\r\n      fibRecursive 10\r\n9\r\n8\r\n7\r\n6\r\n5\r\n4\r\n3\r\n2\r\n1 1\r\n1 1 2\r\n1 1 2 3\r\n1 1 2 3 5\r\n1 1 2 3 5 8\r\n1 1 2 3 5 8 13\r\n1 1 2 3 5 8 13 21\r\n1 1 2 3 5 8 13 21 34\r\n1 1 2 3 5 8 13 21 34 55<\/code><\/pre>\n<p>The recursive solution above is termed &#8220;stack recursive&#8221; in that it creates a new level on the function call stack for each recursive call. We can modify the code slightly to implement a &#8220;<a href=\"http:\/\/en.wikipedia.org\/wiki\/Tail_call\" target=\"_blank\" rel=\"noopener\">tail recursive<\/a>&#8221; solution which Dyalog can detect and optimize by avoiding creating those additional function call stack levels. You can see the effect of this as each level computes its result immediately:<\/p>\n<pre><code class=\"language-apl\">      fibTail\u2190{\u237a\u21900 1 \u22c4 \u2375=0:\u2395\u21901\u2193\u00af1\u2193\u237a \u22c4 (\u2395\u2190\u237a,+\/\u00af2\u2191\u237a)\u2207 \u2395\u2190\u2375-1}\r\n      fibTail 10\r\n        fibTail 10\r\n9\r\n0 1 1\r\n8\r\n0 1 1 2\r\n7\r\n0 1 1 2 3\r\n6\r\n0 1 1 2 3 5\r\n5\r\n0 1 1 2 3 5 8\r\n4\r\n0 1 1 2 3 5 8 13\r\n3\r\n0 1 1 2 3 5 8 13 21\r\n2\r\n0 1 1 2 3 5 8 13 21 34\r\n1\r\n0 1 1 2 3 5 8 13 21 34 55\r\n0\r\n0 1 1 2 3 5 8 13 21 34 55 89\r\n1 1 2 3 5 8 13 21 34 55\r\n<\/code><\/pre>\n<h2>Power Operator Solution<\/h2>\n<pre><code class=\"language-apl\">      fibPower\u2190{\u2375\u2374({\u2375,+\/\u00af2\u2191\u2375}\u2363(0\u2308\u2375-1))1}<\/code><\/pre>\n<p>The power operator is defined as <code class=\"language-apl\">{R}\u2190{X}(f\u2363g)Y<\/code>. When the right operand <code class=\"language-apl\">g<\/code> is a numeric integer scalar \u2013 in this case <code class=\"language-apl\">(0\u2308\u2375-1)<\/code>, the power operator applies its left operand function <code class=\"language-apl\">f<\/code> \u2013 <code class=\"language-apl\">{\u2375,+\/\u00af2\u2191\u2375}<\/code> cumulatively <code class=\"language-apl\">g<\/code> times to its argument <code class=\"language-apl\">Y<\/code>, which in this case is <code class=\"language-apl\">1<\/code>. Similar to the recursive solution, we can add <code class=\"language-apl\">\u2395\u2190<\/code> to see what happens at each application:<\/p>\n<pre><code class=\"language-apl\">      fibPower\u2190{\u2375\u2374({\u2395\u2190\u2375,+\/\u00af2\u2191\u2375}\u2363(0\u2308\u2375-1))1}\r\n      fibPower 10\r\n1 1\r\n1 1 2\r\n1 1 2 3\r\n1 1 2 3 5\r\n1 1 2 3 5 8\r\n1 1 2 3 5 8 13\r\n1 1 2 3 5 8 13 21\r\n1 1 2 3 5 8 13 21 34\r\n1 1 2 3 5 8 13 21 34 55\r\n1 1 2 3 5 8 13 21 34 55<\/code><\/pre>\n<p>In discussing this blog post with my fellow Dyalogers, <a title=\"I'm jealous - Roger has his own wikipedia entry. :)\" href=\"http:\/\/en.wikipedia.org\/wiki\/Roger_Hui\" target=\"_blank\" rel=\"noopener\">Roger Hui<\/a> showed me a rather neat construct:<\/p>\n<pre><code class=\"language-apl\">      fibRoger\u2190{1\u2227+\u2218\u00f7\\\u2375\u23741}     \u235d Roger's original version\r\n      fibBrian\u2190{1\u2227\u00f7(+\u2218\u00f7)\\\u2375\u23741}  \u235d tweaked to make result match contest examples\r\n      fibRoger 10\r\n1 2 3 5 8 13 21 34 55 89\r\n      fibBrian 10\r\n1 1 2 3 5 8 13 21 34 55<\/code><\/pre>\n<p>I&#8217;ve added the parentheses around <code class=\"language-apl\">+\u2218\u00f7<\/code> to make it a bit clearer what the left operand to the scan operator <code class=\"language-apl\">\\<\/code> is. Let&#8217;s break the code down&#8230;<\/p>\n<pre><code class=\"language-apl\">      \u2375\u23741 \u235d produces a vector of \u2375 1's \r\n1 1 1 1 1 \u235d for \u2375=5\r\n<\/code><\/pre>\n<p>Then we apply scan with the function <code class=\"language-apl\">+\u2218\u00f7<\/code>, which in this case has the effect of adding 1 to the reciprocal of the previous result:<\/p>\n<pre><code class=\"language-apl\">      (+\u2218\u00f7)\\1 1 1 1 1\r\n1 2 1.5 1.666666667 1.6<\/code><\/pre>\n<p>Note that the denominator of each term is the corresponding element of the Fibonacci series&#8230;<\/p>\n<pre><code class=\"language-apl\">1 \u00f7 <span style=\"text-decoration: underline;\">1<\/span> = 1\r\n2 \u00f7 <span style=\"text-decoration: underline;\">1<\/span> = 2\r\n3 \u00f7 <span style=\"text-decoration: underline;\">2<\/span> = 1.5\r\n5 \u00f7 <span style=\"text-decoration: underline;\">3<\/span> = 1.6666666667\r\n8 \u00f7 <span style=\"text-decoration: underline;\">5<\/span> = 1.6\r\n<\/code><\/pre>\n<p>To extract them, take the reciprocal and then the LCM (lowest common multiple) with 1.<\/p>\n<pre><code class=\"language-apl\">      1\u2227\u00f71 2 1.5 1.666666667 1.6\r\n1 1 2 3 5<\/code><\/pre>\n<p>What happens if you want to accurately compute larger Fibonacci numbers? There&#8217;s a limit to the precision based on the internal number representations. Because fibRoger and fibBrian delve into floating point representation, they&#8217;re the most limited. (Roger points out that the J language has native support for extended precision and does not suffer from this limitation.)<\/p>\n<p>Dyalog has a system variable, <code class=\"language-apl\">\u2395FR<\/code>, that sets the how floating-point operations are performed using either IEEE 754 64-bit floating-point operations or IEEE 754-2008 128-bit decimal floating-point operation. For most applications, 64-bit operations are\u00a0perfectly acceptable, but in applications that demand a very high degree of precision, 128-bit operations can be used, albeit at some performance degradation. Using 64-bit operations,\u00a0fibBrian loses accuracy after the 35th term while using 128-bits extends the accuracy to 68 terms.<\/p>\n<p>Even setting <code class=\"language-apl\">\u2395FR<\/code> to use 128-bit operations and the print precision, <code class=\"language-apl\">\u2395PP<\/code>, to its maximum, we can only compute up to the 164th element 34-digit\u00a08404037832974134882743767626780173 before being forced into scientific notation.<\/p>\n<p>Can we go further easily? Yes we can! Using Dyalog for Microsoft Windows&#8217; .NET integration, we can seamlessly make use of the BigInteger class in the System.Numerics .NET namespace.<br \/>\nFirst we need to specify the namespace and where to look for it&#8230;<\/p>\n<pre><code class=\"language-apl\">      \u2395USING\u2190'System.Numerics,system.numerics.dll'<\/code><\/pre>\n<p>Then we make a trivial change to our code to use BigInteger instead of native data types&#8230;<\/p>\n<pre><code class=\"language-apl\">      fibRecursive\u2190{\u2375&lt;3:\u2375\u2374\u2395NEW BigInteger 1 \u22c4 {\u2375,+\/\u00af2\u2191\u2375}\u2207 \u2375-1}<\/code><\/pre>\n<p>And we&#8217;re done!<\/p>\n<p>So the next time someone walks up to you and asks &#8220;What can you tell me about the 1,000th element of the Fibonacci series?&#8221;, you can confidently reply that it has 209 digits and a value of<br \/>\n43466557686937456435688527675040625802564660517371780402481729<br \/>\n08953655541794905189040387984007925516929592259308032263477520<br \/>\n96896232398733224711616429964409065331879382989696499285160037<br \/>\n04476137795166849228875.<\/p>\n<p>For other APL Fibonacci implementations, check out <a title=\"dfns Fibonacci page\" href=\"http:\/\/dfns.dyalog.com\/n_fibonacci.htm\" target=\"_blank\" rel=\"noopener\">this page<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The winners of the 2014 APL Problem Solving Competition were recognized at the\u00a0Dyalog &#8217;14\u00a0user meeting and had a chance to share their competition experiences. Emil Bremer Orloff won the student competition and received $2500 USD and an expenses-paid trip to &hellip; <a href=\"https:\/\/www.dyalog.com\/blog\/2014\/11\/solving-the-2014-apl-problem-solving-competition-its-as-easy-as-1-1-2-3\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":10,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[13,8,22,18],"tags":[],"class_list":["post-594","post","type-post","status-publish","format-standard","hentry","category-algorithms","category-apl-language","category-student-competition","category-tips-tricks"],"_links":{"self":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/594","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/users\/10"}],"replies":[{"embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/comments?post=594"}],"version-history":[{"count":76,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/594\/revisions"}],"predecessor-version":[{"id":5174,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/594\/revisions\/5174"}],"wp:attachment":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/media?parent=594"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/categories?post=594"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/tags?post=594"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}