| --- |
| layout: post |
| title: Calculating Fibonacci with Groovy revisited |
| date: '2022-09-08T00:00:00+00:00' |
| categories: groovy |
| --- |
| <p>In a <a href="https://blogs.apache.org/roller-ui/authoring/entryEdit.rol?weblog=groovy&bean.id=7e7c1b79-5567-452b-ac11-0d55f765fd90" target="_blank">recent post</a>, we looked at using <a href="https://blogs.apache.org/roller-ui/authoring/entryEdit.rol?weblog=groovy&bean.id=7e7c1b79-5567-452b-ac11-0d55f765fd90" target="_blank">Matrices with Groovy</a> including using matrices to calculate Fibonacci terms. But do you need that complexity to calculate Fibonacci? Not, not at all. You can do various one-liners for that scenario (to repeat the calculation from that post):</p><pre style="background-color:#2b2b2b;color:#a9b7c6;font-family:'JetBrains Mono',monospace;font-size:9.6pt;">Stream.<span style="color:#9876aa;font-style:italic;">iterate</span>([<span style="color:#6897bb;">1</span>, <span style="color:#6897bb;">1</span>], f -> [f[<span style="color:#6897bb;">1</span>], f.sum()]).limit(<span style="color:#6897bb;">8</span>).toList()*.head()<br></pre><p>The previous post was more about using <i>matrices</i> than Fibonacci per se, though hopefully learning that the Fibonacci matrix was a specialisation of the Leslie matrix was an added bonus.</p><p>Let's have a look at a few other options to write Fibonacci methods in Groovy.</p>
|
|
|
| <h3>Iterative style</h3>
|
|
|
| <p>Unless you learned a functional programming language as your first language, you may have written an iterative Factorial or Fibonacci as one of your first programming learning exercises. Such an algorithm for Fibonacci could look something like this:</p><pre style="background-color:#2b2b2b;color:#a9b7c6;font-family:'JetBrains Mono',monospace;font-size:9.6pt;"><span style="color:#cc7832;">def </span>fib(n) {<br> <span style="color:#cc7832;">if </span>(n <= <span style="color:#6897bb;">1</span>) <span style="color:#cc7832;">return </span>n<br><br> <span style="color:#cc7832;">def </span>previous = n.valueOf(<span style="color:#6897bb;">1</span>), next = previous, sum<br> (n-<span style="color:#6897bb;">2</span>).times <span style="font-weight:bold;">{<br></span><span style="font-weight:bold;"> </span>sum = previous<br> previous = next<br> next = sum + previous<br> <span style="font-weight:bold;">}<br></span><span style="font-weight:bold;"> </span>next<br>}<br><br><span style="color:#cc7832;">assert </span>fib(<span style="color:#6897bb;">10</span>) == <span style="color:#6897bb;">55<br></span><span style="color:#cc7832;">assert </span>fib(<span style="color:#6897bb;">50L</span>) == <span style="color:#6897bb;">12586269025L<br></span><span style="color:#cc7832;">assert </span>fib(<span style="color:#6897bb;">100G</span>) == <span style="color:#6897bb;">354224848179261915075G</span><span style="color:#6a8759;"><br></span></pre><p>The only interesting part to this solution is the use of dynamic idioms. We didn't provide an explicit type for n, so duck-typing means the method works fine for <code>Integer</code>, <code>Long</code> and <code>BigInteger</code> values. This implementation does all calculations using the type of the supplied <code>n</code>, so the user of the method controls that aspect.</p><p>Groovy gives the option to also specify an explicit type like <code>Number</code> or use <code>TypeChecked</code> or <code>CompileStatic</code> for type inference if you wanted. We'll see an example of those options later.</p>
|
|
|
| <h3>Recursive</h3>
|
|
|
| <p>Once you mastered iterative programming, your next programming learning exercise may have been the recursive version of Factorial or Fibonacci. For Fibonacci, you may have coded something like this:</p>
|
| <pre style="background-color:#2b2b2b;color:#a9b7c6;font-family:'JetBrains Mono',monospace;font-size:9.6pt;"><span style="color:#cc7832;">def </span>fib(n) {<br> <span style="color:#cc7832;">if </span>(n <= <span style="color:#6897bb;">1</span>) <span style="color:#cc7832;">return </span>n<br> fib(n - <span style="color:#6897bb;">1</span>) + fib(n - <span style="color:#6897bb;">2</span>)<br>}<br><br><span style="color:#cc7832;">assert </span>fib(<span style="color:#6897bb;">10</span>) == <span style="color:#6897bb;">55<br></span><span style="color:#cc7832;">assert </span>fib(<span style="color:#6897bb;">50L</span>) == <span style="color:#6897bb;">12586269025L<br></span><span style="color:#cc7832;">assert </span>fib(<span style="color:#6897bb;">100G</span>) == <span style="color:#6897bb;">354224848179261915075G</span><span style="color:#6a8759;"><br></span></pre><p>This naïve version is incredibly inefficient. Calling fib(6) ends up calculating fib(2) five times for instance:</p>
|
| <p><img src="https://upload.wikimedia.org/wikipedia/commons/thumb/a/a3/Call_Tree_for_Fibonacci_Number_F6.svg/750px-Call_Tree_for_Fibonacci_Number_F6.svg.png" style="width:40%"></p>
|
| <p>There are several ways to avoid that repetition. One option is to use the <code>@Memoized</code> annotation. Adding this annotation on a method causes the compiler to inject appropriate code for caching results into the method. This is ideal for pure functions like Fibonacci since they always return the same output for a given input. There are annotation attributes to adjust how big such a cache might be, but that sophistication isn't needed here.</p><pre style="background-color:#2b2b2b;color:#a9b7c6;font-family:'JetBrains Mono',monospace;font-size:9.6pt;"><span style="color:#bbb529;">@Memoized<br></span><span style="color:#cc7832;">def </span>fib(n) {<br> <span style="color:#cc7832;">if </span>(n <= <span style="color:#6897bb;">1</span>) <span style="color:#cc7832;">return </span>n<br> fib(n - <span style="color:#6897bb;">1</span>) + fib(n - <span style="color:#6897bb;">2</span>)<br>}<br><br><span style="color:#cc7832;">assert </span>fib(<span style="color:#6897bb;">10</span>) == <span style="color:#6897bb;">55<br></span><span style="color:#cc7832;">assert </span>fib(<span style="color:#6897bb;">50L</span>) == <span style="color:#6897bb;">12586269025L<br></span><span style="color:#cc7832;">assert </span>fib(<span style="color:#6897bb;">100G</span>) == <span style="color:#6897bb;">354224848179261915075G</span><span style="color:#6a8759;"><br></span></pre>
|
| <p>This now runs just as quickly as the iterative method. If you happened to use a <code>Closure</code> instead of a method, you can call one of the <code>memoize</code> methods on <code>Closure</code>.</p><p>A problem with this approach (in fact recursion in general) is that you hit a stack overflow exception for larger values of <code>n</code>, e.g. <code>fib(500G)</code>. Groovy supports tail call elimination with the inclusion of the <code>TailRecursive</code> annotation. In this case the compiler injects an "unrolled" non-recursive version of the algorithm. In order for the "unrolling" to succeed, the algorithm needs to be re-worked so that at most one call to fib occurs in any return statement. Here is a version of the algorithm re-worked in this way:</p>
|
| <pre style="background-color:#2b2b2b;color:#a9b7c6;font-family:'JetBrains Mono',monospace;font-size:9.6pt;"><span style="color:#bbb529;">@TailRecursive<br></span><span style="color:#cc7832;">static </span>fib(n, a, b) {<br> <span style="color:#cc7832;">if </span>(n == <span style="color:#6897bb;">0</span>) <span style="color:#cc7832;">return </span>a<br> <span style="color:#cc7832;">if </span>(n == <span style="color:#6897bb;">1</span>) <span style="color:#cc7832;">return </span>b<br> <span style="color:#9876aa;font-style:italic;">fib</span>(n - <span style="color:#6897bb;">1</span>, b, a + b)<br>}<br><br><span style="color:#cc7832;">assert </span><span style="color:#9876aa;font-style:italic;">fib</span>(<span style="color:#6897bb;">10</span>, <span style="color:#6897bb;">0</span>, <span style="color:#6897bb;">1</span>) == <span style="color:#6897bb;">55<br></span><span style="color:#cc7832;">assert </span><span style="color:#9876aa;font-style:italic;">fib</span>(<span style="color:#6897bb;">50L</span>, <span style="color:#6897bb;">0L</span>, <span style="color:#6897bb;">1L</span>) == <span style="color:#6897bb;">12586269025L<br></span><span style="color:#cc7832;">assert </span><span style="color:#9876aa;font-style:italic;">fib</span>(<span style="color:#6897bb;">100G</span>, <span style="color:#6897bb;">0G</span>, <span style="color:#6897bb;">1G</span>) == <span style="color:#6897bb;">354224848179261915075G<br></span><span style="color:#cc7832;">assert </span><span style="color:#9876aa;font-style:italic;">fib</span>(<span style="color:#6897bb;">500G</span>, <span style="color:#6897bb;">0G</span>, <span style="color:#6897bb;">1G</span>) == <span style="color:#6897bb;">139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125G<br></span></pre><p>This is slightly more complicated to understand than the original if you haven't seen it before but now is both efficient and handles large values of <code>n</code>. We can compile statically for even faster speed like this:</p><pre style="background-color:#2b2b2b;color:#a9b7c6;font-family:'JetBrains Mono',monospace;font-size:9.6pt;"><span style="color:#bbb529;">@TailRecursive<br></span><span style="color:#bbb529;">@CompileStatic<br></span><span style="color:#cc7832;">static </span>fib(Number n, Number a, Number b) {<br> <span style="color:#cc7832;">if </span>(n == <span style="color:#6897bb;">0</span>) <span style="color:#cc7832;">return </span>a<br> <span style="color:#cc7832;">if </span>(n == <span style="color:#6897bb;">1</span>) <span style="color:#cc7832;">return </span>b<br> <span style="color:#9876aa;font-style:italic;">fib</span>(n - <span style="color:#6897bb;">1</span>, b, a + b)<br>}<br><br><span style="color:#cc7832;">assert </span><span style="color:#9876aa;font-style:italic;">fib</span>(<span style="color:#6897bb;">10</span>, <span style="color:#6897bb;">0</span>, <span style="color:#6897bb;">1</span>) == <span style="color:#6897bb;">55<br></span><span style="color:#cc7832;">assert </span><span style="color:#9876aa;font-style:italic;">fib</span>(<span style="color:#6897bb;">50L</span>, <span style="color:#6897bb;">0L</span>, <span style="color:#6897bb;">1L</span>) == <span style="color:#6897bb;">12586269025L<br></span><span style="color:#cc7832;">assert </span><span style="color:#9876aa;font-style:italic;">fib</span>(<span style="color:#6897bb;">100G</span>, <span style="color:#6897bb;">0G</span>, <span style="color:#6897bb;">1G</span>) == <span style="color:#6897bb;">354224848179261915075G<br></span><span style="color:#cc7832;">assert </span><span style="color:#9876aa;font-style:italic;">fib</span>(<span style="color:#6897bb;">500G</span>, <span style="color:#6897bb;">0G</span>, <span style="color:#6897bb;">1G</span>) == <span style="color:#6897bb;">139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125G<br></span></pre><p>If you are using a <code>Closure</code>, you would look at using the <code>trampoline</code> method on <code>Closure</code> to achieve a similar result.</p><h3>Streams</h3>
|
| <p>We saw the Stream based "one-liner" solution at the start of this blog post. Let's adopt the duck-typing idioms we have used so far and define a fib method. It could look like this:</p>
|
| <pre style="background-color:#2b2b2b;color:#a9b7c6;font-family:'JetBrains Mono',monospace;font-size:9.6pt;"><span style="color:#cc7832;">def </span>fib(n) {<br> <span style="color:#cc7832;">def </span>zero = n.valueOf(<span style="color:#6897bb;">0</span>)<br> <span style="color:#cc7832;">def </span>one = n.valueOf(<span style="color:#6897bb;">1</span>)<br> Stream.<span style="color:#9876aa;font-style:italic;">iterate</span>([zero, one], t -> [t[<span style="color:#6897bb;">1</span>], t.sum()])<br> .skip(n.longValue())<br> .findFirst().get()[<span style="color:#6897bb;">0</span>]<br>}<br><br><span style="color:#cc7832;">assert </span>fib(<span style="color:#6897bb;">10</span>) == <span style="color:#6897bb;">55<br></span><span style="color:#cc7832;">assert </span>fib(<span style="color:#6897bb;">50L</span>) == <span style="color:#6897bb;">12586269025L<br></span><span style="color:#cc7832;">assert </span>fib(<span style="color:#6897bb;">100G</span>) == <span style="color:#6897bb;">354224848179261915075G</span><span style="color:#6a8759;"><br></span></pre>
|
| <h3>Bytecode and AST transforms</h3>
|
| <p>Finally, just so you know all your options, here is a version using the <a href="https://github.com/melix/groovy-bytecode-ast" target="_blank">@Bytecode AST transform</a> which lets you write JVM bytecode directly in your Groovy! Note this falls into the category of "don't ever ever do this" but just so you know you can, it is included here:</p>
|
| <pre style="background-color:#2b2b2b;color:#a9b7c6;font-family:'JetBrains Mono',monospace;font-size:9.6pt;"><span style="color:#bbb529;">@Bytecode<br></span><span style="color:#cc7832;">int </span>fib(<span style="color:#cc7832;">int </span>i) {<br> l0<br> iload <span style="color:#6897bb;">1<br></span><span style="color:#6897bb;"> </span>iconst_2<br> if_icmpgt l1<br> iconst_1<br> _goto l2<br> l1<br> frame SAME<br> aload <span style="color:#6897bb;">0<br></span><span style="color:#6897bb;"> </span>iload <span style="color:#6897bb;">1<br></span><span style="color:#6897bb;"> </span>iconst_2<br> isub<br> invokevirtual <span style="color:#6a8759;">'.fib'</span>,<span style="color:#6a8759;">'(I)I'<br></span><span style="color:#6a8759;"> </span>aload <span style="color:#6897bb;">0<br></span><span style="color:#6897bb;"> </span>iload <span style="color:#6897bb;">1<br></span><span style="color:#6897bb;"> </span>iconst_1<br> isub<br> invokevirtual <span style="color:#6a8759;">'.fib'</span>, <span style="color:#6a8759;">'(I)I'<br></span><span style="color:#6a8759;"> </span>iadd<br> l2<br> frame same1,<span style="color:#6a8759;">'I'<br></span><span style="color:#6a8759;"> </span>ireturn<br>}<br><br><span style="color:#cc7832;">assert </span>fib(<span style="color:#6897bb;">10</span>) == <span style="color:#6897bb;">55</span><span style="color:#6a8759;"><br></span></pre><p>Please read the caveats for that transform before considering using it for anything but extreme situations. It's meant more as a fun thing to try than something anyone would want to do in production.</p><p>Have fun writing your own algorithms!</p><p><br></p> |
