Tag Archives: fibonacci

Linear Recurrences

How often has it happened to you in a programming contest (or elsewhere) that you thought it was impossible to solve it faster than O(N) and yet the limits imposed suggest that it has to be done faster. Well, if not all, atleast a majority of them have a solution based on the idea of linear recurrences. In this blog post, I intend to help you out on this !!

In this post, we are going to do a – Solve and Learn strategy ; You will be given a question and I will show you how to apply  the concepts on them.

TYPE 1 :: The Simplest :

If a post mentions recurrences, then it has to mention Fibonacci (Gosh, if only I had a penny for every mention of Fibo in tutorials. )

The recurrence is of type : F(n) = F(n-1) + F(n-2).

I am pretty sure you know to code the linear version of it which runs in O(N) but can you do it in O(log N) ? If you throw google to good use, you will come up with a solution which says there is a Matrix M which when raised to power N, will give you the N-th fibonacci number. And since you can always exponentiate in logN time, you have your answer. But to those, who wondered if this Matrix is magical- read on!

Firstly the answer- No; Its not magical. How. Lets do a little Algebra (yumm… My favourite! )
F(n)=F(n-1)+F(n-2)\\ \\ F(n+1) =F(n)+F(n-1)\\ \\ F(n+2)=F(n+1)+F(n)

Obviously enough, the value of N-th term, depends on two previous terms (or states). This implies that all values depend on just the first two states in the sequence. As you can see here –

\begin{pmatrix}F(n+2)\\ F(n+1)\end{pmatrix}=\begin{pmatrix}1&1\\ 1&0\\ \end{pmatrix}\times\begin{pmatrix}F(n+1)\\ F(n)\end{pmatrix}\\ \\ and\\ \\ \begin{pmatrix}F(n+1)\\ F(n)\end{pmatrix}=\begin{pmatrix}1&1\\ 1&0\\ \end{pmatrix} \times \begin{pmatrix}F(n)\\ F(n-1)\end{pmatrix} \\ \\ Hence \\ \\ \begin{pmatrix}F(n+2)\\ F(n+1)\end{pmatrix}=\begin{pmatrix}1&1\\ 1&0\\ \end{pmatrix} ^2 \times \begin{pmatrix}F(n)\\ F(n-1)\end{pmatrix} \\ \\ \begin{pmatrix}F(n+2)\\ F(n+1)\end{pmatrix}=\begin{pmatrix}1&1\\ 1&0\\ \end{pmatrix}^3 \times \begin{pmatrix}F(n-1)\\ F(n-2)\end{pmatrix}

Hence in General, we may write ::
\begin{pmatrix}F(n)\\ F(n-1)\end{pmatrix}=\begin{pmatrix}1&1\\ 1&0\\ \end{pmatrix}^{n-1} \times \begin{pmatrix}1\\ 0\end{pmatrix}

I hope that has helped you in understanding how to frame such equations and solving it with a matrix.

TYPE 2 : Simplest ++

Now that we have a basic understanding. Try the following recurrence :

F(n) = F(n-1) + F(n-2) + F(n-3).

It is the same as the previous recurrence but with an additional state. I won’t go on explaining the hows (again!). I am going to share the solution.
\begin{pmatrix}F(n)\\ F(n-1)\\ F(n-2) \end{pmatrix}=\begin{pmatrix}1&1&1\\ 1&0&0\\ 0&1&0 \end{pmatrix}^{n-2} \times \begin{pmatrix}2\\ 1\\ 1\end{pmatrix}

TYPE 3: Simplest << 1

Consider the following scenario ::

G(n) = a . G(n-1) + b . G(n-2) + c . H(n)\\ \\ and \\ \\ H(n)= d . H(n-1) + e . H(n-2)

This one is a lot trickier. First thing to notice is that we will need 4 states in a matrix to fully define the next state. The reason for using 4 and not 3 is that H(n) depends on 2 states and thus we need 2 states (and not just 1) to represent it.

If you carefully write down the LHS matrix and the RHS matrix, then we can frame the solution as . . .

\begin{pmatrix}G(n)\\ G(n-1)\\ H(n+1)\\ H(n) \end{pmatrix}=\begin{pmatrix}a&b&c&0\\ 1&0&0&0\\ 0&0&d&e\\ 0&0&1&0 \end{pmatrix}^{n-1} \times \begin{pmatrix}G(1)\\ G(0)\\ H(2)\\ H(1)\end{pmatrix}

TYPE 4 : Ohhh !

The final hurdle can come in the name of a constant. If we add a constant C to the above recurrence we get –

G(n) = a . G(n-1) + b . G(n-2) + c . H(n) + C\\ \\ and \\ \\ H(n)= d . H(n-1) + e . H(n-2)

But to tell you the truth, its not that difficult if your concepts are clean. Now there is another additional state to hold the information about C. The solution will look like –

\begin{pmatrix}G(n)\\ G(n-1)\\ H(n+1)\\ H(n)\\ C \end{pmatrix}=\begin{pmatrix}a&b&c&0&1\\ 1&0&0&0&0\\ 0&0&d&e&0\\ 0&0&1&0&0\\ 0&0&0&0&1 \end{pmatrix}^{n-1} \times \begin{pmatrix}G(1)\\ G(0)\\ H(2)\\ H(1)\\ C\end{pmatrix}

I hope this post lived up to your expectations and I hope it was worth the wait :P. Please feel free to post comments/corrections/improvements to this post to make it really useful.

Advertisements

BrainFUCK-ed

If you are offended by the title, then please SKIP! So, you were caught in the BrainFuck bubble as well. Isn’t it one of the coolest esolangs out there! You might argue – Whats the use of this language. It can’t be used for any REAL software development. Maybe. But as a programmer, it can really strech your boundaries. How? Lets say in C, you had to write a program to print the first five fibonacci numbers (using the logic and not just printing it out), you would code it with your toes. I would too. But think of it in BrainFUCK and you will understand why Urban Muller named it so appropriately.

Here is the Wikilink for it so that you can see the basics of the languange.

In a C version of it, you will need 3 variables – to store the previous value and current value, and one temporary. One more to make sure you only print 5 and not any more , making our count 4 !
Lets look at the code now :

int main()
{
	int prev=1,curr=1,temp,count;
	for(count=0;count<5;count++)
	{
		printf("%d ",curr);
		temp=curr;
		curr=prev+curr;
		prev=temp;

	}
}

That was quick.
But even a simple program like this could make you think very hard in BrainFuck. Its fun to know that you have to think to write simpler programs. It makes my blood rush with just the thought of it.

So here goes !
We only have 8 instructions, out of which we will use 7 (since we are not reading anything from the stdin).
You have to think through absolutely every single thing before you so even put a ‘.’ (dot) on the code editor (quite literally).
We need to print SPACE, so we need 32(ASCII of SPACE) in the memory somewhere!.
We need to print number (for simplicities sake, ONE digit numbers) so we need to make sure we have the ASCII values of it, in memory (ASCII of 0 is 48, 1 is 49 and so on..).
If you look at the C code, we will need keep count of the number of items we have remaining to print. And then we need two locations to store previous and current values of the sequence. A very important thing to remember is that all memory is initialized to 0 at the start and we are relying on this for it to work. Also, the looping statements compare the memory location currently being referred (where your current pointer is) to against 0 and if it is true it breaks otherwise loops.

Writing a simple pseudocode (in terms of only Brainf*k) :

Initialize a location A to 32
Initialize a location B to 48
Initialize a location C to 5
Initialize a location D and E to 1.
Set current Location to C.
Start a Loop
	Add B to E and F.
	Print E.
	Subtract B from E
	Add D to E and F
	Copy E to D 
	Copy F to E
	Reduce C by 1 and Set it as the current location
End Loop

Basically, it was very easy to write this pseudocode. The issue with Braninf*k is that it does not have a COPY instruction for us to use, and so we need to use a looping statement to copy data. But the problem is that to ensure that the loop is executed the correct number of times, we will need to destroy the original value. To get around this, we always update two locations (one where we need it to be copied and the other a temporary!) and then we copy back from the temporary which also destroys it!

Also the A,B,C,D,E and F are all contiguous in memory and so I am using a[0],a[1]…a[6] to refer to them in the code !

Here is the final version.

++++++++[>++++>++++++<<-]>>>++++++>+>+<<-[<[>>>+>+<<<<-]>>>.<<<<.>>>>>[<-<<<+>>>>-]<[>+>+<<-]<[>>>+<<<-]>>[<<+>>-]>[<<+>>-]<<<<-]  

To make sense of it I have divided it into parts. Some parts have not been commented and are left as an exercise for you to figure out ( I know I am mean 😉 ).

++++++++[>++++>++++++<<-] //32 48
>>>++++++ //6
>+>+<<- //Set first two values to 1 and reduce the number of terms to be printed to 5.
[
	<[>>>+>+<<<<-]
	>>>.//print the number
	<<<<.//print space
	>>>>>[<-<<<+>>>>-]
	<[>+>+<<-]
	<[>>>+<<<-]
	>>[<<+>>-]//copy from a[6] to a[4]
	>[<<+>>-]//copy from a[7] to a[5]
	<<<<-//decrement the value
]  

All right. Pretty cool huh! Well as a real mind-boggler you can try making it print N numbers (dont worry about printing it right, just print out the actual value encoded by ascii ).

You could use it to even encrypt messages in a really wierd way. Oh almost forgot. To run your Brainf*k programs use the following website. They have an online interpreter and a debugger of sorts too : www.brainfk.tk

I hope you liked your Christmas Present ;-). Merry Christmas and a Happy New Year… Ho oh ho 😛


%d bloggers like this: