<commit_before>---
layout: post
title: Fibonacci Numbers with Matrices
---

Ahh, the Fibonacci numbers. What mathemetician doesn't love them?

Well, in Week 06 of CIS194, some interesting implementations were discussed. My favorite (that I never actually had encountered before), was in order to get the `n`'th number, you raise a two by two matrix to the `n`'th power. 

Let's take a look at my implementation:

##The Matrix

First off, you need to be able to represent matrices. I decided to use a tuple of tuples for the two by two matrix. 

{% highlight haskell %}
data Matrix = Matrix ((Integer, Integer), (Integer, Integer))
{% endhighlight %}

I also wanted to be able to print them nicely in the terminal, so I whipped up a quick show function. I could have derived it, but in my opinion, this makes it look slightly nicer (sorry, the function is a bit long, so the text wraps). 

{% highlight haskell %}
instance Show Matrix where
	show (Matrix ((a, b), (c, d))) = "[" ++ show a ++ ", " ++ show b ++ "]\n[" ++ show c ++ ", " ++ show d ++ "]"
{% endhighlight %}

And now let's instantiate a matrix!

{% highlight haskell %}
m :: Matrix
m = Matrix ((1, 1), (1, 0))
{% endhighlight %}

To check that it works, let's print out the matrix in `ghci`:

{% highlight Bash shell scripts %}
λ> m
[1, 1]
[1, 0]
λ> 

{% endhighlight %}

##Multiplying Matrices

So that's great, but these matrices don't really do much. We need to be able to raise each matrix to a specific power, but who knows how to do that? I sure don't. With that being said, I do know how to multiply two 2x2 matrices together! Let's define a function `(*)` that takes two 2x2 matrices and returns a matrix representing the multiplication of the two arguments. This multiplication function is a part of the `Num` typeclass, so in essence, we are making `Matrix` an instance of `Num`. 

{% highlight haskell %}
instance Num Matrix where
	(*) (Matrix ((a, b), (c, d))) (Matrix ((e, f), (g, h))) = Matrix (
			((a*e + b*g), (a*f + b*h)), 
			((c*e + d*g), (c*f + d*h))
		)
{% endhighlight %}

You can raise any instance of `Num` to a power after defining the multiplication operator, so Haskell will take care of the rest.

##Quick helper function

The last element of a matrix will represent the Fibonacci number you're looking for. So let's whip up a quick function to get that element. 

{% highlight haskell %}
l :: Matrix -> Integer
l (Matrix m) = (snd . snd) m
{% endhighlight %}

##Finally, the Fibonacci Function!

In CIS194, this is the fourth version of the function, so it is named `fib4`. Essentially, you take a number `n` and return the `n`th Fibonacci number by raising a 2x2 matrix to the `n`th power. Note that raising the matrix to the `0`th power won't work, so we'll use pattern-matching to account for that special case.  

{% highlight haskell %}
fib4 :: Integer -> Integer
fib4 0 = 0
fib4 n = l (f^(n))
{% endhighlight %}

##Conclusion

To conclude, let's try it out!

What's an insanely large Fibonacci number? Well my birthday is April 13th, 1998, so how about we calculate the `41398`th Fibonacci? That'll take a while, especially in ghci, right? Wrong. 

![Screen_Shot 1]({{ site.url }}blog/resources/Fibonacci_ss_1.png)

...

![Screen_Shot 2]({{ site.url }}blog/resources/Fibonacci_ss_2.png)

That's right, the answer is a `8652` digit number, and was calculated in about `.009` seconds. If you want to see the answer, check out [this .txt file]({{ site.url }}blog/resources/Fibonacci_answer.txt). <commit_msg>Screen shots don't show ghci<commit_after>---
layout: post
title: Fibonacci Numbers with Matrices
---

Ahh, the Fibonacci numbers. What mathemetician doesn't love them?

Well, in Week 06 of CIS194, some interesting implementations were discussed. My favorite (that I never actually had encountered before), was in order to get the `n`'th number, you raise a two by two matrix to the `n`'th power. 

Let's take a look at my implementation:

##The Matrix

First off, you need to be able to represent matrices. I decided to use a tuple of tuples for the two by two matrix. 

{% highlight haskell %}
data Matrix = Matrix ((Integer, Integer), (Integer, Integer))
{% endhighlight %}

I also wanted to be able to print them nicely in the terminal, so I whipped up a quick show function. I could have derived it, but in my opinion, this makes it look slightly nicer (sorry, the function is a bit long, so the text wraps). 

{% highlight haskell %}
instance Show Matrix where
	show (Matrix ((a, b), (c, d))) = "[" ++ show a ++ ", " ++ show b ++ "]\n[" ++ show c ++ ", " ++ show d ++ "]"
{% endhighlight %}

And now let's instantiate a matrix!

{% highlight haskell %}
m :: Matrix
m = Matrix ((1, 1), (1, 0))
{% endhighlight %}

To check that it works, let's print out the matrix in `ghci`:

{% highlight Bash shell scripts %}
λ> m
[1, 1]
[1, 0]
λ> 

{% endhighlight %}

##Multiplying Matrices

So that's great, but these matrices don't really do much. We need to be able to raise each matrix to a specific power, but who knows how to do that? I sure don't. With that being said, I do know how to multiply two 2x2 matrices together! Let's define a function `(*)` that takes two 2x2 matrices and returns a matrix representing the multiplication of the two arguments. This multiplication function is a part of the `Num` typeclass, so in essence, we are making `Matrix` an instance of `Num`. 

{% highlight haskell %}
instance Num Matrix where
	(*) (Matrix ((a, b), (c, d))) (Matrix ((e, f), (g, h))) = Matrix (
			((a*e + b*g), (a*f + b*h)), 
			((c*e + d*g), (c*f + d*h))
		)
{% endhighlight %}

You can raise any instance of `Num` to a power after defining the multiplication operator, so Haskell will take care of the rest.

##Quick helper function

The last element of a matrix will represent the Fibonacci number you're looking for. So let's whip up a quick function to get that element. 

{% highlight haskell %}
l :: Matrix -> Integer
l (Matrix m) = (snd . snd) m
{% endhighlight %}

##Finally, the Fibonacci Function!

In CIS194, this is the fourth version of the function, so it is named `fib4`. Essentially, you take a number `n` and return the `n`th Fibonacci number by raising a 2x2 matrix to the `n`th power. Note that raising the matrix to the `0`th power won't work, so we'll use pattern-matching to account for that special case.  

{% highlight haskell %}
fib4 :: Integer -> Integer
fib4 0 = 0
fib4 n = l (f^(n))
{% endhighlight %}

##Conclusion

To conclude, let's try it out!

What's an insanely large Fibonacci number? Well my birthday is April 13th, 1998, so how about we calculate the `41398`th Fibonacci? That'll take a while, right? Wrong. 

![Screen_Shot 1]({{ site.url }}blog/resources/Fibonacci_ss_1.png)

...

![Screen_Shot 2]({{ site.url }}blog/resources/Fibonacci_ss_2.png)

That's right, the answer is a `8652` digit number, and was calculated in about `.009` seconds. If you want to see the answer, check out [this .txt file]({{ site.url }}blog/resources/Fibonacci_answer.txt). 
{'fraction_non_alphanumeric': 0.11169832881016997, 'fraction_numerical': 0.014569347236109127, 'mean_word_length': 3.9942938659058487, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3000711', 'n_tokens_mistral': 2346, 'n_tokens_neox': 2086, 'n_words': 1075}