Related Reads

January 13, 2018 | Views: 1966

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.

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.org

Also, if you want to chat with us, please join our slack channel at https://juliar.org/slack

Thank you for your time,

Juliar Team

Share with Friends

Use Cybytes and

Tip the Author!

Tip the Author!

Join

Share with Friends

Ready to share your knowledge and expertise?

Did You Know?

Cybrary training is FREE

Just create an account now for lifetime access. Members login here.

We recommend always using caution when following any link

Are you sure you want to continue?

Continue

Cancel