Fibonacci Sequence - Very Long Number Adressing

http://jencropable.com/the-fibonacci-spiral/

I've always heard about sequences, the most famous is "the Fibonacci Sequence", and almost everyone've heard about the starting terms 0, 1, 1, 2, 3, 5, etc. Basically, the first term plus the second results in the third one, the second plus the third results in the fourth one, etc.

There is also a way to calculate any term based on the golden ratio:

If you want to know more about this sequence you can google it or visit this link:
http://en.wikipedia.org/wiki/Fibonacci_number

The problem is that if you want to know a very high term there is no way for a numeric type, on programming languages, to address it.

The solution to this problem is simple, if you want to know the term 1.000.000th first you have to estimate how many digits it has, to know the size of an array to store it, using the UInt64 type as a 19 digit handler (because it can not store the 20 digits number 99.999.999.999.999.999.999) you just need to split the number every 19 digits. 

So, for a 20 digits number you need a length 2 array (at least), to store 19 digits in the last position and 1 digit in the first position (keeping the order). The 1.000.000th term has 207.505 digits, so you should use a 10.922 length array.

Steps:




First: Use the "golden ratio based method" to instantly show the terms (for numbers below the 93rd term).
Second: Use a two* dimensional array to split the longer numbers using the regular method (adding the last 2 terms).

* : Two dimensions because you need to store two terms plus an auxiliar. You can also use three unidimesional arrays.

Why not List?
Array are way faster than Lists for calculations, around N to N^2 times for very long numbers.

What would this work for?
There is a lot of very useful applications, you can use it to implement a random number generator for example.

How does it work?
I use this method:

digits = term * 0.20898438
array length = ( digits / 19 ) + 1

so:

array length = 1 + term * 0.010999

So if you want to know the term 3.000.000th it should have no more than 626.955 digits, so you need a 32.998 length array (at least).

There should be a better, and more precise, way to get the number of digits, you should google it if you want to know, but I find this number by analizing the terms I got. 

Have fun and enjoy.
(This is a C# code) 

using System;
using System.Diagnostics;
namespace ConsoleApplication1
{
    class Program
    {
        static void GetFibonacci (int datoLeido)
        {
            int digitos = 0;
            int largo = (int)(1 + 0.010999 * datoLeido);
            Stopwatch sw = new Stopwatch();
            UInt64[,] fibonacci = new UInt64[largo , 3];
                if (datoLeido <= 93)
                {
                    fibonacci [0, 0] = (UInt64)(Math.Pow ((1 + Math.Sqrt (5)) / 2, datoLeido) / Math.Sqrt (5) - Math.Pow ((1 - Math.Sqrt (5)) / 2, datoLeido) / Math.Sqrt (5));
                    Console.WriteLine ("Term: " + fibonacci [0, 0]);
                    Console.WriteLine ("Press any key to continue...");
                    Console.ReadKey ();
                }
                else
                {
                    sw.Start ();
                    fibonacci [fibonacci.GetLength (0) - 1, 0] = (UInt64)(Math.Pow ((1 + Math.Sqrt (5)) / 2, 91) / Math.Sqrt (5) - Math.Pow ((1 - Math.Sqrt (5)) / 2, 91) / Math.Sqrt (5));
                    fibonacci [fibonacci.GetLength (0) - 1, 1] = (UInt64)(Math.Pow ((1 + Math.Sqrt (5)) / 2, 92) / Math.Sqrt (5) - Math.Pow ((1 - Math.Sqrt (5)) / 2, 92) / Math.Sqrt (5));
                    for (int j = 0; j <= datoLeido - 93; j++)
                    {
                        for (int i = fibonacci.GetLength (0) - 1; i >= 0; i--)
                        {
                            fibonacci [i, 2] = fibonacci [i, 1];
                            if (fibonacci [i, 1] == 0)
                                break;
                        }
                        for (int i = fibonacci.GetLength (0) - 1; i > 0; i--)
                        {
                            fibonacci [i, 1] += fibonacci [i, 0];
                            fibonacci [i - 1, 1] += fibonacci [i, 1] / 10000000000000000000;
                            fibonacci [i, 1] = fibonacci [i, 1] % 10000000000000000000;
                            if (fibonacci [i, 1] == 0)
                                break;
                        }
                        for (int i = fibonacci.GetLength (0) - 1; i >= 0; i--)
                        {
                            fibonacci [i, 0] = fibonacci [i, 2];
                            if (fibonacci [i, 2] == 0)
                                break;
                        }  
                    }
                    sw.Stop ();
                    Console.WriteLine ("Term: ");
                    for (int i = 0; i < fibonacci.GetLength (0); i++)
                    {
                        if (fibonacci [i, 1] != 0)
                        {
                            Console.Write (fibonacci [i, 1]);
                            digitos = digitos + fibonacci [i, 1].ToString ().Length;
                        }
                    }
                    Console.WriteLine ();
                    Console.WriteLine ("Digits: " + digitos);
                    Console.WriteLine ("Elapsed time: " + sw.Elapsed);
                    Console.Write ("Press a key to continue...");
                    Console.ReadKey ();
                }
        }

        static void Main(string[] args)
        {
            string datoLeido;
            int dl;
            do
            {  
                Console.Clear();
                Console.WriteLine ("Fibonacci Sequence");
                Console.WriteLine ("Enter the term you want to know? [X: Exit]");
                datoLeido = Console.ReadLine();
                if(int.TryParse(datoLeido, out dl))
                    GetFibonacci(dl);
                else
                    if(datoLeido.ToUpper()!="X")
                        Console.Write (" ¬¬ It should be an integer number...");
            }while(datoLeido.ToUpper()!="X");
        }
    }
}