Ready to Start Your Career?

Juliar - Using recurrence to solve difficult problems

Rattar 's profile image

By: Rattar

January 13, 2018

Hey Everyone,I am creating a series of the insides of Juliar in order to educate you guys in better understanding Juliar and hopefully converting you to firm believers of it :)In this first tutorial in the series, we will explore the use of recurrence in order to speed up Juliar.So let's look at a basic built in function fib() and explore what it is and how it works.fib() is short for Fibonacci. It is a series of increasing numbers. The next number consist of addition of two numbers before it.So for example:0, 1, 1, 2, 3, 5, 8, 13, 21, 34...This is simple:
1+1 = 21+2 = 32+3 = 53+5 = 85+8 = 138+13 = 2113+21 = 34
You might look at the pattern and in Juliar, you might be thinking of creating your own function such as:function fib(x) = {if(x <= 1) { return 1; }else {return fib(x-2) + fib(x-1);}}Basically we are computing the 2 previous numbers and adding them to each other.You might be thinking that this is a clean and effective algorithm. However, you would be wrong.Computer executing fib(200) would still be computing even after planet earth disappears.  You might be wondering why? Well, the problem is that we are exponentially computing the fibonacci numbers. If we compute fib(x-1)...Why do we need to compute fib(x-2)? It seems like we are doing unnecessary work computing the fibonacci numbers that we have computed previously. Juliar's fib() function goes around that. Juliar utilizes recurrence to solve this.So here is the code that Juliar uses internally (simplified):class Array {}function fib(n) = {Array x;x[0] = 0;x[1] =  1;int i = 2;while(i<=n){x[i] =x[i-1]  + x[i-2];i = + 1 i;}return x[n];}You might notice that, we are not calling the function fib and that we are using an array to store the previous results. This turns out to be very effective. By sacrificing some memory, we are able to significantly speed up results. In the previous example, we found that we are constantly having to compute f(x-2)  and then recompute f(x-1) and this causes the algorithm to run in exponential time. By efficiently storing the results and using memory. Our algorithm runs in linear time. Therefore, we can compute fib(200) in a matter of minutes/seconds instead of years.Although, Juliar has a cache of the first 200 fib numbers, Juliar can be used to efficiently compute fibonnaci of much bigger numbers.Thank you for reading this! If this article generates interests, I will try to create more.If you are interested in our project, visit https://juliar.orgAlso, if you want to chat with us, please join our slack channel  at you for your time,Juliar Team
Schedule Demo