15,742,973 members
Articles / Programming Languages / C#
Tip/Trick
Posted 23 Dec 2014

28.6K views
13 bookmarked

# Large Integer Fibonacci Numbers

Rate me:
This code provides a simple yet fast method of calculating very large Fibonacci numbers in an efficient manner (also Fib(i) modulo M).

## 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

C#
`Fibonacci.Fib(1000000);    `

Takes ~ 9169 milliseconds.

C#
`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:

C#
```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:

C#
```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:

C#
```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:

C#
```        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,000th Fibonacci number:

C#
`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

Written By
United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

 First Prev Next
 Impressive JustCodeForFun26-Dec-14 12:59 JustCodeForFun 26-Dec-14 12:59
 Re: Impressive Cryptonite26-Dec-14 13:10 Cryptonite 26-Dec-14 13:10
 Matrix multiplication vs simple addition Wiktor Wandachowicz26-Dec-14 11:58 Wiktor Wandachowicz 26-Dec-14 11:58
 Re: Matrix multiplication vs simple addition Cryptonite26-Dec-14 12:15 Cryptonite 26-Dec-14 12:15
 Comparison to other methods? ahagel24-Dec-14 10:29 ahagel 24-Dec-14 10:29
 Re: Comparison to other methods? Cryptonite26-Dec-14 6:53 Cryptonite 26-Dec-14 6:53
 Don't trim the fat Dennis Dykstra24-Dec-14 9:40 Dennis Dykstra 24-Dec-14 9:40
 Re: Don't trim the fat Cryptonite26-Dec-14 6:54 Cryptonite 26-Dec-14 6:54
 Improvement to IsProbablePrime LWessels24-Dec-14 2:28 LWessels 24-Dec-14 2:28
 Re: Improvement to IsProbablePrime Cryptonite24-Dec-14 5:43 Cryptonite 24-Dec-14 5:43
 Re: Improvement to IsProbablePrime LWessels24-Dec-14 22:27 LWessels 24-Dec-14 22:27
 Re: Improvement to IsProbablePrime Cryptonite26-Dec-14 13:36 Cryptonite 26-Dec-14 13:36
 Nice one Member 1133235423-Dec-14 20:12 Member 11332354 23-Dec-14 20:12
 Re: Nice one Cryptonite24-Dec-14 5:32 Cryptonite 24-Dec-14 5:32
 I agree. The code is supposed to be a simple "Tip/Trick". Pisano periods, GCDs, and totients just go too far outside the scope of this "Tip". It sounds like I need to shorten the article and trim the fat, so to speak.
 My vote of 5 Assil23-Dec-14 14:18 Assil 23-Dec-14 14:18
 Re: My vote of 5 Cryptonite24-Dec-14 5:33 Cryptonite 24-Dec-14 5:33
 Last Visit: 31-Dec-99 18:00     Last Update: 24-Sep-23 23:10 Refresh 1