
Ready to Start Your Career?

By: Rattar
January 13, 2018
Juliar - Using recurrence to solve difficult problems
By: Rattar
January 13, 2018

By: Rattar
January 13, 2018

1+1 = 21+2 = 32+3 = 53+5 = 85+8 = 138+13 = 2113+21 = 34You 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 https://juliar.org/slackThank you for your time,Juliar TeamBuild your Cybersecurity or IT Career
Accelerate in your role, earn new certifications, and develop cutting-edge skills using the fastest growing catalog in the industry