Finding out nth fibonacci number for very large 'n'
AlgorithmMathFibonacciAlgorithm Problem Overview
I was wondering about how can one find the nth term of fibonacci sequence for a very large value of n say, 1000000. Using the grade-school recurrence equation fib(n)=fib(n-1)+fib(n-2), it takes 2-3 min to find the 50th term!
After googling, I came to know about Binet's formula but it is not appropriate for values of n>79 as it is said here
Is there an algorithm to do so just like we have for finding prime numbers?
Algorithm Solutions
Solution 1 - Algorithm
You can use the matrix exponentiation method (linear recurrence method). You can find detailed explanation and procedure in this or this blog. Run time is O(log n).
I don't think there is a better way of doing this.
Solution 2 - Algorithm
You can save a lot time by use of memoization. For example, compare the following two versions (in JavaScript):
Version 1: normal recursion
var fib = function(n) {
return n < 2 ? n : fib(n - 1) + fib(n - 2);
};
Version 2: memoization
A. take use of underscore library
var fib2 = _.memoize(function(n) {
return n < 2 ? n : fib2(n - 1) + fib2(n - 2);
});
B. library-free
var fib3 = (function(){
var memo = {};
return function(n) {
if (memo[n]) {return memo[n];}
return memo[n] = (n <= 2) ? 1 : fib3(n-2) + fib3(n-1);
};
})();
The first version takes over 3 minutes for n = 50 (on Chrome), while the second only takes less than 5ms! You can check this in the jsFiddle.
It's not that surprising if we know version 1's time complexity is exponential (O(2N/2)), while version 2's is linear (O(N)).
Version 3: matrix multiplication
Furthermore, we can even cut down the time complexity to O(log(N)) by computing the multiplication of N matrices.
where Fn denotes the nth term of Fibonacci sequence.
Solution 3 - Algorithm
I agree with Wayne Rooney's answer that the optimal solution will complete in O(log n) steps, however the overall run-time complexity will depend upon the complexity of the multiplication algorithm used. Using Karatsuba Multiplication, for example, the overall run-time complexity would be O(nlog23) ≈ O(n1.585).1
However, matrix exponentiation isn't necessarily the best way to go about it. As a developer at Project Nayuki has noticed, matrix exponentiation carries with it redundant calculations, which can be removed. From the author's description:
> Given Fk and Fk+1, we can calculate these:
>
>
>
Note that this requires only 3 BigInt-to-BigInt multiplications per split, rather than 8 as matrix exponentiation would.
We can still do slightly better than this, though. One of the most elegant Fibonacci identities is related to the Lucas Numbers:
where Ln is the nth Lucas Number. This identity can be further generalized as:
There's a few more-or-less equivalent ways to proceed recursively, but the most logical seems to be on Fn and Ln. Further identities used in the implementation below can either be found or derived from the identities listed for Lucas Sequences:
Proceeding in this way requires only two BigInt-to-BigInt multiplications per split, and only one for the final result. This is about 20% faster than the code provided by Project Nayuki (test script). Note: the original source has been modified (improved) slightly to allow a fair comparison.
def fibonacci(n):
def fib_inner(n):
'''Returns F[n] and L[n]'''
if n == 0:
return 0, 2
u, v = fib_inner(n >> 1)
q = (n & 2) - 1
u, v = u * v, v * v + 2*q
if (n & 1):
u1 = (u + v) >> 1
return u1, 2*u + u1
return u, v
u, v = fib_inner(n >> 1)
if (n & 1):
q = (n & 2) - 1
u1 = (u + v) >> 1
return v * u1 + q
return u * v
Update
A greybeard points out, the above result has already been improved upon by Takahashi (2000)2, by noting that BigInt squaring is generally (and specifically for the Schönhage-Strassen algorithm) less computationally expensive than BigInt multiplication. The author suggestions an iteration, splitting on Fn and Ln, using the following identities:
Iterating in this way will require two BigInt squares per split, rather than a BigInt square and a BigInt multiplication as above. As expected, the run-time is measurably faster than the above implementation for very large n, but is somewhat slower for small values (n < 25000).
However, this can be improved upon slightly as well. The author claims that, "It is known that the Product of Lucas Numbers algorithm uses the fewest bit operations to compute the Fibonacci number Fn." The author then elects to adapt the Product of Lucas Numbers algorithm, which at the time was the fastest known, splitting on Fn and Ln. Note, however, that Ln is only ever used in the computation of Fn+1. This seems a somewhat wasteful, if one considers the following identities:
where the first is taken directly from Takahashi, the second is a result of the matrix exponentiation method (also noted by Nayuki), and the third is the result of adding the previous two. This allows an obvious split on Fn and Fn+1. The result requires one less BigInt addition, and, importantly, one less division by 2 for even n; for odd n the benefit is doubled. In practice this is signifcantly faster than the method proposed by Takahashi for small n (10-15% faster), and marginally faster for very large n (test script).
def fibonacci(n):
def fib_inner(n):
'''Returns F[n] and F[n+1]'''
if n == 0:
return 0, 1
u, v = fib_inner(n >> 1)
q = (n & 2) - 1
u *= u
v *= v
if (n & 1):
return u + v, 3*v - 2*(u - q)
return 2*(v + q) - 3*u, u + v
u, v = fib_inner(n >> 1)
# L[m]
l = 2*v - u
if (n & 1):
q = (n & 2) - 1
return v * l + q
return u * l
Update 2
Since originally posting, I've improved upon the previous result slightly as well. Aside from the two BigInt squares, splitting on Fn and Fn+1 also has an overhead of three BigInt additions and two small constant multiplications per split. This overhead can be eliminated almost entirely by splitting on Ln and Ln+1 instead:
Splitting in this way requires two BigInt squares as before, but only a single BigInt addition. These values need to be related back to the corresponding Fibonacci number, though. Fortunately, this can be achieved with a single division by 5:
Because the quotient is known to be integer, an exact division method such as GMP's mpz_divexact_ui can be used. Unrolling the outermost split allows us to then compute the final value with a single multiplication:
As implemented in Python, this is noticably faster than the previous implementation for small n (5-10% faster) and marginally faster for very large n (test script).
def fibonacci(n):
def fib_inner(n):
'''Returns L[n] and L[n+1]'''
if n == 0:
return mpz(2), mpz(1)
m = n >> 1
u, v = fib_inner(m)
q = (2, -2)[m & 1]
u = u * u - q
v = v * v + q
if (n & 1):
return v - u, v
return u, v - u
m = n >> 1
u, v = fib_inner(m)
# F[m]
f = (2*v - u) / 5
if (n & 1):
q = (n & 2) - 1
return v * f - q
return u * f
1 It can be seen that the number of digits (or bits) of Fn ~ O(n) as:
The runtime complexity using Karatsuba Multiplication can then be calculated as:
2 Takahashi, D. (2000), "A fast algorithm for computing large Fibonacci numbers" (PDF), Information Processing Letters 75, pp. 243–246.
Solution 4 - Algorithm
Use recurrence identities http://en.wikipedia.org/wiki/Fibonacci_number#Other_identities to find n-th number in log(n) steps. You will have to use arbitrary precision integers for that. Or you can calculate the precise answer modulo some factor by using modular arithmetic at each step.
Noticing that 3n+3 == 3(n+1), we can devise a single-recursive function which calculates two sequential Fibonacci numbers at each step dividing the n by 3 and choosing the appropriate formula according to the remainder value. IOW it calculates a pair @(3n+r,3n+r+1), r=0,1,2 from a pair @(n,n+1) in one step, so there's no double recursion and no memoization is necessary.
A Haskell code is here.
F(2n-1) = F(n-1)^2 + F(n)^2 === a' = a^2 + b^2
F(2n) = 2 F(n-1) F(n) + F(n)^2 === b' = 2ab + b^2
seems to lead to faster code. Using "Lucas sequence identities" might be the fastest (this is due to user:primo, who cites this implementation).
Solution 5 - Algorithm
Most of the people already gave you link explaining the finding of Nth Fibonacci number, by the way Power algorithm works the same with minor change.
Anyways this is my O(log N) solution.
package algFibonacci;
import java.math.BigInteger;
public class algFibonacci {
// author Orel Eraki
// Fibonacci algorithm
// O(log2 n)
public static BigInteger Fibonacci(int n) {
int num = Math.abs(n);
if (num == 0) {
return BigInteger.ZERO;
}
else if (num <= 2) {
return BigInteger.ONE;
}
BigInteger[][] number = { { BigInteger.ONE, BigInteger.ONE }, { BigInteger.ONE, BigInteger.ZERO } };
BigInteger[][] result = { { BigInteger.ONE, BigInteger.ONE }, { BigInteger.ONE, BigInteger.ZERO } };
while (num > 0) {
if (num%2 == 1) result = MultiplyMatrix(result, number);
number = MultiplyMatrix(number, number);
num/= 2;
}
return result[1][1].multiply(BigInteger.valueOf(((n < 0) ? -1:1)));
}
public static BigInteger[][] MultiplyMatrix(BigInteger[][] mat1, BigInteger[][] mat2) {
return new BigInteger[][] {
{
mat1[0][0].multiply(mat2[0][0]).add(mat1[0][1].multiply(mat2[1][0])),
mat1[0][0].multiply(mat2[0][1]).add(mat1[0][1].multiply(mat2[1][1]))
},
{
mat1[1][0].multiply(mat2[0][0]).add(mat1[1][1].multiply(mat2[1][0])),
mat1[1][0].multiply(mat2[0][1]).add(mat1[1][1].multiply(mat2[1][1]))
}
};
}
public static void main(String[] args) {
System.out.println(Fibonacci(8181));
}
}
Solution 6 - Algorithm
For calculating arbitrarily large elements of the Fibonacci sequence, you're going to have to use the closed-form solution -- Binet's formula, and use arbitrary-precision math to provide enough precision to calculate the answer.
Just using the recurrence relation, though, should not require 2-3 minutes to calculate the 50th term -- you should be able to calculate terms out into the billions within a few seconds on any modern machine. It sounds like you're using the fully-recursive formula, which does lead to a combinatorial explosion of recursive calculations. The simple iterative formula is much faster.
To wit: the recursive solution is:
int fib(int n) {
if (n < 2)
return 1;
return fib(n-1) + fib(n-2)
}
... and sit back and watch the stack overflow.
The iterative solution is:
int fib(int n) {
if (n < 2)
return 1;
int n_1 = 1, n_2 = 1;
for (int i = 2; i <= n; i += 1) {
int n_new = n_1 + n_2;
n_1 = n_2;
n_2 = n_new;
}
return n_2;
}
Notice how we're essentially calculating the next term n_new from previous terms n_1 and n_2, then "shuffling" all the terms down for the next iteration. With a running time linear on the value of n, it's a matter of a few seconds for n in the billions (well after integer overflow for your intermediate variables) on a modern gigahertz machine.
Solution 7 - Algorithm
For calculating the Fibonacci numbers, the recursive algorithm is one of the worst way. By simply adding the two previous numbers in a for cycle (called iterative method) will not take 2-3 minutes, to calculate the 50th element.
Solution 8 - Algorithm
Here's a python version to compute nth Fibonacci number in O(log(n))
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
def matmul(M1, M2):
a11 = M1[0][0]*M2[0][0] + M1[0][1]*M2[1][0]
a12 = M1[0][0]*M2[0][1] + M1[0][1]*M2[1][1]
a21 = M1[1][0]*M2[0][0] + M1[1][1]*M2[1][0]
a22 = M1[1][0]*M2[0][1] + M1[1][1]*M2[1][1]
return [[a11, a12], [a21, a22]]
def matPower(mat, p):
if p == 1:
return mat
m2 = matPower(mat, p//2)
if p % 2 == 0:
return matmul(m2, m2)
else:
return matmul(matmul(m2, m2),mat)
Q = [[1,1],[1,0]]
q_final = matPower(Q, n-1)
return q_final[0][0]
Solution 9 - Algorithm
I wrote a C implementation, that support any scale of input number with GNU gmp.
The time to figure fib for a single number is O(n), and space for cache is O(1), (it actually figured all fib for 0 ~ n).
Code
fib_cached_gmp.c:
// fibonacci - cached algorithm - any scale of input with GMP,
#include <gmp.h>
#include <stdio.h>
#include <stdlib.h>
// a single step,
void fib_gmp_next(mpz_t *cache) {
mpz_add(cache[2], cache[0], cache[1]);
mpz_set(cache[0], cache[1]);
mpz_set(cache[1], cache[2]);
}
// figure fib for a single number, in O(n),
mpz_t *fib_gmp(int n, mpz_t *result) {
// init cache,
mpz_t cache[3]; // number: [fib(n-2), fib(n-1), fib(n)],
mpz_init(cache[0]);
mpz_init(cache[1]);
mpz_init(cache[2]);
mpz_set_si(cache[0], 0);
mpz_set_si(cache[1], 1);
while (n >= 2) {
fib_gmp_next(cache);
n--;
}
mpz_set(*result, cache[n]);
return result;
}
// test - print fib from 0 to n, tip: cache won't be reused between any 2 input numbers,
void test_seq(int n) {
mpz_t result;
mpz_init(result);
for (int i = 0; i <= n; i++) {
gmp_printf("fib(%2d): %Zd\n", i, fib_gmp(i, &result));
}
}
// test - print fib for a single num,
void test_single(int x) {
mpz_t result;
mpz_init(result);
gmp_printf("fib(%d): %Zd\n", x, fib_gmp(x, &result));
}
int main() {
// test sequence,
test_seq(100);
// test single,
test_single(12345);
return 0;
}
Install gmp first:
// for Ubuntu,
sudo apt-get install libgmp3-dev
Compile:
gcc fib_cached_gmp.c -lgmp
Execute:
./a.out
Example output:
fib( 0): 0
fib( 1): 1
fib( 2): 1
fib( 3): 2
fib( 4): 3
fib( 5): 5
fib( 6): 8
fib( 7): 13
fib( 8): 21
fib( 9): 34
fib(10): 55
fib(11): 89
fib(12): 144
fib(13): 233
fib(14): 377
fib(15): 610
fib(16): 987
fib(17): 1597
fib(18): 2584
fib(19): 4181
fib(20): 6765
fib(21): 10946
fib(22): 17711
fib(23): 28657
fib(24): 46368
fib(25): 75025
fib(26): 121393
fib(27): 196418
fib(28): 317811
fib(29): 514229
fib(30): 832040
fib(31): 1346269
fib(32): 2178309
fib(33): 3524578
fib(34): 5702887
fib(35): 9227465
fib(36): 14930352
fib(37): 24157817
fib(38): 39088169
fib(39): 63245986
fib(40): 102334155
fib(41): 165580141
fib(42): 267914296
fib(43): 433494437
fib(44): 701408733
fib(45): 1134903170
fib(46): 1836311903
fib(47): 2971215073
fib(48): 4807526976
fib(49): 7778742049
fib(50): 12586269025
fib(51): 20365011074
fib(52): 32951280099
fib(53): 53316291173
fib(54): 86267571272
fib(55): 139583862445
fib(56): 225851433717
fib(57): 365435296162
fib(58): 591286729879
fib(59): 956722026041
fib(60): 1548008755920
fib(61): 2504730781961
fib(62): 4052739537881
fib(63): 6557470319842
fib(64): 10610209857723
fib(65): 17167680177565
fib(66): 27777890035288
fib(67): 44945570212853
fib(68): 72723460248141
fib(69): 117669030460994
fib(70): 190392490709135
fib(71): 308061521170129
fib(72): 498454011879264
fib(73): 806515533049393
fib(74): 1304969544928657
fib(75): 2111485077978050
fib(76): 3416454622906707
fib(77): 5527939700884757
fib(78): 8944394323791464
fib(79): 14472334024676221
fib(80): 23416728348467685
fib(81): 37889062373143906
fib(82): 61305790721611591
fib(83): 99194853094755497
fib(84): 160500643816367088
fib(85): 259695496911122585
fib(86): 420196140727489673
fib(87): 679891637638612258
fib(88): 1100087778366101931
fib(89): 1779979416004714189
fib(90): 2880067194370816120
fib(91): 4660046610375530309
fib(92): 7540113804746346429
fib(93): 12200160415121876738
fib(94): 19740274219868223167
fib(95): 31940434634990099905
fib(96): 51680708854858323072
fib(97): 83621143489848422977
fib(98): 135301852344706746049
fib(99): 218922995834555169026
fib(100): 354224848179261915075
fib(12345): 400805695072240470970514993214065752192289440772063392234116121035966330621821050108284603033716632771086638046166577665205834362327397885009536790892524821512145173749742393351263429067658996935575930135482780507243981402150702461932551227590433713277255705297537428017957026536279252053237729028633507123483103210846617774763936154673522664591736081039709294423865668046925492747583953758325850613548914282578320544573036249175099094644435323970587790740267131607004023987409385716162460955707793257532112771932704816713519196128834470721836094265012918046427449156654067195071358955104097973710150920536847877434256779886729555691213282504703193401739340461924048504866698176130757935914248753973087073009601101912877383634628929467608983980664185363370286731771712542583041365328648124549323878806758395652340861186334027392307091079257180835672989798524084534677252369585918458720952520972332496025465803523315515681084895362126005441170936820059518262349022456888758938672920855739736423917065122816343192172271301981007636070751378441363091187289522144227851382197807194256392294919912037019476582418451273767976783751999133072126657949249799858935787018952232743400610036315564885371356712960608966755186612620425868892621106627825137425386831657368826398245606147944273998498356443362170133234924531673939303668042878258282104212769625245680321344034442698232414181912301904509531018692483863038992377680591406376081935756597411807864832452421993121459549055042253305545594009110753730302061881025182053074077930494574304284381890534053065639084253641881363463311184024281835265103884539012874542416238100890688593076189105555658375552988619203325356676814545718066196038345684671830102920209857682912971565838896011294918349088792184108318689299230788355618638040186790724351073650210514429114905535411044888774713860041341593318365792673354888566799196442017231870631867558530906286613228902689695061557951752309687806567573290910909535395758148994377158637050112347651517847188123790794231572729345617619677555583207012253101701328971768827861922408064379891201972881554890367344239218306050355964382953279316318309272212482218232309006973312977359562553184608144571713073802285675503209229581312057259729362382786183100343961484090866057560474044189870633912200595478051573769889968342203512550302655117491740823696686983281784153050366346823513213598551985596176977626982962058849363351794302206703907577970065793839511591930741441079234179943480206539767561244271325923343752071038968002157889912694947204003637791271084190929058369801531787887444598295425899927970
Tips:
- Ｔhe
test_seq()is not very smart, it didn't reuse the cache between 2 input number.
While actually a single call tofib_gmp()would be enough, if you add agmp_printf()tofib_gmp_next()and provide the i tofib_gmp_next()in each step.
Anyhow, it's just for demo.
Solution 10 - Algorithm
First, you can formed an idea of the highest term from largest known Fibonacci term. also see stepping through recursive Fibonacci function presentation. A interested approach about this subject is in this article. Also, try to read about it in the worst algorithm in the world?.
Solution 11 - Algorithm
I solved a UVA problems: 495 - Fibonacci Freeze
It generate all Fibonacci numbers up to 5000th and print outputs for given inputs (range 1st - 5000th).
It is accepted with run-time 00.00 sec.
The Fibonacci number for 5000 is:
3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125
#include<stdio.h>
#include<string.h>
#define LIMIT 5001
#define MAX 1050
char num[LIMIT][MAX];
char result[MAX];
char temp[MAX];
char* sum(char str1[], char str2[])
{
int len1 = strlen(str1);
int len2 = strlen(str2);
int minLen, maxLen;
int i, j, k;
if (len1 > len2)
minLen = len2, maxLen = len1;
else
minLen = len1, maxLen = len2;
int carry = 0;
for (k = 0, i = len1 - 1, j = len2 - 1; k<minLen; k++, i--, j--)
{
int val = (str1[i] - '0') + (str2[j] - '0') + carry;
result[k] = (val % 10) + '0';
carry = val / 10;
}
while (k < len1)
{
int val = str1[i] - '0' + carry;
result[k] = (val % 10) + '0';
carry = val / 10;
k++; i--;
}
while (k < len2)
{
int val = str2[j] - '0' + carry;
result[k] = (val % 10) + '0';
carry = val / 10;
k++; j--;
}
if (carry > 0)
{
result[maxLen] = carry + '0';
maxLen++;
result[maxLen] = '\0';
}
else
{
result[maxLen] = '\0';
}
i = 0;
while (result[--maxLen])
{
temp[i++] = result[maxLen];
}
temp[i] = '\0';
return temp;
}
void generateFibonacci()
{
int i;
num[0][0] = '0'; num[0][1] = '\0';
num[1][0] = '1'; num[1][1] = '\0';
for (i = 2; i <= LIMIT; i++)
{
strcpy(num[i], sum(num[i - 1], num[i - 2]));
}
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int N;
generateFibonacci();
while (scanf("%d", &N) == 1)
{
printf("The Fibonacci number for %d is %s\n", N, num[N]);
}
return 0;
}
Solution 12 - Algorithm
The Simplest Pythonic Implementation can be given as follows
def Fib(n):
if (n < 0) :
return -1
elif (n == 0 ):
return 0
else:
a = 1
b = 1
for i in range(2,n+1):
a,b = b, a+b
return a
Solution 13 - Algorithm
More elegant solution in python
def fib(n):
if n == 0:
return 0
a, b = 0, 1
for i in range(2, n+1):
a, b = b, a+b
return b
Solution 14 - Algorithm
With some knowledge of discrete mathematics, you can find any Fibonacci number in constant time O(1). There is something called Linear Homogeneous Recurrence Relation.
Fibonacci sequence is an famous example.
To find the nth Fibonacci number we need to find that
We know that
where
Then, the Characteristic equation is
After finding the roots of the characteristic equation and substituting in the first equation
Finally, we need to find the value of both alpha 1 & alpha 2
Now, you can use this equation to find any Fibonacci number in O(1).
Solution 15 - Algorithm
I have a source code in c to calculate even 3500th fibonacci number :- for more details visit
http://codingloverlavi.blogspot.in/2013/04/fibonacci-series.html
source code in C :-
#include<stdio.h>
#include<conio.h>
#define max 2000
int arr1[max],arr2[max],arr3[max];
void fun(void);
int main()
{
int num,i,j,tag=0;
clrscr();
for(i=0;i<max;i++)
arr1[i]=arr2[i]=arr3[i]=0;
arr2[max-1]=1;
printf("ENTER THE TERM : ");
scanf("%d",&num);
for(i=0;i<num;i++)
{
fun();
if(i==num-3)
break;
for(j=0;j<max;j++)
arr1[j]=arr2[j];
for(j=0;j<max;j++)
arr2[j]=arr3[j];
}
for(i=0;i<max;i++)
{
if(tag||arr3[i])
{
tag=1;
printf("%d",arr3[i]);
}
}
getch();
return 1;
}
void fun(void)
{
int i,temp;
for(i=0;i<max;i++)
arr3[i]=arr1[i]+arr2[i];
for(i=max-1;i>0;i--)
{
if(arr3[i]>9)
{
temp=arr3[i];
arr3[i]%=10;
arr3[i-1]+=(temp/10);
}
}
}
Solution 16 - Algorithm
here is a short python code, works well upto 7 digits. Just requires a 3 element array
def fibo(n):
i=3
l=[0,1,1]
if n>2:
while i<=n:
l[i%3]= l[(i-1) % 3] + l[(i-2) % 3]
i+=1
return l[n%3]
Solution 17 - Algorithm
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
const long long int MAX = 10000000;
// Create an array for memoization
long long int f[MAX] = {0};
// Returns n'th fuibonacci number using table f[]
long long int fib(int n)
{
// Base cases
if (n == 0)
return 0;
if (n == 1 || n == 2)
return (f[n] = 1);
if (f[n])
return f[n];
long long int k = (n & 1)? (n+1)/2 : n/2;
f[n] = (n & 1)? (fib(k)*fib(k) + fib(k-1)*fib(k-1)) %MOD
: ((2*fib(k-1) + fib(k))*fib(k))%MOD;
return f[n];
}
int main()
{
long long int n = 1000000;
printf("%lld ", fib(n));
return 0;
}
Time complexity: O(Log n) as we divide the problem to half in every recursive call.
Solution 18 - Algorithm
Calculating fibonacci numbers (using Haskell):
Version 1: Direct translation of the definition to code (very slow version):
fib :: Integer -> Integer
fib 0 = 1
fib 1 = 1
fib n =
fib (n - 1) + fib (n - 2)
Version 2: Using the work we have done to calculate F_{n - 1} and F_{n - 2} (the fast version):
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
You can get the nth fibonacci by simply doing fibs !! n where n is the index.
Version 3: Using the matrix multiplicaiton technique. (the even faster version):
-- declaring a matrix
data Matrix = Matrix
( (Integer, Integer)
, (Integer, Integer)
)
deriving (Show, Eq)
-- creating it an instance of Num
-- so that if we implement (*) we get (^) for free
instance Num Matrix where
(*) = mMult
-- don't need these
(+) = undefined
negate = undefined
fromInteger = undefined
abs = undefined
signum = undefined
-- 2-d matrix multiplication
mMult :: Matrix -> Matrix -> Matrix
mMult (Matrix ((a11, a12), (a21, a22))) (Matrix ((b11, b12), (b21, b22))) =
Matrix
( (a11 * b11 + a12 * b21, a11 * b12 + a12 * b22)
, (a21 * b11 + a22 * b21, a21 * b12 + a22 * b22)
)
-- base matrix for generating fibonacci
fibBase :: Matrix
fibBase =
Matrix ((1,1), (1,0))
-- get the large fibonacci numbers
fastFib :: Int -> Integer
fastFib n =
let
getNth (Matrix ((_, a12), _)) = a12
in
getNth (fibBase ^ n)
Solution 19 - Algorithm
I have written a small code to compute Fibonacci for large number which is faster than conversational recursion way.
I am using memorizing technique to get last Fibonacci number instead of recomputing it.
public class FabSeries {
private static Map<BigInteger, BigInteger> memo = new TreeMap<>();
public static BigInteger fabMemorizingTech(BigInteger n) {
BigInteger ret;
if (memo.containsKey(n))
return memo.get(n);
else {
if (n.compareTo(BigInteger.valueOf(2)) <= 0)
ret = BigInteger.valueOf(1);
else
ret = fabMemorizingTech(n.subtract(BigInteger.valueOf(1))).add(
fabMemorizingTech(n.subtract(BigInteger.valueOf(2))));
memo.put(n, ret);
return ret;
}
}
public static BigInteger fabWithoutMemorizingTech(BigInteger n) {
BigInteger ret;
if (n.compareTo(BigInteger.valueOf(2)) <= 0)
ret = BigInteger.valueOf(1);
else
ret = fabWithoutMemorizingTech(n.subtract(BigInteger.valueOf(1))).add(
fabWithoutMemorizingTech(n.subtract(BigInteger.valueOf(2))));
return ret;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Enter Number");
BigInteger num = scanner.nextBigInteger();
// Try with memorizing technique
Long preTime = new Date().getTime();
System.out.println("Stats with memorizing technique ");
System.out.println("Fibonacci Value : " + fabMemorizingTech(num) + " ");
System.out.println("Time Taken : " + (new Date().getTime() - preTime));
System.out.println("Memory Map: " + memo);
// Try without memorizing technique.. This is not responsive for large
// value .. can 50 or so..
preTime = new Date().getTime();
System.out.println("Stats with memorizing technique ");
System.out.println("Fibonacci Value : " + fabWithoutMemorizingTech(num) + " ");
System.out.println("Time Taken : " + (new Date().getTime() - preTime));
}
}
> Enter Number
>
> 40
>
> Stats with memorizing technique
>
> Fibonacci Value : 102334155
>
> Time Taken : 5
>
> Memory Map: {1=1, 2=1, 3=2, 4=3, 5=5, 6=8, 7=13, 8=21, 9=34, 10=55, 11=89, 12=144, 13=233, 14=377, 15=610, 16=987, 17=1597, 18=2584, 19=4181, 20=6765, 21=10946, 22=17711, 23=28657, 24=46368, 25=75025, 26=121393, 27=196418, 28=317811, 29=514229, 30=832040, 31=1346269, 32=2178309, 33=3524578, 34=5702887, 35=9227465, 36=14930352, 37=24157817, 38=39088169, 39=63245986, 40=102334155}
>
> Stats without memorizing technique
>
> Fibonacci Value : 102334155
>
> Time Taken : 11558
Solution 20 - Algorithm
If you are using C# have a look at Lync and BigInteger. I tried this with 1000000 (actually 1000001 as I skip the first 1000000) and was below 2 minutes (00:01:19.5765).
public static IEnumerable<BigInteger> Fibonacci()
{
BigInteger i = 0;
BigInteger j = 1;
while (true)
{
BigInteger fib = i + j;
i = j;
j = fib;
yield return fib;
}
}
public static string BiggerFib()
{
BigInteger fib = Fibonacci().Skip(1000000).First();
return fib.ToString();
}
Solution 21 - Algorithm
This JavaScript implementation handles nthFibonacci(1200) no problemo:
var nthFibonacci = function(n) {
var arr = [0, 1];
for (; n > 1; n--) {
arr.push(arr.shift() + arr[0])
}
return arr.pop();
};
console.log(nthFibonacci(1200)); // 2.7269884455406272e+250
Solution 22 - Algorithm
I have done a program. It doesn't take long to calculate the values but the maximum term which can be displayed is the 1477th(because of the max range for double). Results appear almost instantly. The series starts from 0. If there are any improvements needed,please feel free to edit it.
#include<iostream>
using namespace std;
void fibseries(long int n)
{
long double x=0;
double y=1;
for (long int i=1;i<=n;i++)
{
if(i%2==1)
{
if(i==n)
{
cout<<x<<" ";
}
x=x+y;
}
else
{
if(i==n)
{
cout<<x<<" ";
}
y=x+y;
}
}
}
main()
{
long int n=0;
cout<<"The number of terms ";
cin>>n;
fibseries(n);
return 0;
}
Solution 23 - Algorithm
Just for the information:
The following formula seems working fine but depends on the preciseness of the number used-
> [((1+√5)/2)ⁿ- ((1-√5)/2)ⁿ]/√5
Note: Don't round-off the figures for more preciseness.
JS sample code:
let n = 74,
const sqrt5 = Math.sqrt(5);
fibNum = Math.round((Math.pow(((1+sqrt5)/2),n)- Math.pow(((1-sqrt5)/2),n))/sqrt5) ;
As per the Number Precision, it'll work fine on chrome console upto n=74
Open for any suggestion!
Another solution
Follows the steps-
- make a set of index and value and pervious value of fibonacci series at certain intervals. e.g each 50 or each 100.
- Find the nearest lower index of the desired number
nfrom the set of step-1. - Proceed in traditional way by adding the previous value in each subsequent one.
Note: It doesn't seems good, but if you really concern about time complexity, this solution is a hit. The max iterations will be equal to the interval as per step-1.
Conclusion:
- Fibonacci numbers are strongly related to the golden ratio: Binet's formula expresses the nth Fibonacci number in terms of n and the golden ratio, and implies that the ratio of two consecutive Fibonacci numbers tends to the golden ratio as n increases.
- In pure mathematics Binet's formula will give you the exact result every time. In real world computing there will be errors as the precision needed exceeds the precision used. Every real solution has the same problem with exceeding precision at some point.