100 Fibonacci numbers

Crop Image

×

Crop

Generate 100 Fibonacci numbers

We can do this two ways:

1) Recursive Algorithm

2) Binet's Formula

Recursive Algorithm:

F_n = F_{n - 1} + F_{n - 2}

where F₀ = 0 and F₁ = 1

Show Fibonacci Formula:

N/A + 0

N/A + 1

1 + 0 + 1

1 + 1 + 2

2 + 1 + 3

3 + 2 + 5

5 + 3 + 8

8 + 5 + 13

13 + 8 + 21

21 + 13 + 34

34 + 21 + 55

55 + 34 + 89

89 + 55 + 144

144 + 89 + 233

233 + 144 + 377

377 + 233 + 610

610 + 377 + 987

987 + 610 + 1,597

1,597 + 987 + 2,584

2,584 + 1,597 + 4,181

4,181 + 2,584 + 6,765

6,765 + 4,181 + 10,946

10,946 + 6,765 + 17,711

17,711 + 10,946 + 28,657

28,657 + 17,711 + 46,368

46,368 + 28,657 + 75,025

75,025 + 46,368 + 121,393

121,393 + 75,025 + 196,418

196,418 + 121,393 + 317,811

317,811 + 196,418 + 514,229

514,229 + 317,811 + 832,040

832,040 + 514,229 + 1,346,269

1,346,269 + 832,040 + 2,178,309

2,178,309 + 1,346,269 + 3,524,578

3,524,578 + 2,178,309 + 5,702,887

5,702,887 + 3,524,578 + 9,227,465

9,227,465 + 5,702,887 + 14,930,352

14,930,352 + 9,227,465 + 24,157,817

24,157,817 + 14,930,352 + 39,088,169

39,088,169 + 24,157,817 + 63,245,986

63,245,986 + 39,088,169 + 102,334,155

102,334,155 + 63,245,986 + 165,580,141

165,580,141 + 102,334,155 + 267,914,296

267,914,296 + 165,580,141 + 433,494,437

433,494,437 + 267,914,296 + 701,408,733

701,408,733 + 433,494,437 + 1,134,903,170

1,134,903,170 + 701,408,733 + 1,836,311,903

1,836,311,903 + 1,134,903,170 + 2,971,215,073

2,971,215,073 + 1,836,311,903 + 4,807,526,976

4,807,526,976 + 2,971,215,073 + 7,778,742,049

7,778,742,049 + 4,807,526,976 + 12,586,269,025

12,586,269,025 + 7,778,742,049 + 20,365,011,074

20,365,011,074 + 12,586,269,025 + 32,951,280,099

32,951,280,099 + 20,365,011,074 + 53,316,291,173

53,316,291,173 + 32,951,280,099 + 86,267,571,272

86,267,571,272 + 53,316,291,173 + 139,583,862,445

139,583,862,445 + 86,267,571,272 + 225,851,433,717

225,851,433,717 + 139,583,862,445 + 365,435,296,162

365,435,296,162 + 225,851,433,717 + 591,286,729,879

591,286,729,879 + 365,435,296,162 + 956,722,026,041

956,722,026,041 + 591,286,729,879 + 1,548,008,755,920

1,548,008,755,920 + 956,722,026,041 + 2,504,730,781,961

2,504,730,781,961 + 1,548,008,755,920 + 4,052,739,537,881

4,052,739,537,881 + 2,504,730,781,961 + 6,557,470,319,842

6,557,470,319,842 + 4,052,739,537,881 + 10,610,209,857,723

10,610,209,857,723 + 6,557,470,319,842 + 17,167,680,177,565

17,167,680,177,565 + 10,610,209,857,723 + 27,777,890,035,288

27,777,890,035,288 + 17,167,680,177,565 + 44,945,570,212,853

44,945,570,212,853 + 27,777,890,035,288 + 72,723,460,248,141

72,723,460,248,141 + 44,945,570,212,853 + 117,669,030,460,994

117,669,030,460,994 + 72,723,460,248,141 + 190,392,490,709,135

190,392,490,709,135 + 117,669,030,460,994 + 308,061,521,170,129

308,061,521,170,129 + 190,392,490,709,135 + 498,454,011,879,264

498,454,011,879,264 + 308,061,521,170,129 + 806,515,533,049,393

806,515,533,049,393 + 498,454,011,879,264 + 1,304,969,544,928,657

1,304,969,544,928,657 + 806,515,533,049,393 + 2,111,485,077,978,050

2,111,485,077,978,050 + 1,304,969,544,928,657 + 3,416,454,622,906,707

3,416,454,622,906,707 + 2,111,485,077,978,050 + 5,527,939,700,884,757

5,527,939,700,884,757 + 3,416,454,622,906,707 + 8,944,394,323,791,464

8,944,394,323,791,464 + 5,527,939,700,884,757 + 14,472,334,024,676,220

14,472,334,024,676,220 + 8,944,394,323,791,464 + 23,416,728,348,467,684

23,416,728,348,467,684 + 14,472,334,024,676,220 + 37,889,062,373,143,904

37,889,062,373,143,904 + 23,416,728,348,467,684 + 61,305,790,721,611,592

61,305,790,721,611,592 + 37,889,062,373,143,904 + 99,194,853,094,755,504

99,194,853,094,755,504 + 61,305,790,721,611,592 + 160,500,643,816,367,104

160,500,643,816,367,104 + 99,194,853,094,755,504 + 259,695,496,911,122,592

259,695,496,911,122,592 + 160,500,643,816,367,104 + 420,196,140,727,489,664

420,196,140,727,489,664 + 259,695,496,911,122,592 + 679,891,637,638,612,224

679,891,637,638,612,224 + 420,196,140,727,489,664 + 1,100,087,778,366,101,888

1,100,087,778,366,101,888 + 679,891,637,638,612,224 + 1,779,979,416,004,714,240

1,779,979,416,004,714,240 + 1,100,087,778,366,101,888 + 2,880,067,194,370,816,000

2,880,067,194,370,816,000 + 1,779,979,416,004,714,240 + 4,660,046,610,375,530,496

4,660,046,610,375,530,496 + 2,880,067,194,370,816,000 + 7,540,113,804,746,346,496

7,540,113,804,746,346,496 + 4,660,046,610,375,530,496 + 12,200,160,415,121,876,992

12,200,160,415,121,876,992 + 7,540,113,804,746,346,496 + 19,740,274,219,868,225,536

19,740,274,219,868,225,536 + 12,200,160,415,121,876,992 + 31,940,434,634,990,100,480

31,940,434,634,990,100,480 + 19,740,274,219,868,225,536 + 51,680,708,854,858,326,016

51,680,708,854,858,326,016 + 31,940,434,634,990,100,480 + 83,621,143,489,848,426,496

83,621,143,489,848,426,496 + 51,680,708,854,858,326,016 + 135,301,852,344,706,760,704

135,301,852,344,706,760,704 + 83,621,143,489,848,426,496 + 218,922,995,834,555,203,584

Use Binet's Formula

F_n = 1/√5(((1 + √5)/2)ⁿ - ((1 - √5)/2)ⁿ)

Given n = 99, we have:

F₉₉ = 0.44721359549996 * ((3.2360679774998/2)⁹⁹ - (-1.2360679774998/2)⁹⁹)

F₉₉ = 0.44721359549996 * ((1.6180339887499)⁹⁹ - (-0.61803398874989)⁹⁹)

F₉₉ = 0.44721359549996 * (4.8952670052397E+20 - -2.0427894922374E-21)

F₉₉ = 0.44721359549996 * 4.8952670052397E+20

Final Answer