Fibonacci sequence: Difference between revisions

 

=={{header|0815}}==

%<:0D:>~$<:01:~%>=<:a94fad42221f2702:>~>

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

{{trans|Python}}

 

I n < 2

R n

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

===using fullword integers===

* integer (31 bits) = 10 decimals -> max fibo(46)

FIBONACC CSECT

</pre>

===using packed decimals===

* packed dec (PL8) = 15 decimals => max fibo(73)

FIBOWTOP CSECT

 

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.

STA $F0 ; LOWER NUMBER

LDA #1

{{trans|ARM Assembly}}

Input is in D0, and the output is also in D0. There is no protection from 32-bit overflow, so use at your own risk. (I used this [https://godbolt.org/ C compiler] to create this in ARM Assembly and translated it manually into 68000 Assembly. It wasn't that difficult since both CPUs have similar architectures.)

MOVEM.L D4-D5,-(SP)

MOVE.L D0,D4

=={{header|8080 Assembly}}==

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

DCR C ; decrement, because we know f(1) already

MVI A, 1

JNZ LOOP ; jump if not zero

RET ; return from subroutine</syntaxhighlight>

 

=={{header|8086 Assembly}}==

 

The max input is 24 before you start having 16-bit overflow.

; WRITTEN IN C WITH X86-64 CLANG 3.3 AND DOWNGRADED TO 16-BIT X86

; INPUT: DI = THE NUMBER YOU WISH TO CALC THE FIBONACCI NUMBER FOR.

 

For the purpose of this example, assume that both this code and the table are in the <code>.CODE</code> segment.

;input: BX = the desired fibonacci number (in other words, the "n" in "F(n)")

; DS must point to the segment where the fibonacci table is stored

=={{header|8th}}==

An iterative solution:

: fibon \ n -- fib(n)

>r 0 1

=={{header|ABAP}}==

===Iterative===

CHANGING number_fib TYPE i.

DATA: lv_old type i,

===Impure Functional===

{{works with|ABAP|7.4 SP08 Or above only}}

n TYPE string

x = `0`

=={{header|ACL2}}==

Fast, tail recursive solution:

(if (or (zp n) (zp (1- n)))

b

=={{header|Action!}}==

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

INT curr,prev,tmp

 

 

=={{header|ActionScript}}==

{

if (n < 2)

 

===Recursive===

 

procedure Fib is

 

===Iterative, build-in integers===

 

procedure Test_Fibonacci is

Using the big integer implementation from a cryptographic library [https://github.com/cforler/Ada-Crypto-Library/].

 

 

procedure Fibonacci is

===Fast method using fast matrix exponentiation===

 

with ada.text_io;

use ada.text_io;

=={{header|AdvPL}}==

===Recursive===

#include "totvs.ch"

User Function fibb(a,b,n)

 

===Iterative===

#include "totvs.ch"

User Function fibb(n)

end while

return(fnext)

</syntaxhighlight>

 

=={{header|Aime}}==

fibs(integer n)

{

=={{header|ALGOL 60}}==

{{works with|A60}}

comment Fibonacci sequence;

integer procedure fibonacci(n); value n; integer n;

{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}}

{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d]}}

LONG REAL sqrt 5 = long sqrt(5);

LONG REAL p = (1 + sqrt 5) / 2;

{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}}

{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d]}}

CASE n+1 IN

0, 1, 1, 2, 3, 5

{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}}

{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d]}}

( n < 2 | n | fib(n-1) + fib(n-2));</syntaxhighlight>

===Generative===

{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}}

{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d]}}

 

PROC gen fibonacci = (INT n, YIELDINT yield)VOID: (

 

This uses a pre-generated list, requiring much less run-time processor usage, but assumes that INT is only 31 bits wide.

-701408733, 433494437, -267914296, 165580141, -102334155,

63245986, -39088169, 24157817, -14930352, 9227465, -5702887,

 

=={{header|ALGOL W}}==

% return the nth Fibonacci number %

integer procedure Fibonacci( integer value n ) ;

Note that the 21st Fibonacci number (= 10946) is the largest that can be calculated without overflowing ALGOL-M's integer data type.

====Iterative====

BEGIN

INTEGER M, N, A, I;

 

====Naively recursive====

BEGIN

IF X < 3 THEN

=={{header|Alore}}==

 

if n < 2

return 1

=={{header|Amazing Hopper}}==

Analitic, Recursive and Iterative mode.

#include <hbasic.h>

 

 

=={{header|AntLang}}==

fib:{<0;1> {x,<x[-1]+x[-2]>}/ range[x]}

/nth

=={{header|Apex}}==

 

/*

author: snugsfbay

 

{{works with|Dyalog APL}}

fib←{⍵≤1:⍵ ⋄ (∇ ⍵-1)+∇ ⍵-2}

</syntaxhighlight>

:<math>\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}.</math>

In APL:

↑+.×/N/⊂2 2⍴1 1 1 0

</syntaxhighlight>

The ''First'' removes the shell from the ''Enclose''.

At this point we're basically done, but we need to pick out only <math>F_n</math> in order to complete the task. Here's one way:

↑0 1↓↑+.×/N/⊂2 2⍴1 1 1 0

</syntaxhighlight>

{{works with|GNU APL}}

An alternative approach, using Binet's formula (which was apparently known long before Binet):

 

=={{header|AppleScript}}==

===Imperative===

 

set x to (text returned of (display dialog "What fibbonaci number do you want?" default answer "3"))

set x to x as integer

The simple recursive version is famously slow:

 

if n < 1 then

0

{{Trans|JavaScript}} (ES6 memoized fold example)

{{Trans|Haskell}} (Memoized fold example)

 

-- fib :: Int -> Int

=={{header|ARM Assembly}}==

Expects to be called with <math>n</math> in R0, and will return <math>f(n)</math> in the same register.

push {r1-r3}

mov r1, #0

=={{header|ArnoldC}}==

 

 

HEY CHRISTMAS TREE f1

===Recursive===

 

if? x<2 [1]

else [(fib x-1) + (fib x-2)]

=={{header|AsciiDots}}==

 

 

/--#$--\

=={{header|ATS}}==

===Recursive===

fun fib_rec(n: int): int =

if n >= 2 then fib_rec(n-1) + fib_rec(n-2) else n

 

===Iterative===

(*

** This one is also referred to as being tail-recursive

 

===Iterative and Verified===

(*

** This implementation is verified!

 

===Matrix-based===

(* ****** ****** *)

//

===Iterative===

{{trans|C}}

MsgBox % fib(A_Index)

Return

===Recursive and iterative===

Source: [http://www.autohotkey.com/forum/topic44657.html AutoHotkey forum] by Laszlo

Important note: the recursive version would be very slow

without a global or static array. The iterative version

=={{header|AutoIt}}==

===Iterative===

$n0 = 0

$n1 = 1

</syntaxhighlight>

===Recursive===

$n0 = 0

$n1 = 1

=={{header|AWK}}==

As in many examples, this one-liner contains the function as well as testing with input from stdin, output to stdout.

10

fib(10)=55</syntaxhighlight>

 

Iterative solution:

r₁→N

0→I

In Babel, we can define fib using a stack-based approach that is not recursive:

 

 

foo x < puts x in foo. In this case, x is the code list between the curly-braces. This is how you define callable code in Babel. The definition works by initializing the stack with 0, 1. On each iteration of the times loop, the function duplicates the top element. In the first iteration, this gives 0, 1, 1. Then it moves down the stack with the <- operator, giving 0, 1 again. It adds, giving 1. then it moves back up the stack, giving 1, 1. Then it swaps. On the next iteration this gives:

And so on. To test fib:

 

 

{{out}}

=={{header|bash}}==

===Iterative===

$ fib=1;j=1;while((fib<100));do echo $fib;((k=fib+j,fib=j,j=k));done

</syntaxhighlight>

 

===Recursive===

{

if [ $1 -le 0 ]

 

==={{header|BASIC256}}===

# Basic-256 ver 1.1.4

# iterative Fibonacci sequence

print n + chr(9) + c

</syntaxhighlight>

 

==={{header|Commodore BASIC}}===

110 INPUT "MIN, MAX"; N1, N2

120 IF N1 > N2 THEN T = N1: N1 = N2: N2 = T

 

READY.</pre>

 

==={{header|Integer BASIC}}===

Only works with quite small values of <math>n</math>.

20 A=0

30 B=1

 

==={{header|IS-BASIC}}===

110 FOR I=0 TO 20

120 PRINT "F";I,FIB(I)

200 LET FIB=A

210 END DEF</syntaxhighlight>

 

==={{header|QBasic}}===

{{works with|FreeBASIC}}

====Iterative====

n1 = 0

n2 = 1

Next version calculates each value once, as needed, and stores the results in an array for later retreival (due to the use of <code>REDIM PRESERVE</code>, it requires [[QuickBASIC]] 4.5 or newer):

 

 

REDIM SHARED fibNum(1) AS LONG

====Recursive====

This example can't handle n < 0.

IF (n < 2) THEN

recFib = n

 

====Array (Table) Lookup====

This uses a pre-generated list, requiring much less run-time processor usage. (Since the sequence never changes, this is probably the best way to do this in "the real world". The same applies to other sequences like prime numbers, and numbers like pi and e.)

 

DATA 63245986,-39088169,24157817,-14930352,9227465,-5702887,3524578,-2178309

DATA 1346269,-832040,514229,-317811,196418,-121393,75025,-46368,28657,-17711

'*****sample inputs*****</syntaxhighlight>

 

 

 

 

{{out}}

 

==={{header|Sinclair ZX81 BASIC}}===

====Analytic====

20 PRINT INT (0.5+(((SQR 5+1)/2)**N)/SQR 5)</syntaxhighlight>

 

====Iterative====

20 LET A=0

30 LET B=1

 

====Tail recursive====

20 LET A=0

30 LET B=1

120 GOSUB 70

130 RETURN</syntaxhighlight>

 

=={{header|Batch File}}==

Recursive version

@echo off

if "%1" equ "" goto :eof

 

<!--- works with C syntax highlighting --->

// Fibonacci sequence, recursive version

fun fibb

// vim: set syntax=c ts=4 sw=4 et:

</syntaxhighlight>

 

=={{header|bc}}==

=== iterative ===

 

define fib(x) {

 

=={{header|BCPL}}==

 

let fib(n) = n<=1 -> n, valof

=={{header|beeswax}}==

 

_`Enter n: `TN`Fib(`{`)=`X~P~K#{;

#>~P~L#MM@>+@'q@{;

Notice the UInt64 wrap-around at <code>Fib(94)</code>!

 

Enter n: i0

 

 

=={{header|Befunge}}==

^ .:\/*8"@"\%*8"@":\ <</syntaxhighlight>

 

=={{header|BlitzMax}}==

 

n = int(input( "Enter n: "))

 

=={{header|Blue}}==

: fib ( nth:ecx -- result:edi ) 1 0

: compute ( times:ecx accum:eax scratch:edi -- result:edi ) xadd latest loop ;

=== Recursive ===

A primitive recursive can be done with predicates:

Or, it can be done with the Choose(<code>◶</code>) modifier:

 

=== Iterative ===

An iterative solution can be made with the Repeat(<code>⍟</code>) modifier:

 

=={{header|Bracmat}}==

===Recursive===

 

fib$30

 

===Iterative===

last i this new

. !arg:<2

{{works with|Brainf***|implementations with unbounded cell size}}

The first cell contains ''n'' (10), the second cell will contain ''fib(n)'' (55), and the third cell will contain ''fib(n-1)'' (34).

>>+<<[->[->+>+<<]>[-<+>]>[-<+>]<<<]</syntaxhighlight>

 

The following generates n fibonacci numbers and prints them, though not in ascii.

It does have a limit due to the cells usually being 1 byte in size.

>> + Init #2 to 1

<<

=={{header|Brat}}==

===Recursive===

true? x < 2, x, { fibonacci(x - 1) + fibonacci(x - 2) }

}</syntaxhighlight>

 

===Tail Recursive===

true? x == 0,

result,

 

===Memoization===

 

fibonacci = { x |

{true? x < 2, x, { cache[x] = fibonacci(x - 1) + fibonacci(x - 2) }}

}</syntaxhighlight>

 

=={{header|Burlesque}}==

 

{0 1}{^^++[+[-^^-]\/}30.*\[e!vv

</syntaxhighlight>

 

0 1{{.+}c!}{1000.<}w!

</syntaxhighlight>

=={{header|C}}==

===Recursive===

return (--n>0)?(fibb(b, a+b, n)):(a);

}</syntaxhighlight>

 

===Iterative===

int fnow = 0, fnext = 1, tempf;

while(--n>0){

 

===Analytic===

#define PHI ((1 + sqrt(5))/2)

 

{{trans|Python}}

{{works with|gcc|version 4.1.2 20080704 (Red Hat 4.1.2-44)}}

typedef enum{false=0, true=!0} bool;

typedef void iterator;

 

===Fast method for a single large value===

#include <stdio.h>

#include <gmp.h>

 

=== Recursive ===

public static ulong Fib(uint n) {

return (n < 2)? n : Fib(n - 1) + Fib(n - 2);

 

=== Tail-Recursive ===

public static ulong Fib(uint n) {

return Fib(0, 1, n);

 

=== Iterative ===

public static ulong Fib(uint x) {

if (x == 0) return 0;

}

</syntaxhighlight>

 

=== Eager-Generative ===

public static IEnumerable<long> Fibs(uint x) {

IList<ulong> fibs = new List<ulong>();

 

=== Lazy-Generative ===

public static IEnumerable<ulong> Fibs(uint x) {

ulong prev = -1;

=== Analytic ===

This returns digits up to the 93^rd Fibonacci number, but the digits become inaccurate past the 71^st. There is custom rounding applied to the result that allows the function to be accurate at the 71^st number instead of topping out at the 70^th.

 

static ulong fib(uint n) {

if (n > 71) throw new ArgumentOutOfRangeException("n", n, "Needs to be smaller than 72.");

double r = Math.Pow(Phi, n) / r5;

do { t = x / g; lg = g; g = (t + g) / 2M; } while (lg != g);

return g; }

if (n > 93) throw new ArgumentOutOfRangeException("n", n, "Needs to be smaller than 94.");

decimal r = Pow_dec(Phi, n) / r5;

do { t = x / g; lg = g; g = (t + g) / 2M; } while (lg != g);

return g; }

Needs <code>System.Windows.Media.Matrix</code> or similar Matrix class.

Calculates in <math>O(n)</math>.

public static ulong Fib(uint n) {

var M = new Matrix(1,0,0,1);

Needs <code>System.Windows.Media.Matrix</code> or similar Matrix class.

Calculates in <math>O(\log{n})</math>.

private static Matrix M;

private static readonly Matrix N = new Matrix(1,1,1,0);

 

=== Array (Table) Lookup ===

private static int[] fibs = new int[]{ -1836311903, 1134903170,

-701408733, 433494437, -267914296, 165580141, -102334155,

This large step recurrence routine can calculate the two millionth Fibonacci number in under 1 / 5 second at tio.run. This routine can generate the fifty millionth Fibonacci number in under 30 seconds at tio.run. The unused conventional iterative method times out at two million on tio.run, you can only go to around 1,290,000 or so to keep the calculation time (plus string conversion time) under the 60 second timeout limit there. When using this large step recurrence method, it takes around 5 seconds to convert the two millionth Fibonacci number (417975 digits) into a string (so that one may count those digits).

 

using System.Collections.Generic;

using BI = System.Numerics.BigInteger;

partial: 85312949175076415430516606545038251...91799493108960825129188777803453125

</pre>

 

=={{header|C++}}==

Using unsigned int, this version only works up to 48 before fib overflows.

 

int main()

This version does not have an upper bound.

 

#include <gmpxx.h>

 

 

Version using transform:

#include <vector>

#include <functional>

 

Far-fetched version using adjacent_difference:

#include <vector>

#include <functional>

 

Version which computes at compile time with metaprogramming:

 

template <int n> struct fibo

 

The following version is based on fast exponentiation:

 

inline void fibmul(int* f, int* g)

===Using Zeckendorf Numbers===

The nth fibonacci is represented as Zeckendorf 1 followed by n-1 zeroes. [[Zeckendorf number representation#Using a C++11 User Defined Literal|Here]] I define a class N which defines the operations increment ++() and comparison <=(other N) for Zeckendorf Numbers.

// Use Zeckendorf numbers to display Fibonacci sequence.

// Nigel Galloway October 23rd., 2012

===Using Standard Template Library===

Possibly less "Far-fetched version".

// Use Standard Template Library to display Fibonacci sequence.

// Nigel Galloway March 30th., 2013

 

=={{header|Cat}}==

dup 1 <=

[]

 

=={{header|Chapel}}==

var a = 0, b = 1;

 

 

=={{header|Chef}}==

 

An unobfuscated iterative implementation.

 

Serves 1.</syntaxhighlight>

 

=={{header|Clio}}==

Clio is pure and functions are lazy and memoized by default

 

if n < 2: n

else: (n - 1 -> fib) + (n - 2 -> fib)

===Lazy Sequence===

This is implemented idiomatically as an infinitely long, lazy sequence of all Fibonacci numbers:

(map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))</syntaxhighlight>

Thus to get the nth one:

So long as one does not hold onto the head of the sequence, this is unconstrained by length.

 

The one-line implementation may look confusing at first, but on pulling it apart it actually solves the problem more "directly" than a more explicit looping construct.

(map first ;; throw away the "metadata" (see below) to view just the fib numbers

(iterate ;; create an infinite sequence of [prev, curr] pairs

 

A more elegant solution is inspired by the Haskell implementation of an infinite list of Fibonacci numbers:

Then, to see the first ten,

(0 1 1 2 3 5 8 13 21 34)</syntaxhighlight>

 

 

Here's a simple interative process (using a recursive function) that carries state along with it (as args) until it reaches a solution:

;; n is which fib number you're on for this call (0th, 1st, 2nd, etc.)

;; j is the nth fib number (ex. when n = 5, j = 5)

Based upon the doubling algorithm which computes in O(log (n)) time as described here https://www.nayuki.io/page/fast-fibonacci-algorithms

Implementation credit: https://stackoverflow.com/questions/27466311/how-to-implement-this-fast-doubling-fibonacci-algorithm-in-clojure/27466408#27466408

(defn fib [n]

(letfn [(fib* [n]

A naive slow recursive solution:

 

(case n

0 0

This can be improved to an O(n) solution, like the iterative solution, by memoizing the function so that numbers that have been computed are cached. Like a lazy sequence, this also has the advantage that subsequent calls to the function use previously cached results rather than recalculating.

 

(memoize

(fn [n]

 

=== Using core.async ===

(require '[clojure.core.async

:refer [<! >! >!! <!! timeout chan alt! go]])

 

=={{header|CLU}}==

fib = iter () yields (int)

a: int := 0

Iteration uses a while() loop. Memoization uses global properties.

 

set_property(GLOBAL PROPERTY fibonacci_1 1)

set_property(GLOBAL PROPERTY fibonacci_next 2)

endfunction(fibonacci)</syntaxhighlight>

 

set(s "")

foreach(i RANGE 0 9)

=={{header|COBOL}}==

===Iterative===

Data Division.

Working-Storage Section.

===Recursive===

{{works with|GNU Cobol|2.0}}

IDENTIFICATION DIVISION.

PROGRAM-ID. fibonacci-main.

=={{header|CoffeeScript}}==

===Analytic===

sqrt = Math.sqrt

phi = ((1 + sqrt(5))/2)

 

===Iterative===

return n if n < 2

[prev, curr] = [0, 1]

 

===Recursive===

if n < 2 then n else fib_rec(n-1) + fib_rec(n-2)</syntaxhighlight>

 

 

===Iterative===

a = 1

i = 1 # start

Note that Common Lisp uses bignums, so this will never overflow.

===Iterative===

(case n

(0 f0)

 

Simpler one:

(let ((a 0) (b 1) (c n))

(loop for i from 2 to n do

c))</syntaxhighlight>

 

 

===Recursive===

(if (< n 2)

n

 

 

(if (= n 0)

a

 

Tail recursive and squaring:

(if (= n 1) (+ (* b p) (* a q))

(fib (ash n -1)

I use [https://franz.com/downloads/clp/survey Allegro CL 10.1]

 

;; Project : Fibonacci sequence

 

 

=== Solution with methods and eql specializers ===

(defmethod fib (n)

(declare ((integer 0 *) n))

This solution uses a list to keep track of the Fibonacci sequence for 0 or a

positive integer.

(cond ((< n 0) nil)

((< n 2) n)

we reverse it back when we return it).

 

 

;;; Helper functions

=={{header|Computer/zero Assembly}}==

To find the <math>n</math>th Fibonacci number, set the initial value of <tt>count</tt> equal to <math>n</math>–2 and run the program. The machine will halt with the answer stored in the accumulator. Since Computer/zero's word length is only eight bits, the program will not work with values of <math>n</math> greater than 13.

STA temp

ADD x ; lower No.

y: 1

temp: 0</syntaxhighlight>

 

=={{header|Corescript}}==

var previous = 1

var number = 0

 

=={{header|Cowgol}}==

 

sub fibonacci(n: uint32): (a: uint32) is

 

=={{header|Crystal}}==

===Recursive===

n < 2 ? n : fib(n - 1) + fib(n - 2)

end</syntaxhighlight>

 

===Iterative===

return n if n < 2

 

 

===Tail Recursive===

n == 0 ? prevFib : fibTailRecursive(n - 1, fib, prevFib + fib)

end</syntaxhighlight>

 

===Analytic===

(((5 ** 0.5 + 1) / 2) ** n / 5 ** 0.5).round.to_i

end</syntaxhighlight>

Here are four versions of Fibonacci Number calculating functions. ''FibD'' has an argument limit of magnitude 84 due to floating point precision, the others have a limit of 92 due to overflow (long).The traditional recursive version is inefficient. It is optimized by supplying a static storage to store intermediate results. A Fibonacci Number generating function is added.

All functions have support for negative arguments.

 

long sgn(alias unsignedFib)(int n) { // break sign manipulation apart

0:0 | -1:1 | -2:-1 | -3:2 | -4:-3 | -5:5 | -6:-8 | -7:13 | -8:-21 | -9:34 | </pre>

===Matrix Exponentiation Version===

 

T fibonacciMatrix(T=BigInt)(size_t n) {

===Faster Version===

For N = 10_000_000 this is about twice faster (run-time about 2.20 seconds) than the matrix exponentiation version.

 

// Algorithm from: Takahashi, Daisuke,

 

=={{header|Dart}}==

if (n==0 || n==1) {

return n;

=={{header|Datalog}}==

Simple recurive implementation for Souffle.

Fib(0, 0).

Fib(1, 1).

 

=={{header|DBL}}==

; Fibonacci sequence for DBL version 4 by Dario B.

;

This needs a modern Dc with <code>r</code> (swap) and <code>#</code> (comment).

It easily can be adapted to an older Dc, but it will impact readability a lot.

d - # 0

1 + # 1

 

=== Iterative ===

function FibonacciI(N: Word): UInt64;

var

 

=== Recursive ===

function Fibonacci(N: Word): UInt64;

begin

Algorithm is based on

:<math>\begin{pmatrix}1&1\\1&0\end{pmatrix}^n = \begin{pmatrix}F(n+1)&F(n)\\F(n)&F(n-1)\end{pmatrix}</math>.

function fib(n: Int64): Int64;

 

 

=={{header|DIBOL-11}}==

 

 

 

FIB2, D10, 1

FIBNEW, D10

 

RECORD HEADER

 

RECORD OUTPUT

WRITES(8,HEADER)

 

LOOP,

FIBNEW = FIB1 + FIB2

LOOPCNT = LOOPCNT + 1

 

CLOSE 8

END

 

 

 

</syntaxhighlight>

=={{header|DWScript}}==

 

begin

if N < 2 then Result := 1

=={{header|Dyalect}}==

 

if n < 2 {

return n

 

=={{header|E}}==

var s := [0, 1]

for _ in 0..!n {

=={{header|EasyLang}}==

 

.

 

Recursive (inefficient):

 

.

 

=={{header|EchoLisp}}==

Use '''memoization''' with the recursive version.

(define (fib n)

(if (< n 2) n

===Analytic===

 

 

 

=={{header|EDSAC order code}}==

This program calculates the <i>n</i>th—by default the tenth—number in the Fibonacci sequence and displays it (in binary) in the first word of storage tank 3.

==================

 

=={{header|Eiffel}}==

class

APPLICATION

=={{header|Ela}}==

Tail-recursive function:

where fib' a b 0 = a

fib' a b n = fib' b (a + b) (n - 1)</syntaxhighlight>

Infinite (lazy) list:

where fib' x y = & x :: fib' y (x + y)</syntaxhighlight>

 

=={{header|Elena}}==

{{trans|Smalltalk}}

fibu(n)

else

{

{

int t := ac[1];

public program()

{

{

console.printLine(fibu(i))

=== Alternative version using yieldable method ===

 

 

public FibonacciGenerator

long n_1 := 1l;

 

 

while(true)

long n := n_2 + n_1;

 

 

n_2 := n_1;

auto e := new FibonacciGenerator();

console.printLine(e.next())

};

 

=={{header|Elixir}}==

def fib(0), do: 0

def fib(1), do: 1

 

Using Stream:

Stream.unfold({0,1}, fn {a,b} -> {a,{b,a+b}} end) |> Enum.take(10)

</syntaxhighlight>

 

=={{header|Elm}}==

Naïve recursive implementation.

fibonacci n = if n < 2 then

n

else

fibonacci(n - 2) + fibonacci(n - 1)</syntaxhighlight>

 

=={{header|Emacs Lisp}}==

===version 1===

 

(cond

((< c n) (fib n b (+ a b) (+ 1 c)))

===version 2===

 

(let (vec i j k)

(if (< n 2)

<b>Eval:</b>

 

(mapconcat (lambda (n) (format "%d" (fibonacci n)))

(number-sequence 0 15) " "))</syntaxhighlight>

=={{header|Erlang}}==

===Recursive ===

-module(fib).

-export([fib/1]).

 

===Iterative ===

-module(fiblin).

-export([fib/1])

 

<b> Evaluate:</b>

io:write([fiblin:fib(X) || X <- lists:seq(1,10) ]).

</syntaxhighlight>

 

===Iterative 2===

fib(N) -> fib(N, 0, 1).

 

 

=={{header|ERRE}}==

! derived from my book "PROGRAMMARE IN ERRE"

! iterative solution

==='Recursive' version===

{{works with|Euphoria|any version}}

function fibor(integer n)

if n<2 then return n end if

==='Iterative' version===

{{works with|Euphoria|any version}}

function fiboi(integer n)

integer f0=0, f1=1, f

==='Tail recursive' version===

{{works with|Euphoria|4.0.0}}

function fibot(integer n, integer u = 1, integer s = 0)

if n < 1 then

==='Paper tape' version===

{{works with|Euphoria|4.0.0}}

include std/mathcons.e -- for PINF constant

 

 

{{Works with|Office 365 Betas 2021}}

=LAMBDA(n,

APPLYN(n - 2)(

 

And assuming that the following names are also bound to reusable generic lambdas in the Name manager:

=LAMBDA(xs,

LAMBDA(ys,

Or as a fold, obtaining just the Nth term of the Fibonacci series:

 

=LAMBDA(n,

INDEX(

Assuming the following generic bindings in the Excel worksheet Name manager:

 

=LAMBDA(xs,

LAMBDA(ys,

=={{header|F_Sharp|F#}}==

This is a fast [tail-recursive] approach using the F# big integer support:

let fibonacci n : bigint =

let rec f a b n =

val it : bigint = 354224848179261915075I</syntaxhighlight>

Lazy evaluated using sequence workflow:

for (a,b) in Seq.zip fib (Seq.skip 1 fib) -> a+b}</syntaxhighlight>

 

 

Lazy evaluation using the sequence unfold anamorphism is much much better as to efficiency:

fibonacci |> Seq.nth 10000

</syntaxhighlight>

Since it uses exponentiation by squaring, calculations of fib(n) where n is a power of 2 are particularly quick.

Eg. fib(2^20) was calculated in a little over 4 seconds on this poster's laptop.

open System

open System.Diagnostics

=={{header|Factor}}==

===Iterative===

dup 2 < [

[ 0 1 ] dip [ swap [ + ] keep ] times

 

===Recursive===

dup 2 < [

[ 1 - fib ] [ 2 - fib ] bi +

 

===Tail-Recursive===

dup 1 <

[ 2drop ]

===Matrix===

{{trans|Ruby}}

 

: fib ( n -- m )

=={{header|Falcon}}==

===Iterative===

 

if n < 2: return n

end</syntaxhighlight>

===Recursive===

if n < 2 : return n

return fib_r(n-1) + fib_r(n-2)

end</syntaxhighlight>

===Tail Recursive===

return fib_aux(n,0,1)

end

 

=={{header|FALSE}}==

20n: {First 20 numbers}

0 1 n;f;!%%44,. {Output: "0,1,1,2,3,5..."}</syntaxhighlight>

 

=={{header|Fancy}}==

def fib {

match self -> {

Ints have a limit of 64-bits, so overflow errors occur after computing Fib(92) = 7540113804746346429.

 

class Main

{

}

}

</syntaxhighlight>

 

=={{header|Fermat}}==

Array fib[n+1];

fib[1] := 0;

=={{header|Fexl}}==

 

# (fib n) = the nth Fibonacci number

\fib=

=={{header|Fish}}==

Outputs Fibonacci numbers until stopped.

 

=={{header|FOCAL}}==

01.20 ASK "N =", N

01.30 SET A=0

 

=={{header|Forth}}==

0 1 rot 0 ?do over + swap loop drop ;</syntaxhighlight>

 

Or, for negative-index support:

 

rot dup 0 = if drop drop exit then

dup 0 > if 1 - rot rot dup rot +

Since there are only a fixed and small amount of Fibonacci numbers that fit in a machine word, this FORTH version creates a table of Fibonacci numbers at compile time. It stops compiling numbers when there is arithmetic overflow (the number turns negative, indicating overflow.)

 

: F-next, over + swap

dup 0> IF dup , true ELSE false THEN ;

=={{header|Fortran}}==

===FORTRAN IV===

NN=46

DO 1 I=0,NN

</pre>

===FORTRAN 77===

FUNCTION IFIB(N)

IF (N.EQ.0) THEN

</syntaxhighlight>

Test program

EXTERNAL IFIB

CHARACTER*10 LINE

===Recursive===

In ISO Fortran 90 or later, use a RECURSIVE function:

contains

recursive function fibR(n) result(fib)

===Iterative===

In ISO Fortran 90 or later:

integer, intent(in) :: n

integer, parameter :: fib0 = 0, fib1 = 1

 

Test program

use fibonacci

=={{header|Free Pascal}}==

''See also: [[#Pascal|Pascal]]''

/// domain for Fibonacci function

/// where result is within nativeUInt

fibonacci := f[previous];

end;</syntaxhighlight>

 

=={{header|Frink}}==

All of Frink's integers can be arbitrarily large.

fibonacciN[n] :=

{

=={{header|FRISC Assembly}}==

To find the nth Fibonacci number, call this subroutine with n in register R0: the answer will be returned in R0 too. Contents of other registers are preserved.

PUSH R2

PUSH R3

=={{header|FunL}}==

=== Recursive ===

fib( 0 ) = 0

fib( 1 ) = 1

 

=== Tail Recursive ===

def

_fib( 0, prev, _ ) = prev

 

=== Lazy List ===

def _fib( a, b ) = a # _fib( b, a + b )

 

 

=== Iterative ===

a, b = 0, 1

 

 

=== Binet's Formula ===

 

def fib( n ) =

 

=== Matrix Exponentiation ===

res = array( a.length(), b(0).length() )

 

=== Iterative ===

 

fun main(n: int): int =

loop((a,b) = (0,1)) = for _i < n do

=={{header|FutureBasic}}==

=== Iterative ===

 

local fn Fibonacci( n as long ) as long

=== Recursive ===

Cost is a time penalty

local fn Fibonacci( n as NSInteger ) as NSInteger

NSInteger result

=={{header|Fōrmulæ}}==

 

 

 

 

=={{header|GAP}}==

local a;

a := [[0, 1], [1, 1]]^n;

end;</syntaxhighlight>

GAP has also a buit-in function for that.

 

=={{header|Gecho}}==

Prints the first several fibonacci numbers...

 

=={{header|GML}}==

//Returns the nth fibonacci number

 

=={{header|Go}}==

=== Recursive ===

if a < 2 {

return a

}</syntaxhighlight>

=== Iterative ===

"math/big"

)

}</syntaxhighlight>

=== Iterative using a closure ===

fib1, fib2 := 0, 1

return func() int {

}</syntaxhighlight>

=== Using a goroutine and channel ===

a, b := 0, 1

for {

}

</syntaxhighlight>

 

=={{header|Groovy}}==

=== Recursive ===

A recursive closure must be ''pre-declared''.

rFib = {

it == 0 ? 0

 

=== Iterative ===

it == 0 ? 0

: it == 1 ? 1

 

=== Analytic ===

def aFib = { (φ**it - (-φ)**(-it))/(5**(1/2)) as BigInteger }</syntaxhighlight>

 

Test program:

def start = System.currentTimeMillis()

def result = c()

=={{header|Harbour}}==

===Recursive===

#include "harbour.ch"

Function fibb(a,b,n)

 

===Iterative===

#include "harbour.ch"

Function fibb(n)

{{Works with|exact-real|0.12.5.1}}

Using Binet's formula and [https://hackage.haskell.org/package/exact-real-0.12.5.1/docs/Data-CReal.html exact real arithmetic] library we can calculate arbitrary Fibonacci number '''exactly'''.

import Data.CReal

 

</syntaxhighlight>

Let's try it for large numbers:

λ> fib 10 :: CReal 0

55

Simple definition, very inefficient.

 

if x < 1

then 0

===Recursive with Memoization===

Very fast.

if x < 1

then 0

===Recursive with Memoization using memoized library===

Even faster and simpler is to use a defined memoizer (e.g. from MemoTrie package):

fib :: Integer -> Integer

fib = memo f where

f n = fib (n-1) + fib (n-2)</syntaxhighlight>

You can rewrite this without introducing f explicitly

fib :: Integer -> Integer

fib = memo $ \x -> case x of

n -> fib (n-1) + fib (n-2)</syntaxhighlight>

Or using LambdaCase extension you can write it even shorter:

import Data.MemoTrie

fib :: Integer -> Integer

n -> fib (n-1) + fib (n-2)</syntaxhighlight>

The version that supports negative numbers:

import Data.MemoTrie

fib :: Integer -> Integer

 

===Iterative===

where

go n a b

This is a standard example how to use lazy lists. Here's the (infinite) list of all Fibonacci numbers:

 

Or alternatively:

 

The ''n''th Fibonacci number is then just <code plang="haskell">fib !! n</code>. The above is equivalent to

 

 

Also

 

 

==== As a fold ====

Accumulator holds last two members of the series:

 

 

fib :: Integer -> Integer

we can simply write:

 

 

fib

=== With recurrence relations ===

Using <code>Fib[m=3n+r]</code> [http://en.wikipedia.org/wiki/Fibonacci_number#Other_identities recurrence identities]:

 

fibstep :: (Integer, Integer) -> (Integer, Integer)

 

<code>(fibN2 n)</code> directly calculates a pair <code>(f,g)</code> of two consecutive Fibonacci numbers, <code>(Fib[n], Fib[n+1])</code>, from recursively calculated such pair at about <code>n/3</code>:

(208988,"19532821287077577316")</syntaxhighlight>

The above should take less than 0.1s to calculate on a modern box.

Other identities that could also be used are [http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form here]. In particular, for <i>(n-1,n) ---> (2n-1,2n)</i> transition which is equivalent to the matrix exponentiation scheme, we have

 

 

and for <i>(n,n+1) ---> (2n,2n+1)</i> (derived from d'Ocagne's identity, for example),

 

 

=={{header|Haxe}}==

=== Iterative ===

 

{

var current = 0;

 

=== As Iterator ===

{

private var current = 0;

 

Used like:

Sys.println(i);</syntaxhighlight>

 

=={{header|HicEst}}==

 

Fibonacci = ($==2) + Fibonacci($-1) + Fibonacci($-2)

 

=={{header|Hoon}}==

=/ a=@ud 0

=/ b=@ud 1

=={{header|Hope}}==

===Recursive===

--- f 0 <= 0;

--- f 1 <= 1;

 

===Tail-recursive===

--- fib n <= l (1, 0, n)

whererec l == \(a,b,succ c) => if c<1 then a else l((a+b),a,c)

=== With lazy lists ===

This language, being one of Haskell's ancestors, also has lazy lists. Here's the (infinite) list of all Fibonacci numbers:

--- fibs <= fs whererec fs == 0::1::map (+) (tail fs||fs);</syntaxhighlight>

The ''n''th Fibonacci number is then just <code plang="hope">fibs @ n</code>.

=={{header|Hy}}==

Recursive implementation.

(if (< n 2)

n

computes fib(1000) if there is no integer argument.

 

write(fib(integer(!args) | 1000)

end

This example computes fib(1000000) if there is no integer argument.

 

write(fib(integer(!args) | 1000000))

end

=={{header|IDL}}==

===Recursive===

if n lt 3 then return,1L else return, fib(n-1)+fib(n-2)

end</syntaxhighlight>

 

===Iterative===

psum = (csum = 1uL)

if n lt 3 then return,csum

 

===Analytic===

q=1/( p=(1+sqrt(5))/2 )

return,round((p^n+q^n)/sqrt(5))

 

===Analytic===

fibAnalytic n =

floor $ ((pow goldenRatio n) - (pow (-1.0/goldenRatio) n)) / sqrt(5)

goldenRatio = (1.0 + sqrt(5)) / 2.0</syntaxhighlight>

===Recursive===

fibRecursive Z = Z

fibRecursive (S Z) = (S Z)

fibRecursive (S (S n)) = fibRecursive (S n) + fibRecursive n </syntaxhighlight>

===Iterative===

fibIterative n = fibIterative' n Z (S Z)

where fibIterative' : Nat -> Nat -> Nat -> Nat

fibIterative' (S n) a b = fibIterative' n b (a + b) </syntaxhighlight>

===Lazy===

fibLazy = 0 :: 1 :: zipWith (+) fibLazy (

case fibLazy of

 

=={{header|J}}==

'''Examples:'''

144

fibN i.31

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040</syntaxhighlight>

 

=={{header|Java}}==

===Iterative===

{

if (n < 2)

}</syntaxhighlight>

 

/**

* O(log(n))

 

===Recursive===

{

return (n < 2) ? n : recFibN(n - 1) + recFibN(n - 2);

===Caching-recursive===

A variant on recursive, that caches previous results, reducing complexity from O(n²) to simply O(n). Leveraging Java’s Map.computeIfAbsent makes this thread-safe, and the implementation pretty trivial.

 

static final Map<Integer, Long> cache = new HashMap<>();

===Analytic===

This method works up to the 92^nd Fibonacci number. After that, it goes out of range.

{

double p = (1 + Math.sqrt(5)) / 2;

}</syntaxhighlight>

===Tail-recursive===

{

return fibInner(0, 1, n);

}</syntaxhighlight>

===Streams===

import java.util.function.LongUnaryOperator;

import java.util.stream.LongStream;

====Recursive====

Basic recursive function:

return n<2?n:fib(n-1)+fib(n-2);

}</syntaxhighlight>

Can be rewritten as:

if (n<2) { return n; } else { return fib(n-1)+fib(n-2); }

}</syntaxhighlight>

 

One possibility familiar to Scheme programmers is to define an internal function for iteration through anonymous tail recursion:

return function(n,a,b) {

return n>0 ? arguments.callee(n-1,b,a+b) : a;

 

===Iterative===

var a = 0, b = 1, t;

while (n-- > 0) {

With the keys of a dictionary,

 

return cache = cache || {}, function(n){

if (cache[n]) return cache[n];

with the indices of an array,

 

'use strict';

 

 

====Y-Combinator====

return (function(fn) {

return fn(fn);

 

====Generators====

var prev = 0;

var curr = 1;

we can use an accumulating fold.

 

'use strict';

 

{{Trans|Haskell}} (Memoized fold example)

 

'use strict';

 

=={{header|Joy}}==

===Recursive===

 

===Iterative===

 

=={{header|jq}}==

so using it, the following algorithms only give exact answers up to fib(78). By contrast,

using the Go implementation of jq and the definition of nth_fib given below:

nth_fib(pow(2;20)) | tostring | [length, .[:10], .[-10:]]

</syntaxhighlight>

 

===Recursive===

if (n < 2) then n

else nth_fib_naive(n - 1) + nth_fib_naive(n - 2)

===Tail Recursive===

Recent versions of jq (after July 1, 2014) include basic optimizations for tail recursion, and nth_fib is defined here to take advantage of TCO. For example, nth_fib(10000000) completes with only 380KB (that's K) of memory. However nth_fib can also be used with earlier versions of jq.

# input: [f(i-2), f(i-1), countdown]

def fib: (.[0] + .[1]) as $sum

</syntaxhighlight>

 

(range(0;5), 50) | [., nth_fib(.)]

</syntaxhighlight>

[1,1]

[2,1]

 

===Binet's Formula===

(5|sqrt) as $rt

| ((1 + $rt)/2) as $phi

 

===Generator===

def fibonacci(n):

# input: [f(i-2), f(i-1), countdown]

=={{header|Julia}}==

===Recursive===

===Iterative===

x,y = (0,1)

for i = 1:n x,y = (y, x+y) end

end</syntaxhighlight>

===Matrix form===

 

=={{header|K}}==

 

===Recursive===

 

===Recursive with memoization===

Using a (global) dictionary c.

 

 

===Analytic===

{_((phi^x)-((1-phi)^x))%_sqrt[5]}</syntaxhighlight>

 

===Sequence to n===

 

=={{header|Kabap}}==

 

===Sequence to n===

// Calculate the $n'th Fibonacci number

 

 

=={{header|Klingphix}}==

dup 0 less

( ["Invalid argument"]

 

=={{header|Kotlin}}==

ITERATIVE {

override fun get(n: Int): Long = if (n < 2) {

 

=={{header|L++}}==

(main (prn (fib 30)))</syntaxhighlight>

 

{{VI solution|LabVIEW_Fibonacci_sequence.png}}

 

 

1) basic version

{def fib1

{fib5 1000} -> 4.346655768693743e+208 (CPU ~ 1ms)

 

</syntaxhighlight>

 

=={{header|Lang5}}==

__A -1 extract nip ; : nip swap drop ; : tuck swap over ;

: -rot rot rot ; : 0= 0 == ; : 1+ 1 + ; : 1- 1 - ; : sum '+ reduce ;

 

=={{header|langur}}==

 

writeln map .fibonacci, series 2..20</syntaxhighlight>

 

=={{header|Lasso}}==

define fibonacci(n::integer) => {

 

 

===Recursive===

takes '[n].

if { n <= 1. } then {

 

===Memoization===

takes '[n].

cache := here cache.

It runs on Lean 3.4.2:

 

-- Our first implementation is the usual recursive definition:

def fib1 : ℕ → ℕ

It runs on Lean 4:

 

-- Naive version

def fib1 (n : Nat) : Nat :=

===Recursive===

 

(defun fib

((0) 0)

===Iterative===

 

(defun fib

((n) (when (>= n 0))

</syntaxhighlight>

 

 

=={{header|Lingo}}==

===Recursive===

if n<2 then return n

return fib(n-1)+fib(n-2)

 

===Iterative===

if n<2 then return n

fibPrev = 0

 

===Analytic===

sqrt5 = sqrt(5.0)

p = (1+sqrt5)/2

 

=={{header|Lisaac}}==

+ result : UINTEGER_64;

(n < 2).if {

 

=={{header|LiveCode}}==

function fibi n

put 0 into aa

 

=={{header|LLVM}}==

; LLVM does not provide a way to print values, so the alternative would be

; to just load the string into memory, and that would be boring.

 

=={{header|Logo}}==

 

=={{header|LOLCODE}}==

HAI 1.2

HOW DUZ I fibonacci YR N

=={{header|LSL}}==

Rez a box on the ground, and add the following as a New Script.

if(n<2) {

return n;

=={{header|Lua}}==

===Recursive===

--calculates the nth fibonacci number. Breaks for negative or non-integer n.

function fibs(n)

 

===Pedantic Recursive===

--more pedantic version, returns 0 for non-integer n

function pfibs(n)

 

===Tail Recursive===

function a(n,u,s) if n<2 then return u+s end return a(n-1,u+s,u) end

function trfib(i) return a(i-1,1,0) end

 

===Table Recursive===

fib_n = setmetatable({1, 1}, {__index = function(z,n) return n<=0 and 0 or z[n-1] + z[n-2] end})

</syntaxhighlight>

 

===Table Recursive 2===

-- table recursive done properly (values are actually saved into table;

-- also the first element of Fibonacci sequence is 0, so the initial table should be {0, 1}).

 

===Iterative===

function ifibs(n)

local p0,p1=0,1

 

=={{header|Luck}}==

let cache = {} in

let fibc x = if x<=1 then x else (

 

=={{header|Lush}}==

(if (< n 2)

n

=={{header|M2000 Interpreter}}==

Return decimal type and use an Inventory (as closure) to store known return values. All closures are in scope in every recursive call (we use here lambda(), but we can use fib(), If we make Fib1=fib then we have to use lambda() for recursion.

Inventory K=0:=0,1:=1

fib=Lambda K (x as decimal)-> {

Here an example where we use a BigNum class to make a Group which hold a stack of values, and take 14 digits per item in stack. We can use inventory to hold groups, so we use the fast fib() function from code above, where we remove the type definition of Ret variable, and set two first items in inventory as groups.

 

 

Class BigNum {

 

=={{header|M4}}==

`eval(fibo(decr($1)) + fibo(decr(decr($1))))')')')dnl

define(`loop',`ifelse($1,$2,,`$3($1) loop(incr($1),$2,`$3')')')dnl

=={{header|MAD}}==

 

INTERNAL FUNCTION(N)

 

=={{header|Maple}}==

> f := n -> ifelse(n<3,1,f(n-1)+f(n-2));

> f(2);

The Wolfram Language already has a built-in function <tt>Fibonacci</tt>, but a simple recursive implementation would be

 

fib[1] = 1

fib[n_Integer] := fib[n - 1] + fib[n - 2]</syntaxhighlight>

An optimization is to cache the values already calculated:

 

fib[1] = 1

fib[n_Integer] := fib[n] = fib[n - 1] + fib[n - 2]</syntaxhighlight>

The above implementations may be too simplistic, as the first is incredibly slow for any reasonable range due to nested recursions and while the second is faster it uses an increasing amount of memory. The following uses recursion much more effectively while not using memory:

 

If[rm < 1, prvprv, fibi[prv, prvprv + prv, rm - 1]]

fib[n_Integer] := fibi[0, 1, n]</syntaxhighlight>

However, the recursive approaches in Mathematica are limited by the limit set for recursion depth (default 1024 or 4096 for the above cases), limiting the range for 'n' to about 1000 or 2000. The following using an iterative approach has an extremely high limit (greater than a million):

 

For[i = 0, i < n, i++, tmp = prv; prv += prvprv; prvprv = tmp];

Return[prvprv]]</syntaxhighlight>

If one wanted a list of Fibonacci numbers, the following is quite efficient:

 

fibList[n_Integer] := Map[Take[#, 1] &, NestList[fibi, {0, 1}, n]] // Flatten</syntaxhighlight>

 

Output from the last with "fibList[100]":

 

1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, \

196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, \

The Wolfram Language can also solve recurrence equations using the built-in function <tt>RSolve</tt>

 

fib[1] == 1}, fib[n], n][[1]]</syntaxhighlight>

 

This function can also be expressed as

 

 

which evaluates to

 

 

and is defined for all real or complex values of n.

{{trans|Julia}}

 

f = [1 1 ; 1 0]^(n-1);

 

===Iterative===

Fn = [1 0]; %Fn(1) is F_{n-2}, Fn(2) is F_{n-1}

The MATLAB help file suggests an interesting method of generating the Fibonacci numbers. Apparently the determinate of the Dramadah Matrix of type 3 (MATLAB designation) and size n-by-n is the nth Fibonacci number. This method is implimented below.

 

if n == 1

 

===Tartaglia/Pascal Triangle Method===

function number = fibonacci(n)

%construct the Tartaglia/Pascal Triangle

 

=={{header|Maxima}}==

fib2(n) := (matrix([0, 1], [1, 1])^^n)[1, 2]$

 

=={{header|MAXScript}}==

===Iterative===

(

if n < 2 then

)</syntaxhighlight>

===Recursive===

(

if n < 2 then

 

===fib.m===

% The following code is derived from the Mercury Tutorial by Ralph Becket.

% http://www.mercury.csse.unimelb.edu.au/information/papers/book.pdf

The much faster iterative algorithm can be written as:

 

:- pred fib_acc(int::in, int::in, int::in, int::in, int::out) is det.

 

</syntaxhighlight>

 

It has several inputs which form the loop, the first is the current number, the second is a limit, ie when to stop counting. And the next two are accumulators for the last and next-to-last results.

 

But what if you want the speed of the fib_acc with the recursive (more declarative) definition of fib? Then use memoization, because Mercury is a pure language fib(N, F) will always give the same F for the same N, guaranteed. Therefore memoization asks the compiler to use a table to remember the value for F for any N, and it's a one line change:

 

:- pragma memo(fib/2).

:- pred fib(int::in, int::out) is det.

 

=={{header|Metafont}}==

if n=0: 0

elseif n=1: 1

end</syntaxhighlight>

 

 

=={{header|min}}==

(2 <)

unless

 

=={{header|MiniScript}}==

An efficient solution (for n >= 0):

if n < 2 then return n

n1 = 0

 

And for comparison, a recursive solution (also for n >= 0):

if n < 1 then return 0

if n == 1 then return 1

print rfib(6)</syntaxhighlight>

=={{header|MiniZinc}}==

let {

array[0..n] of var int: fibonacci;

 

This is the iterative approach to the Fibonacci sequence.

.text

main: li $v0, 5 # read integer from input. The read integer will be stroed in $v0

 

=={{header|Mirah}}==

return n if n < 2

fibPrev = 1

 

=={{header|МК-61/52}}==

03</syntaxhighlight>

 

====Tail Recursion====

This version is tail recursive.

let

fun fib' (0,a,b) = a

 

====Recursion====

 

==={{header|MLite}}===

====Recursion====

Tail recursive.

(0, x1, x2) = x2

| (n, x1, x2) = fib (n-1, x2, x1+x2)

 

=={{header|ML/I}}==

"" Fibonacci - recursive

MCSKIP MT,<>

 

=={{header|Modula-2}}==

FROM FormatString IMPORT FormatString;

FROM Terminal IMPORT WriteString,WriteLn,ReadChar;

=={{header|Modula-3}}==

===Recursive===

BEGIN

IF n < 2 THEN

=== Iterative (with negatives) ===

 

 

VAR

=={{header|Monicelli}}==

Recursive version. It includes a main that reads a number N from standard input and prints the Nth Fibonacci number.

# Main

Lei ha clacsonato

=={{header|MontiLang}}==

Reads number from standard input and prints to that number in the fibonacci sequence

1 VAR b .

INPUT TOINT

Forth-style solution

 

swap dup rot swap

enddef

Simpler

 

0 1

FOR count

=={{header|MUMPS}}==

===Iterative===

;Iterative version to get the Nth Fibonacci number

;N must be a positive integer

=={{header|Nanoquery}}==

===Iterative===

if (n < 2)

return n

=={{header|Nemerle}}==

===Recursive===

using System.Console;

 

}</syntaxhighlight>

===Tail Recursive===

{

match(x)

=={{header|NESL}}==

===Recursive===

 

=={{header|NetRexx}}==

{{trans|REXX}}