Juliar – Using recurrence to solve difficult problems

Profile image for rattar
January 13, 2018 | Views: 1487

Begin Learning Cyber Security for FREE Now!

FREE REGISTRATIONAlready a Member Login Here

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
FacebookTwitterGoogle+LinkedInEmail
Use Cybytes and
Tip the Author!
Join
Share with Friends
FacebookTwitterGoogle+LinkedInEmail
Ready to share your knowledge and expertise?
Comment on This

You must be logged in to post a comment.

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.

Get it on Google Play
 

Support Cybrary

Donate Here to Get This Month's Donor Badge

 

Cybrary|0P3N

Skip to toolbar

We recommend always using caution when following any link

Are you sure you want to continue?

Continue
Cancel