Find Nth Fibonacci Number Java O Logn Solution

Task

Fibonacci sequence
You are encouraged to solve this task according to the task description, using any language you may know.

The Fibonacci sequence is a sequence F_n of natural numbers defined recursively:

                                    F₀              = 0                                                          F₁              = 1                                                          F_n              = F_n-1              + F_n-2, if n>1

Task

Write a function to generate the n^th Fibonacci number.

Solutions can be iterative or recursive (though recursive solutions are generally considered too slow and are mostly used as an exercise in recursion).

The sequence is sometimes extended into negative numbers by using a straightforward inverse of the positive definition:

                                    F_n              = F_n+2              - F_n+1, if n<0

support for negative n in the solution is optional.

Related tasks

Fibonacci n-step number sequences‎
Leonardo numbers

References

Wikipedia, Fibonacci number
Wikipedia, Lucas number
MathWorld, Fibonacci Number
Some identities for r-Fibonacci numbers
OEIS Fibonacci numbers
OEIS Lucas numbers

1 0815
2 11l
3 360 Assembly
- 3.1 using fullword integers
- 3.2 using packed decimals
4 6502 Assembly
5 8080 Assembly
6 8th
7 ABAP
- 7.1 Iterative
- 7.2 Impure Functional
8 ACL2
9 Action!
10 ActionScript
11 Ada
- 11.1 Recursive
- 11.2 Iterative, build-in integers
- 11.3 Iterative, long integers
- 11.4 Fast method using fast matrix exponentiation
12 AdvPL
- 12.1 Recursive
- 12.2 Iterative
13 Aime
14 ALGOL 60
15 ALGOL 68
- 15.1 Analytic
- 15.2 Iterative
- 15.3 Recursive
- 15.4 Generative
- 15.5 Array (Table) Lookup
16 ALGOL W
17 ALGOL-M
- 17.1 Iterative
- 17.2 Naively recursive
18 Alore
19 AntLang
20 Apex
21 APL
- 21.1 Naive Recursive
- 21.2 Array
- 21.3 Analytic
22 AppleScript
- 22.1 Imperative
- 22.2 Functional
23 Arendelle
24 ARM Assembly
25 ArnoldC
26 Arturo
- 26.1 Recursive
27 AsciiDots
28 ATS
- 28.1 Recursive
- 28.2 Iterative
- 28.3 Iterative and Verified
- 28.4 Matrix-based
29 AutoHotkey
- 29.1 Iterative
- 29.2 Recursive and iterative
30 AutoIt
- 30.1 Iterative
- 30.2 Recursive
31 AWK
32 Axe
33 Babel
34 bash
- 34.1 Iterative
- 34.2 Recursive
35 BASIC
- 35.1 Applesoft BASIC
- 35.2 BASIC256
- 35.3 Commodore BASIC
- 35.4 Integer BASIC
- 35.5 IS-BASIC
- 35.6 QBasic
  - 35.6.1 Iterative
  - 35.6.2 Recursive
  - 35.6.3 Array (Table) Lookup
  - 35.6.4 Fibonacci from Russia
- 35.7 Sinclair ZX81 BASIC
  - 35.7.1 Analytic
  - 35.7.2 Iterative
  - 35.7.3 Tail recursive
36 Batch File
37 Battlestar
38 BBC BASIC
39 bc
- 39.1 iterative
40 BCPL
41 beeswax
42 Befunge
43 Bracmat
- 43.1 Recursive
- 43.2 Iterative
44 Brainf***
45 Brat
- 45.1 Recursive
- 45.2 Tail Recursive
- 45.3 Memoization
46 Burlesque
47 C
- 47.1 Recursive
- 47.2 Iterative
- 47.3 Analytic
- 47.4 Generative
- 47.5 Fast method for a single large value
48 C#
- 48.1 Recursive
- 48.2 Tail-Recursive
- 48.3 Iterative
- 48.4 Eager-Generative
- 48.5 Lazy-Generative
- 48.6 Analytic
- 48.7 Matrix
- 48.8 Array (Table) Lookup
- 48.9 Arbitrary Precision
49 C++
- 49.1 Using Zeckendorf Numbers
- 49.2 Using Standard Template Library
50 Cat
51 Chapel
52 Chef
53 Clio
54 Clojure
- 54.1 Lazy Sequence
- 54.2 Iterative
- 54.3 Doubling Algorithm (Fast)
- 54.4 Recursive
- 54.5 Using core.async
55 CLU
56 CMake
57 COBOL
- 57.1 Iterative
- 57.2 Recursive
58 CoffeeScript
- 58.1 Analytic
- 58.2 Iterative
- 58.3 Recursive
59 Comefrom0x10
- 59.1 Iterative
60 Common Lisp
- 60.1 Iterative
- 60.2 Recursive
- 60.3 Alternate solution
- 60.4 Solution with methods and eql specializers
- 60.5 List-based iterative
- 60.6 List-based recursive
61 Computer/zero Assembly
62 Corescript
63 Cowgol
64 Crystal
- 64.1 Recursive
- 64.2 Iterative
- 64.3 Tail Recursive
- 64.4 Analytic
65 D
- 65.1 Matrix Exponentiation Version
- 65.2 Faster Version
66 Dart
67 Datalog
68 DBL
69 Dc
70 Delphi
- 70.1 Iterative
- 70.2 Recursive
- 70.3 Matrix
71 DIBOL-11
72 DWScript
73 Dyalect
74 E
75 EasyLang
76 EchoLisp
77 ECL
- 77.1 Analytic
78 EDSAC order code
79 Eiffel
80 Ela
81 Elena
- 81.1 Alternative version using yieldable method
82 Elixir
83 Elm
84 Emacs Lisp
- 84.1 version 1
- 84.2 version 2
85 Erlang
- 85.1 Recursive
- 85.2 Iterative
- 85.3 Iterative 2
86 ERRE
87 Euphoria
- 87.1 'Recursive' version
- 87.2 'Iterative' version
- 87.3 'Tail recursive' version
- 87.4 'Paper tape' version
88 Excel
- 88.1 LAMBDA
89 F#
90 Factor
- 90.1 Iterative
- 90.2 Recursive
- 90.3 Tail-Recursive
- 90.4 Matrix
91 Falcon
- 91.1 Iterative
- 91.2 Recursive
- 91.3 Tail Recursive
92 FALSE
93 Fancy
94 Fantom
95 Fermat
96 Fexl
97 FOCAL
98 Forth
99 Fortran
- 99.1 FORTRAN IV
- 99.2 FORTRAN 77
- 99.3 Recursive
- 99.4 Iterative
100 Free Pascal
101 FreeBASIC
102 Frink
103 FRISC Assembly
104 FunL
- 104.1 Recursive
- 104.2 Tail Recursive
- 104.3 Lazy List
- 104.4 Iterative
- 104.5 Binet's Formula
- 104.6 Matrix Exponentiation
105 Futhark
- 105.1 Iterative
106 FutureBasic
- 106.1 Iterative
107 Fōrmulæ
108 GAP
109 Gecho
110 GFA Basic
111 GML
112 Go
- 112.1 Recursive
- 112.2 Iterative
- 112.3 Iterative using a closure
- 112.4 Using a goroutine and channel
113 Groovy
- 113.1 Recursive
- 113.2 Iterative
- 113.3 Analytic
114 Harbour
- 114.1 Recursive
- 114.2 Iterative
115 Haskell
- 115.1 Analytic
- 115.2 Recursive
- 115.3 Recursive with Memoization
- 115.4 Recursive with Memoization using memoized library
- 115.5 Iterative
  - 115.5.1 With lazy lists
  - 115.5.2 As a fold
- 115.6 With matrix exponentiation
- 115.7 With recurrence relations
116 Haxe
- 116.1 Iterative
- 116.2 As Iterator
117 HicEst
118 Hoon
119 Hope
- 119.1 Recursive
- 119.2 Tail-recursive
- 119.3 With lazy lists
120 Hy
121 Icon and Unicon
122 IDL
- 122.1 Recursive
- 122.2 Iterative
- 122.3 Analytic
123 Idris
- 123.1 Analytic
- 123.2 Recursive
- 123.3 Iterative
- 123.4 Lazy
124 J
125 Java
- 125.1 Iterative
- 125.2 Recursive
- 125.3 Caching-recursive
- 125.4 Analytic
- 125.5 Tail-recursive
- 125.6 Streams
126 JavaScript
- 126.1 ES5
  - 126.1.1 Recursive
- 126.2 Iterative
  - 126.2.1 Memoization
  - 126.2.2 Y-Combinator
  - 126.2.3 Generators
- 126.3 ES6
  - 126.3.1 Memoized
127 Joy
- 127.1 Recursive
- 127.2 Iterative
128 jq
- 128.1 Recursive
- 128.2 Tail Recursive
- 128.3 Binet's Formula
- 128.4 Generator
129 Julia
- 129.1 Recursive
- 129.2 Iterative
- 129.3 Matrix form
130 K
- 130.1 Recursive
- 130.2 Recursive with memoization
- 130.3 Analytic
- 130.4 Sequence to n
131 Kabap
- 131.1 Sequence to n
132 Klingphix
133 Kotlin
134 L++
135 LabVIEW
136 lambdatalk
137 Lang5
138 langur
139 Lasso
140 Latitude
- 140.1 Recursive
- 140.2 Memoization
141 Lean
142 LFE
- 142.1 Recursive
- 142.2 Iterative
143 Liberty BASIC
- 143.1 Iterative/Recursive
- 143.2 Iterative/Negative
144 Lingo
- 144.1 Recursive
- 144.2 Iterative
- 144.3 Analytic
145 Lisaac
146 LiveCode
147 LLVM
148 Logo
149 LOLCODE
150 LSL
151 Lua
- 151.1 Recursive
- 151.2 Pedantic Recursive
- 151.3 Tail Recursive
- 151.4 Table Recursive
- 151.5 Table Recursive 2
- 151.6 Iterative
152 Luck
153 Lush
154 M2000 Interpreter
155 M4
156 MAD
157 Maple
158 Mathematica / Wolfram Language
159 MATLAB
- 159.1 Matrix
- 159.2 Iterative
- 159.3 Dramadah Matrix Method
- 159.4 Tartaglia/Pascal Triangle Method
160 Maxima
161 MAXScript
- 161.1 Iterative
- 161.2 Recursive
162 Mercury
- 162.1 fib.m
- 162.2 Iterative algorithm
- 162.3 Memoization
163 Metafont
164 Microsoft Small Basic
- 164.1 Iterative
- 164.2 Binet's Formula
165 min
166 MiniScript
167 MIPS Assembly
168 Mirah
169 МК-61/52
170 ML
- 170.1 Standard ML
  - 170.1.1 Tail Recursion
  - 170.1.2 Recursion
- 170.2 MLite
  - 170.2.1 Recursion
171 ML/I
172 Modula-2
173 Modula-3
- 173.1 Recursive
- 173.2 Iterative (with negatives)
174 Monicelli
175 MontiLang
176 MUMPS
- 176.1 Iterative
177 Nanoquery
- 177.1 Iterative
178 Nemerle
- 178.1 Recursive
- 178.2 Tail Recursive
179 NESL
- 179.1 Recursive
180 NetRexx
181 NewLISP
- 181.1 Iterative
- 181.2 Recursive
- 181.3 Matrix multiplication
- 181.4 With a stack
182 NGS
- 182.1 Iterative
183 Nial
- 183.1 Iterative
- 183.2 Recursive
- 183.3 Matrix
184 Nim
- 184.1 Analytic
- 184.2 Iterative
- 184.3 Recursive
- 184.4 Tail-recursive
- 184.5 Continuations
185 Nix
186 Oberon-2
187 Objeck
- 187.1 Recursive
188 Objective-C
- 188.1 Recursive
- 188.2 Iterative
189 OCaml
- 189.1 Iterative
- 189.2 Recursive
- 189.3 Arbitrary Precision
- 189.4 O(log(n)) with arbitrary precision
190 Octave
- 190.1 Recursive
- 190.2 Iterative
- 190.3 Analytic
- 190.4 Tail Recursive
191 Oforth
192 Ol
193 OPL
194 Order
- 194.1 Recursive
- 194.2 Memoization
195 Oz
- 195.1 Iterative
- 195.2 Recursive
- 195.3 Tail-recursive
- 195.4 Lazy-recursive
196 PARI/GP
- 196.1 Built-in
- 196.2 Matrix
- 196.3 Analytic
- 196.4 Algebraic
- 196.5 Combinatorial
- 196.6 Binary powering
- 196.7 Recursive
- 196.8 Anonymous recursion
- 196.9 Memoization
- 196.10 Iterative
- 196.11 Chebyshev
- 196.12 Anti-Hadamard matrix
- 196.13 Testing adjacent bits
- 196.14 One-by-one
197 Pascal
- 197.1 Analytic
- 197.2 Recursive
- 197.3 Iterative
- 197.4 Analytic2
198 Perl
- 198.1 Iterative
- 198.2 Recursive
- 198.3 Modules
199 Phix
200 Phixmonti
201 PHP
- 201.1 Iterative
- 201.2 Recursive
202 PicoLisp
- 202.1 Recursive
- 202.2 Recursive with Cache
- 202.3 Iterative
- 202.4 Coroutines
203 Pike
- 203.1 Iterative
- 203.2 Recursive
204 PIR
205 PL/I
206 PL/M
207 PL/pgSQL
- 207.1 Recursive
- 207.2 Calculated
- 207.3 Linear
- 207.4 Tail recursive
208 PL/SQL
209 Plain English
210 Pop11
211 PostScript
212 Potion
- 212.1 Recursive
- 212.2 Iterative
- 212.3 Matrix based
- 212.4 Handling negative values
213 PowerBASIC
214 PowerShell
- 214.1 Iterative
- 214.2 Recursive
215 Processing
216 Prolog
- 216.1 Poor man's memoization
- 216.2 Continuation passing style
- 216.3 With lazy lists
- 216.4 Generators idiom
- 216.5 Yet another implementation
- 216.6 Efficient implementation
217 Pure
- 217.1 Tail Recursive
218 PureBasic
- 218.1 Macro based calculation
- 218.2 Recursive
- 218.3 Recursive & optimized with a static hash table
219 Purity
220 Python
- 220.1 Analytic
- 220.2 Iterative
  - 220.2.1 Iterative positive and negative
- 220.3 Recursive
- 220.4 Recursive with Memoization
- 220.5 Better Recursive doesn't need Memoization
- 220.6 Generative
  - 220.6.1 Example use
- 220.7 Matrix-Based
- 220.8 Large step recurrence
- 220.9 Same as above but slightly faster
- 220.10 Generative with Recursion
- 220.11 As a scan or a fold
  - 220.11.1 itertools.accumulate
  - 220.11.2 functools.reduce
- 220.12 Array and Range
221 QB64
222 Qi
- 222.1 Recursive
- 222.2 Iterative
223 Quackery
224 R
- 224.1 Iterative positive and negative
- 224.2 Other methods
225 Ra
226 Racket
- 226.1 Tail Recursive
- 226.2 Matrix Form
227 Raku
- 227.1 List Generator
- 227.2 Iterative
- 227.3 Recursive
228 RASEL
229 Red
230 Relation
231 Retro
- 231.1 Recursive
- 231.2 Iterative
232 REXX
233 Ring
234 Rockstar
- 234.1 Iterative (minimized)
- 234.2 Iterative (idiomatic)
- 234.3 Recursive
235 Ruby
- 235.1 Iterative
- 235.2 Recursive
- 235.3 Recursive with Memoization
- 235.4 Matrix
- 235.5 Generative
- 235.6 Binet's Formula
236 Run BASIC
237 Rust
- 237.1 Iterative
- 237.2 Recursive
- 237.3 Recursive (with pattern matching)
- 237.4 Tail recursive (with pattern matching)
- 237.5 Analytic
- 237.6 Using an Iterator
  - 237.6.1 Iterator "Successors"
238 S-BASIC
239 SAS
- 239.1 Iterative
- 239.2 Naive recursive
240 Sather
241 Scala
- 241.1 Recursive
- 241.2 Lazy sequence
- 241.3 Tail recursive
- 241.4 foldLeft
- 241.5 Iterator
242 Scheme
- 242.1 Iterative
- 242.2 Recursive
- 242.3 Recursive Sequence Generator
- 242.4 Dijkstra Algorithm
243 Scilab
244 sed
245 Seed7
- 245.1 Recursive
- 245.2 Iterative
246 SequenceL
- 246.1 Recursive
- 246.2 Tail Recursive
- 246.3 Matrix
247 SETL
248 Shen
249 Sidef
- 249.1 Iterative
- 249.2 Recursive
- 249.3 Recursive with memoization
- 249.4 Closed-form
- 249.5 Built-in
250 Simula
251 SkookumScript
- 251.1 Built-in
- 251.2 Recursive
- 251.3 Iterative
252 Slate
253 Smalltalk
254 smart BASIC
255 SNOBOL4
- 255.1 Recursive
- 255.2 Tail-recursive
- 255.3 Iterative
- 255.4 Analytic
256 SNUSP
- 256.1 Iterative
- 256.2 Recursive
257 Softbridge BASIC
- 257.1 Iterative
258 Spin
- 258.1 Iterative
259 SPL
- 259.1 Analytic
- 259.2 Iterative
- 259.3 Recursive
260 SQL
- 260.1 Analytic
- 260.2 Recursive
261 SSEM
262 Stata
- 262.1 Mata
263 StreamIt
264 SuperCollider
- 264.1 Recursive
- 264.2 Analytic
- 264.3 Iterative
265 Swift
- 265.1 Analytic
- 265.2 Iterative
- 265.3 Recursive
266 Tailspin
- 266.1 Recursive simple
- 266.2 Iterative, mutable state
- 266.3 State machine
267 Tcl
- 267.1 Simple Version
  - 267.1.1 Iterative
  - 267.1.2 Recursive
  - 267.1.3 Tail-Recursive
- 267.2 Handling Negative Numbers
  - 267.2.1 Iterative
  - 267.2.2 Recursive
- 267.3 For the Mathematically Inclined
268 Tern
- 268.1 Recursive
- 268.2 Coroutine
269 TI-83 BASIC
270 TI-89 BASIC
- 270.1 Recursive
- 270.2 Iterative
271 Tiny BASIC
272 TSE SAL
273 Turing
274 TUSCRIPT
275 UNIX Shell
276 UnixPipes
277 Ursa
- 277.1 Iterative
278 Ursala
279 V
280 Vala
- 280.1 Recursive
- 280.2 Iterative
281 VAX Assembly
282 VBA
283 VBScript
- 283.1 Non-recursive, object oriented, generator
  - 283.1.1 Class Definition:
  - 283.1.2 Invocation:
  - 283.1.3 Output:
284 Vedit macro language
- 284.1 Iterative
- 284.2 Unlimited precision
285 Visual Basic
286 Visual Basic .NET
- 286.1 Iterative
- 286.2 Recursive
- 286.3 BigInteger
- 286.4 BigInteger, speedier method
287 Vlang
- 287.1 Iterative
- 287.2 Recursive
288 Wart
- 288.1 Recursive, all at once
- 288.2 Recursive, using cases
- 288.3 Recursive, using memoization
289 WDTE
- 289.1 Memoized Recursive
- 289.2 Iterative
290 WebAssembly
291 Whitespace
- 291.1 Iterative
- 291.2 Recursive
292 Wrapl
- 292.1 Generator
- 292.2 Iterator
293 Wren
294 x86 Assembly
295 xEec
296 XLISP
- 296.1 Analytic
- 296.2 Tail recursive
297 Xojo
298 XPL0
299 XQuery
300 zkl
301 ZX Spectrum Basic
- 301.1 Iterative
- 301.2 Analytic

0815 [edit]


%<:0D:>~$<:01:~%>=<:a94fad42221f2702:>~>
}:_s:{x{={~$x+%{=>~>x~-x<:0D:~>~>~^:_s:?

11l [edit]

Translation of: Python

F fib_iter(n)
          I n < 2
          R n
          V fib_prev = 1
          V fib = 1
          L 2 .< n
          (fib_prev, fib) = (fib, fib + fib_prev)
          R fib L(i) 1..20
            print(fib_iter(i), end' ' ')
print()

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

360 Assembly [edit]

For maximum compatibility, programs use only the basic instruction set.

using fullword integers [edit]

*        Fibonacci sequence    05/11/2014
*        integer (31 bits) = 10 decimals -> max fibo(46)
FIBONACC CSECT
          USING FIBONACC,R12    base register
SAVEAREA B     STM-SAVEAREA(R15) skip savearea
          DC    17F'0'          savearea
          DC    CL8'FIBONACC'   eyecatcher
STM      STM   R14,R12,12(R13) save previous context
          ST    R13,4(R15)      link backward
          ST    R15,8(R13)      link forward
          LR    R12,R15         set addressability
*        ----
          LA    R1,0            f(n-2)=0
          LA    R2,1            f(n-1)=1
          LA    R4,2            n=2          
          LA    R6,1            step
          LH    R7,NN           limit
LOOP     EQU   *               for n=2 to nn
          LR    R3,R2             f(n)=f(n-1)
          AR    R3,R1             f(n)=f(n-1)+f(n-2)
          CVD   R4,PW             n  convert binary to packed (PL8)
          UNPK  ZW,PW             packed (PL8) to zoned (ZL16)
          MVC   CW,ZW             zoned (ZL16) to  char (CL16)
          OI    CW+L'CW-1,X'F0'   zap sign
          MVC   WTOBUF+5(2),CW+14 output
          CVD   R3,PW             f(n) binary to packed decimal (PL8)
          MVC   ZN,EM             load mask
          ED    ZN,PW             packed dec (PL8) to char (CL20)
          MVC   WTOBUF+9(14),ZN+6 output
          WTO   MF=(E,WTOMSG)     write buffer
          LR    R1,R2             f(n-2)=f(n-1)
          LR    R2,R3             f(n-1)=f(n)
          BXLE  R4,R6,LOOP      endfor n
*        ----
          LM    R14,R12,12(R13) restore previous savearea pointer
          XR    R15,R15         return code set to 0
          BR    R14             return to caller
*        ----  DATA
NN       DC    H'46'           nn max n
PW       DS    PL8             15num
ZW       DS    ZL16
CW       DS    CL16
ZN       DS    CL20
*                  ' b 0 0 0 , 0 0 0 , 0 0 0 , 0 0 0 , 0 0 0'  15num
EM       DC    XL20'402020206B2020206B2020206B2020206B202120'  mask
WTOMSG   DS    0F
          DC    H'80',XL2'0000'
*                   fibo(46)=1836311903          
WTOBUF   DC    CL80'fibo(12)=1234567890'
          REGEQU
          END   FIBONACC

... fibo(41)=   165,580,141 fibo(42)=   267,914,296 fibo(43)=   433,494,437 fibo(44)=   701,408,733 fibo(45)= 1,134,903,170 fibo(46)= 1,836,311,903

using packed decimals [edit]

*        Fibonacci sequence        31/07/2018
*        packed dec (PL8) = 15 decimals => max fibo(73)
FIBOWTOP CSECT
          USING  FIBOWTOP,R13       base register
          B      72(R15)            skip savearea
          DC     17F'0'             savearea
          SAVE   (14,12)            save previous context
          ST     R13,4(R15)         link backward
          ST     R15,8(R13)         link forward
          LR     R13,R15            set addressability
*        ----
          ZAP    FNM2,=P'0'         f(0)=0
          ZAP    FNM1,=P'1'         f(1)=1
          LA     R4,2               n=2          
          LA     R6,1               step
          LH     R7,NN              limit
LOOP     EQU    *                  for n=2 to nn
          ZAP    FN,FNM1              f(n)=f(n-2)
          AP     FN,FNM2              f(n)=f(n-1)+f(n-2)
          CVD    R4,PW                n          
          MVC    ZN,EM                load mask
          ED     ZN,PW                packed dec (PL8) to char (CL16)
          MVC    WTOBUF+5(2),ZN+L'ZN-2  output
          MVC    ZN,EM                load mask
          ED     ZN,FN                packed dec (PL8) to char (CL16)
          MVC    WTOBUF+9(L'ZN),ZN        output
          WTO    MF=(E,WTOMSG)        write buffer
          ZAP    FNM2,FNM1            f(n-2)=f(n-1)
          ZAP    FNM1,FN              f(n-1)=f(n)
          BXLE   R4,R6,LOOP         endfor n
*        ----
          L      R13,4(0,R13)       restore previous savearea pointer
          RETURN (14,12),RC=0       restore registers from calling sav
*        ----   DATA
NN       DC     H'73'              nn
FNM2     DS     PL8                f(n-2)
FNM1     DS     PL8                f(n-1)
FN       DS     PL8                f(n)
PW       DS     PL8                15num
ZN       DS     CL20
*                   ' b 0 0 0 , 0 0 0 , 0 0 0 , 0 0 0 , 0 0 0'  15num
EM       DC     XL20'402020206B2020206B2020206B2020206B202120'  mask
WTOMSG   DS     0F
          DC     H'80',XL2'0000'
*                    fibo(73)=806515533049393
WTOBUF   DC     CL80'fibo(12)=123456789012345 '
          REGEQU          
          END    FIBOWTOP

... fibo(68)=  72,723,460,248,141 fibo(69)= 117,669,030,460,994 fibo(70)= 190,392,490,709,135 fibo(71)= 308,061,521,170,129 fibo(72)= 498,454,011,879,264 fibo(73)= 806,515,533,049,393

6502 Assembly [edit]

This subroutine stores the first n—by default the first ten—Fibonacci numbers in memory, beginning (because, why not?) at address 3867 decimal = F1B hex. Intermediate results are stored in three sequential addresses within the low 256 bytes of memory, which are the most economical to access.

The results are calculated and stored, but are not output to the screen or any other physical device: how to do that would depend on the hardware and the operating system.

          LDA  #0
          STA  $F0     ; LOWER NUMBER
          LDA  #1
          STA  $F1     ; HIGHER NUMBER
          LDX  #0
LOOP:  LDA  $F1
          STA  $0F1B,X
          STA  $F2     ; OLD HIGHER NUMBER
          ADC  $F0
          STA  $F1     ; NEW HIGHER NUMBER
          LDA  $F2
          STA  $F0     ; NEW LOWER NUMBER
          INX
          CPX  #$0A    ; STOP AT FIB(10)
          BMI  LOOP
          RTS          ; RETURN FROM SUBROUTINE

8080 Assembly [edit]

This subroutine expects to be called with the value of $n$ in register A, and returns $f(n)$ also in A. You may want to take steps to save the previous contents of B, C, and D. The routine only works with fairly small values of $n$ .

FIBNCI: MOV  C,  A  ; C will store the counter
          DCR  C      ; decrement, because we know f(1) already
          MVI  A,  1
          MVI  B,  0
LOOP:   MOV  D,  A
          ADD  B      ; A := A + B
          MOV  B,  D
          DCR  C
          JNZ  LOOP   ; jump if not zero
          RET         ; return from subroutine

8th [edit]

An iterative solution:


: fibon \ n -- fib(n)
          >r 0 1          
          ( tuck n:+ ) \ fib(n-2) fib(n-1) -- fib(n-1) fib(n)
          r> n:1- times ; : fib \ n -- fib(n)
            dup 1 n:= if 1 ;; then
            fibon nip ;

ABAP [edit]

Iterative [edit]

          FORM          fibonacci_iter          USING          index          TYPE          i
          CHANGING          number_fib          TYPE          i.          
          DATA          :          lv_old          type          i,          
          lv_cur          type          i.          
          Do          index          times          .          
          If          sy-          index          =          1          or          sy-          index          =          2          .          
          lv_cur          =          1          .          
          lv_old          =          0          .          
          endif          .          
          number_fib          =          lv_cur          +          lv_old.          
          lv_old          =          lv_cur.          
          lv_cur          =          number_fib.          
          enddo          .          
          ENDFORM          .

Impure Functional [edit]

Works with: ABAP version 7.4 SP08 Or above only

cl_demo_output=>          display          (          REDUCE #(          INIT fibnm          =          VALUE          stringtab(          (          |0|          )          (          |1|          )          )          
          n          TYPE          string          
          x          =          `0`          
          y          =          `1`          
          FOR          i          =          1          WHILE          i          <=          100          
          NEXT          n          =          (          x          +          y          )          
          fibnm          =          VALUE          #(          BASE fibnm          (          n          )          )          
          x          =          y
          y          =          n          )          )          .

ACL2 [edit]

Fast, tail recursive solution:

          (          defun          fast-fib-r          (n a b)          
          (          if          (          or          (zp n)          (zp          (          1- n)          )          )          
          b
          (fast-fib-r          (          1- n)          b          (+ a b)          )          )          )          (            defun            fast-fib            (n)            
            (fast-fib-r n            1            1            )            )          
          (            defun            first-fibs-r            (n i)            
            (declare            (xargs            :            measure            (nfix            (- n i)            )            )            )            
            (            if            (zp            (- n i)            )            
            nil            
            (            cons            (fast-fib i)            
            (first-fibs-r n            (            1+ i)            )            )            )            )          
          (            defun            first-fibs            (n)            
            (first-fibs-r n            0            )            )

>(first-fibs 20) (1 1 2 3 5 8 13 21 34 55 89    144 233 377 610 987 1597 2584 4181 6765)

Action! [edit]

Action! language does not support recursion. Therefore an iterative approach has been proposed.

INT FUNC Fibonacci(INT n)
          INT curr,prev,tmp   IF n>=-1 AND n<=1 THEN
            RETURN (n)
            FI
             prev=0
            IF n>0 THEN
            curr=1
            DO
            tmp=prev
            prev=curr
            curr==+tmp
            n==-1
            UNTIL n=1
            OD
            ELSE
            curr=-1
            DO
            tmp=prev
            prev=curr
            curr==+tmp
            n==+1
            UNTIL n=-1
            OD
            FI
RETURN (curr)
           PROC Main()
            BYTE n
            INT f
             Put(125) ;clear screen
             FOR n=0 TO 22
            DO
            f=Fibonacci(n)
            Position(2,n+1)
            PrintF("Fib(%I)=%I",n,f)
               IF n>0 THEN
            f=Fibonacci(-n)
            Position(21,n+1)
            PrintF("Fib(%I)=%I",-n,f)
            FI
            OD
RETURN

Screenshot from Atari 8-bit computer

Fib(0)=0 Fib(1)=1           Fib(-1)=-1 Fib(2)=1           Fib(-2)=-1 Fib(3)=2           Fib(-3)=-2 Fib(4)=3           Fib(-4)=-3 Fib(5)=5           Fib(-5)=-5 Fib(6)=8           Fib(-6)=-8 Fib(7)=13          Fib(-7)=-13 Fib(8)=21          Fib(-8)=-21 Fib(9)=34          Fib(-9)=-34 Fib(10)=55         Fib(-10)=-55 Fib(11)=89         Fib(-11)=-89 Fib(12)=144        Fib(-12)=-144 Fib(13)=233        Fib(-13)=-233 Fib(14)=377        Fib(-14)=-377 Fib(15)=610        Fib(-15)=-610 Fib(16)=987        Fib(-16)=-987 Fib(17)=1597       Fib(-17)=-1597 Fib(18)=2584       Fib(-18)=-2584 Fib(19)=4181       Fib(-19)=-4181 Fib(20)=6765       Fib(-20)=-6765 Fib(21)=10946      Fib(-21)=-10946 Fib(22)=17711      Fib(-22)=-17711

ActionScript [edit]

          public          function          fib(n:uint):uint
          {          
          if          (n          <          2          )          
          return          n;             return            fib(n -            1            )            + fib(n -            2            );
            }

Ada [edit]

Recursive [edit]

          with          Ada.Text_IO, Ada.Command_Line;procedure            Fib            is          
              X: Positive := Positive'Value(Ada.Command_Line.Argument            (            1            )            );
                       function            Fib(P: Positive)            return            Positive            is            
            begin            
            if            P <=            2            then            
            return            1;
            else            
            return            Fib(P-1            )            + Fib(P-2            );
            end            if;
            end            Fib;
          begin            
            Ada.Text_IO.Put            (            "Fibonacci("            & Integer'Image(X)            &            " ) = "            );
            Ada.Text_IO.Put_Line            (Integer'Image(Fib(X)            )            );
            end            Fib;

Iterative, build-in integers [edit]

          with          Ada.Text_IO;          use          Ada.Text_IO;procedure            Test_Fibonacci            is            
            function            Fibonacci            (N : Natural)            return            Natural            is            
            This : Natural :=            0;
            That : Natural :=            1;
            Sum  : Natural;
            begin            
            for            I            in            1..N            loop            
            Sum  := This + That;
            That := This;
            This := Sum;
            end            loop;
            return            This;
            end            Fibonacci;
            begin            
            for            N            in            0..10            loop            
            Put_Line            (Positive'Image            (Fibonacci            (N)            )            );
            end            loop;
            end            Test_Fibonacci;

          0  1  1  2  3  5  8  13  21  34  55

Iterative, long integers [edit]

Using the big integer implementation from a cryptographic library [1].

          with          Ada.Text_IO, Ada.Command_Line, Crypto.Types.Big_Numbers;procedure            Fibonacci            is          
              X: Positive := Positive'Value(Ada.Command_Line.Argument            (            1            )            );
              Bit_Length: Positive :=            1            +            (            696            * X)            /            1000;
            -- that number of bits is sufficient to store the full result.          
                       package            LN            is            new            Crypto.Types.Big_Numbers            
            (Bit_Length +            (            32            - Bit_Length            mod            32            )            );
            -- the actual number of bits has to be a multiple of 32            
            use            LN;
                       function            Fib(P: Positive)            return            Big_Unsigned            is            
            Previous: Big_Unsigned := Big_Unsigned_Zero;
            Result:   Big_Unsigned := Big_Unsigned_One;
            Tmp:      Big_Unsigned;
            begin            
            -- Result = 1 = Fibonacci(1)            
            for            I            in            1            ..            P-1            loop            
            Tmp := Result;
            Result := Previous + Result;
            Previous := Tmp;
            -- Result = Fibonacci(I+1))            
            end            loop;
            return            Result;
            end            Fib;
          begin            
            Ada.Text_IO.Put            (            "Fibonacci("            & Integer'Image(X)            &            " ) = "            );
            Ada.Text_IO.Put_Line            (LN.Utils.To_String            (Fib(X)            )            );
            end            Fibonacci;

> ./fibonacci 777 Fibonacci( 777 ) = 1081213530912648191985419587942084110095342850438593857649766278346130479286685742885693301250359913460718567974798268702550329302771992851392180275594318434818082

Fast method using fast matrix exponentiation [edit]


          with          ada.text_io;
          use          ada.text_io;procedure            fast_fibo            is            
            -- We work with biggest natural integers in a 64 bits machine                        
            type            Big_Int            is            mod            2**64;
                       -- We provide an index type for accessing the fibonacci sequence terms                        
            type            Index            is            new            Big_Int;
                       -- fibo is a generic function that needs a modulus type since it will return            
            -- the n'th term of the fibonacci sequence modulus this type (use Big_Int to get the                        
            -- expected behaviour in this particular task)            
            generic            
            type            ring_element            is            mod            <>;
            with            function            "*"            (a, b : ring_element)            return            ring_element            is            <>;
            function            fibo            (n : Index)            return            ring_element;
            function            fibo            (n : Index)            return            ring_element            is          
                       type            matrix            is            array            (            1            ..            2,            1            ..            2            )            of            ring_element;
                       -- f is the matrix you apply to a column containing (F_n, F_{n+1}) to get                        
            -- the next one containing (F_{n+1},F_{n+2})            
            -- could be a more general matrix (given as a generic parameter) to deal with                        
            -- other linear sequences of order 2            
            f :            constant            matrix :=            (            1            =>            (            0,            1            ),            2            =>            (            1,            1            )            );
                       function            "*"            (a, b : matrix)            return            matrix            is            
            (            1            =>            (a(            1,1            )*b(            1,1            )+a(            1,2            )*b(            2,1            ), a(            1,1            )*b(            1,2            )+a(            1,2            )*b(            2,2            )            ),
            2            =>            (a(            2,1            )*b(            1,1            )+a(            2,2            )*b(            2,1            ), a(            2,1            )*b(            1,2            )+a(            2,2            )*b(            2,2            )            )            );
                       function            square            (m : matrix)            return            matrix            is            (m * m);
                       -- Fast_Pow could be non recursive but it doesn't really matter since            
            -- the number of calls is bounded up by the size (in bits) of Big_Int (e.g 64)            
            function            fast_pow            (m : matrix; n : Index)            return            matrix            is            
            (            if            n =            0            then            (            1            =>            (            1,            0            ),            2            =>            (            0,            1            )            )            -- = identity matrix            
            elsif            n            mod            2            =            0            then            square            (fast_pow            (m, n /            2            )            )            
            else            m * square            (fast_pow            (m, n /            2            )            )            );
                       begin            
            return            fast_pow            (f, n)            (            2,            1            );
            end            fibo;
                       function            Big_Int_Fibo            is            new            fibo            (Big_Int);
            begin            
            -- calculate instantly F_n with n=10^15 (modulus 2^64 )            
            put_line            (Big_Int_Fibo            (            10**15            )'img);
            end            fast_fibo;

AdvPL [edit]

Recursive [edit]


#include "totvs.ch"
User Function fibb(a,b,n)
return(if(--n>0,fibb(b,a+b,n),a))

Iterative [edit]


#include "totvs.ch"
User Function fibb(n)          
          local fnow:=0, fnext:=1, tempf
          while (--n>0)
          tempf:=fnow+fnext
          fnow:=fnext
          fnext:=tempf
          end while
return(fnext)

Aime [edit]

integer
fibs(integer n)
{
          integer w;     if (n == 0) {
            w = 0;
            } elif (n == 1) {
            w = 1;
            } else {
            integer a, b, i;
                   i = 1;
            a = 0;
            b = 1;
            while (i < n) {
            w = a + b;
            a = b;
            b = w;
            i += 1;
            }
            }
               return w;
}

ALGOL 60 [edit]

Works with: A60

begin
          comment Fibonacci sequence;
          integer procedure fibonacci(n); value n; integer n;
          begin
          integer i, fn, fn1, fn2;
          fn2 := 1;
          fn1 := 0;
          fn  := 0;
          for i := 1 step 1 until n do begin
          fn  := fn1 + fn2;
          fn2 := fn1;
          fn1 := fn
          end;
          fibonacci := fn
          end fibonacci;     integer i;
            for i := 0 step 1 until 20 do outinteger(1,fibonacci(i))
end

          0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987  1597  2584  4181  6765