Large Integer Fibonacci Numbers

• Download FibonacciCalculator-noexe.zip - 23.1 KB
• Download FibonacciCalculator.zip - 23.1 KB

Introduction

This WPF C# .NET 4.5 code takes advantage of a 2-dimensional system of linear difference equations that gives a very fast implementation of generating large Fibinocci numbers (and Fibonacci numbers modulo N).

The Fibonacci numbers series starts 0,1,1,2,3,5,8,13,21,34,55,89.....

and is defined as: F[n] = F[n-2] + F[n-1]

They are found everywhere in mother nature and define the most efficient packing order of two dimensional objects:

They have some interesting properties when it comes to prime numbers. In fact, the algorithm (in the code below) tests for primality. The first few pseudoprimes are: 4181, 5777, 6479, 6721.

The graph of the first 332 pseudoprimes looks like this:

(If you can create an algorithm to test for the pseudoprimes, please be sure to drop a line in the comments below. I'd be glad to investigate it.)

Also, the Fibonacci sequence can be used to calculate the golden ratio. This is because F[n+1] / F[n] approaches the golden ratio as n approaches infinity.

Background

While looking for new methods for integer factorization and primality testing, I stumbled accross the Fibonacci series and was thoroughly fascinated by its properties.

I've always wondered: is there an efficient way to calculate the index (i) of Fib(i) where Fib(i) modulo m is congruent to zero and the factors of m are unknown?

And what about calculating the index (i) where Fib(i) % m is positve or negative one (and the factors of m are unknown)?

Some Speed Tests

Fibonacci.Fib(1000000);    

Takes ~ 9169 milliseconds.

Fibonacci.FibMod(BigInteger.Parse("1000000000000"), BigInteger.Parse("1000000000001")) ;

Takes ~ 2 milliseconds

Using the Code

You will need to reference System.Numerics in C# .NET 4.5 or higher.

This implementation makes use of some simple matrix operations for calculating Fibonacci numbers by index:

public static BigInteger Fib(BigInteger idx)
{
    if (idx == 0) return 0;
    if (idx == 1) return 0;
    var m = new FibMatrix(1, 1, 1, 0);
    m = m.RaiseMatrixByPower(idx - 1);
    return m.Result();
}

The matrix is raised to a power (idx - 1) and the resultant value in cell location (0,0) is the Fibonacci value.   The first few digits of the 1 millionth Fibonacci number is:

195328212870775773163201494759625633244354299659187339695340519457162525788701569476664198...

Also note, to calculate the golden ratio you can simply divide two consecutive Fibonacci numbers:

var dgs = BigInteger.Parse
("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
var f1 = Fibonacci.Fib(10000);
var f2 = Fibonacci.Fib(10001) * dgs;

var rs = f2 / f1;
var tmp = rs.ToString();

which gives (after placing the decimal):

1.6180339887498948482045868343656381177203091798057628621354486227052604628189024497072072041893911374

The following method handles the modular reduction of our Fibonacci numbers by some divisor:

public static BigInteger FibMod(BigInteger idx, BigInteger divisor)
{
    if (idx == 0) return 0;
    if (idx == 1) return 0;
    var m = new FibMatrix(1, 1, 1, 0);
    m = m.RaiseMatrixByPowerMod(idx - 1, divisor);
    return m.Result();
}

And it can be used to test for probable primality:

        public static bool IsProbablePrime(BigInteger value)
        {
            if (value <= 6)
            {
                if (value == 2) return true;
                if (value == 3) return true;
                if (value == 5) return true;
                return false;
            }
            if (value % 2 == 0) return false;
            if (value % 3 == 0) return false;

            if (value % 6 != 1 && value % 6 != 5) return false;

            var md = FibMod(value, value);
            var primeTest = false;

            var res = value % 5;

            if (res == 2 || res == 3)
            {
                if (md == (value - 1)) primeTest = true;
            }
            else
            {
                if (md == 1) primeTest = true;
            }

            return primeTest;
        }

Notice that this is a "probable prime" test. That means if it returns "true", there's a strong possibility that the number being tested is prime. However, if it returns false, it's absolutely NOT a prime.

Also, if you are asked to calculate the last 5 digits of the 10,000^th Fibonacci number:

var f1 = Fibonacci.FibMod(BigInteger.Parse("10000"), 100000);

which gives: 66875.

Points of Interest

1. Consecutive Fibonacci numbers are the worst case scenario in Euclid's GCD problem
2. Primality testing
3. Pisano periods, totients, and integer factorization
4. Possible to create a non-recursive method (to prevent stack overflows)
5. Possible speedups that utilize multiple threads

Some Interesting Equations

1. Golden Ratio = (1 + SQRT(5)) / 2
2. F(n) = [(1 + SQRT(5))^n - (1 - SQRT(5))^n] / [2^n * SQRT(5)]
3. GCD(F(m), F(n)) = F(GCD(m,n))

References

• http://en.wikipedia.org/wiki/Fibonacci_number
• http://en.wikipedia.org/wiki/Pisano_period