# Juliar – Using recurrence to solve difficult problems

January 13, 2018 | Views: 1825

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 = 2

1+2 = 3

2+3 = 5

3+5 = 8

5+8 = 13

8+13 = 21

13+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.

If you are interested in our project, visit https://juliar.org

Juliar Team

Share with Friends
Use Cybytes and
Tip the Author!
Share with Friends

### Our Revolution

We believe Cyber Security training should be free, for everyone, FOREVER. Everyone, everywhere, deserves the OPPORTUNITY to learn, begin and grow a career in this fascinating field. Therefore, Cybrary is a free community where people, companies and training come together to give everyone the ability to collaborate in an open source way that is revolutionizing the cyber security educational experience.

### Cybrary On The Go

Get the Cybrary app for Android for online and offline viewing of our lessons.

Â

### Support Cybrary

Donate Here to Get This Month's Donor Badge

Â

### Cybrary|0P3N

We recommend always using caution when following any link

Are you sure you want to continue?

Continue
Cancel