Fibonacci sequence: Difference between revisions

 

=={{header|0815}}==

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

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

 

=={{header|11l}}==

{{trans|Python}}

 

I n < 2

R n

L(i) 1..20

print(fib_iter(i), end' ‘ ’)

 

{{out}}

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

===using fullword integers===

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

FIBONACC CSECT

WTOBUF DC CL80'fibo(12)=1234567890'

REGEQU

{{out}}

<pre>

</pre>

===using packed decimals===

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

FIBOWTOP CSECT

WTOBUF DC CL80'fibo(12)=123456789012345 '

REGEQU

{{out}}

<pre>

 

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

CPX #$0A ; STOP AT FIB(10)

BMI LOOP

 

=={{header|68000 Assembly}}==

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

ADD.L D4,D0

MOVEM.L (SP)+,D4-D5

 

=={{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

DCR C

JNZ LOOP ; jump if not zero

 

=={{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.

pop BX

pop BP

 

===Using A Lookup Table===

 

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

dword 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269

dword 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986

 

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

An iterative solution:

: fibon \ n -- fib(n)

>r 0 1

dup 1 n:= if 1 ;; then

fibon nip ;

 

=={{header|ABAP}}==

===Iterative===

CHANGING number_fib TYPE i.

DATA: lv_old type i,

lv_cur = number_fib.

enddo.

 

===Impure Functional===

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

n TYPE string

x = `0`

fibnm = VALUE #( BASE fibnm ( n ) )

x = y

 

=={{header|ACL2}}==

Fast, tail recursive solution:

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

b

 

(defun first-fibs (n)

 

{{out}}

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

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

INT curr,prev,tmp

 

FI

OD

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Fibonacci_sequence.png Screenshot from Atari 8-bit computer]

 

=={{header|ActionScript}}==

{

if (n < 2)

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

 

=={{header|Ada}}==

 

===Recursive===

 

procedure Fib is

Ada.Text_IO.Put("Fibonacci(" & Integer'Image(X) & " ) = ");

Ada.Text_IO.Put_Line(Integer'Image(Fib(X)));

 

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

 

procedure Test_Fibonacci is

Put_Line (Positive'Image (Fibonacci (N)));

end loop;

{{out}}

<pre>

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

 

 

procedure Fibonacci is

Ada.Text_IO.Put("Fibonacci(" & Integer'Image(X) & " ) = ");

Ada.Text_IO.Put_Line(LN.Utils.To_String(Fib(X)));

 

{{out}}

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

 

with ada.text_io;

use ada.text_io;

-- calculate instantly F_n with n=10^15 (modulus 2^64 )

put_line (Big_Int_Fibo (10**15)'img);

 

=={{header|AdvPL}}==

===Recursive===

#include "totvs.ch"

User Function fibb(a,b,n)

return(if(--n>0,fibb(b,a+b,n),a))

 

===Iterative===

#include "totvs.ch"

User Function fibb(n)

end while

return(fnext)

 

=={{header|Aime}}==

fibs(integer n)

{

return w;

}

 

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

{{works with|A60}}

comment Fibonacci sequence;

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

integer i;

for i := 0 step 1 until 20 do outinteger(1,fibonacci(i))

{{out}}

<pre>

{{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;

print(", ")

OD;

{{out}}

<pre>

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

print(", ")

OD;

{{out}}

<pre>

{{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]}}

===Generative===

{{trans|Python|Note: This specimen retains the original [[Prime decomposition#Python|Python]] coding style.}}

{{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: (

# OD # ));

print(new line)

{{out}}

<pre>

 

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,

print(", ")

OD;

{{out}}

<pre>

 

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

% return the nth Fibonacci number %

integer procedure Fibonacci( integer value n ) ;

for i := 0 until 10 do writeon( i_w := 3, s_w := 0, Fibonacci( i ) )

 

{{out}}

<pre>

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;

END;

FIBONACCI := N;

 

====Naively recursive====

BEGIN

IF X < 3 THEN

ELSE

FIBONACCI := FIBONACCI( X - 2 ) + FIBONACCI( X - 1 );

 

=={{header|Alore}}==

 

if n < 2

return 1

end

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

 

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

Analitic, Recursive and Iterative mode.

#include <hbasic.h>

 

Next

Return(B)

{{out}}

<pre>

 

=={{header|AntLang}}==

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

/nth

 

=={{header|Apex}}==

 

/*

author: snugsfbay

}

 

=={{header|APL}}==

 

{{works with|Dyalog APL}}

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

 

Read this as: In the variable "fib", store the function that says, if the argument is less than or equal to 1, return the argument. Else, calculate the value you get when you recursively call the current function with the argument of the current argument minus one and add that to the value you get when you recursively call the current function with the argument of the current function minus two.

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

Plugging in 4 for N gives the following result:

:<math>\begin{pmatrix} 5 & 3 \\ 3 & 2 \end{pmatrix}</math>

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

 

====Analytic====

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

end if

end repeat

 

 

The simple recursive version is famously slow:

 

if n < 1 then

0

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

end if

 

but we can combine '''enumFromTo(m, n)''' with the accumulator of a higher-order '''fold/reduce''' function to memoize the series:

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

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

 

-- fib :: Int -> Int

end script

end if

{{Out}}

<pre>2178309</pre>

=={{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

mov r0, r2

pop {r1-r3}

 

=={{header|ArnoldC}}==

 

 

HEY CHRISTMAS TREE f1

CHILL

 

 

=={{header|Arturo}}==

===Recursive===

 

if? x<2 [1]

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

loop 1..25 [x][

print ["Fibonacci of" x "=" fib x]

 

=={{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

then (fix loop (i:int, r0:int, r1:int): int => if i > 1 then loop (i-1, r1, r0+r1) else r1)(n, 0, 1)

else 0

 

===Iterative and Verified===

(*

** This implementation is verified!

loop {0} (FIB0 (), FIB1 () | n, 0, 1)

end // end of [fibats]

 

===Matrix-based===

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

//

//

} (* end of [main0] *)

 

=={{header|AutoHotkey}}==

===Iterative===

{{trans|C}}

MsgBox % fib(A_Index)

Return

}

Return this

 

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

c := b, b += a, a := c

Return n=0 ? 0 : n>0 || n&1 ? b : -b

 

=={{header|AutoIt}}==

===Iterative===

$n0 = 0

$n1 = 1

Return $febo

EndFunc

===Recursive===

$n0 = 0

$n1 = 1

EndIf

EndFunc

 

=={{header|AWK}}==

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

10

 

=={{header|Axe}}==

 

Iterative solution:

r₁→N

0→I

End

J

 

=={{header|Babel}}==

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

<pre>

1

 

===Recursive===

{

if [ $1 -le 0 ]

fi

}

 

=={{header|BASIC}}==

 

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

# Basic-256 ver 1.1.4

# iterative Fibonacci sequence

print " "

print n + chr(9) + c

 

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

110 INPUT "MIN, MAX"; N1, N2

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

230 : PRINT ","; STR$(A);

240 NEXT I

 

{{Out}}

 

READY.</pre>

 

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

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

20 A=0

30 B=1

80 NEXT I

90 PRINT B

 

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

110 FOR I=0 TO 20

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

190 NEXT

200 LET FIB=A

 

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

{{works with|FreeBASIC}}

====Iterative====

n1 = 0

n2 = 1

itFib = n1

END IF

 

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

ERROR 6 'overflow

END SELECT

 

{{out}} (unhandled error in final input prevents output):

====Recursive====

This example can't handle n < 0.

IF (n < 2) THEN

recFib = n

recFib = recFib(n - 1) + recFib(n - 2)

END IF

 

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

NEXT

PRINT

 

 

 

 

{{out}}

 

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

====Analytic====

 

====Iterative====

20 LET A=0

30 LET B=1

70 LET A=C

80 NEXT I

 

====Tail recursive====

20 LET A=0

30 LET B=1

110 LET N=N-1

120 GOSUB 70

 

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

Recursive version

@echo off

if "%1" equ "" goto :eof

set r2=%errorlevel%

set /a r0 = r1 + r2

 

{{out}}

 

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

// Fibonacci sequence, recursive version

fun fibb

 

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

 

=={{header|bc}}==

=== iterative ===

 

define fib(x) {

}

fib(1000)

 

=={{header|BCPL}}==

 

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

let start() be

for i=0 to 10 do

{{out}}

<pre>F_0 = 0

=={{header|beeswax}}==

 

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

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

 

Example output:

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

 

Enter n: i0

 

Fib(94)=1293530146158671551

 

=={{header|Befunge}}==

 

=={{header|BlitzMax}}==

 

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

n = n - 1

wend

 

=={{header|Blue}}==

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

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

 

: example ( -- ) 11 fib drop ;

 

=={{header|BQN}}==

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

)

& !this

 

fib$777

{{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).

 

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

<<

]

<<<< Back to #0

 

=={{header|Brat}}==

===Recursive===

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

 

===Tail Recursive===

true? x == 0,

result,

fibonacci = { x |

fib_aux x, 1, 0

 

===Memoization===

 

fibonacci = { x |

{ cache[x] }

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

 

=={{header|Burlesque}}==

 

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

 

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

 

=={{header|C}}==

===Recursive===

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

 

===Iterative===

int fnow = 0, fnext = 1, tempf;

while(--n>0){

}

return fnext;

 

===Analytic===

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

 

long long unsigned fib(unsigned n) {

return floor( (pow(PHI, n) - pow(1 - PHI, n))/sqrt(5) );

 

===Generative===

{{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;

OD;

printf("...\n");

{{out}}

<pre>

 

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

#include <stdio.h>

#include <gmp.h>

}

return 0;

{{out}}

<pre>

 

=== 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);

return (n < 1)? a :(n == 1)? b : Fib(b, a + b, n - 1);

}

 

=== Iterative ===

public static ulong Fib(uint x) {

if (x == 0) return 0;

return next;

}

 

=== Eager-Generative ===

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

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

return fibs;

}

 

=== 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; }

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

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

 

=== Matrix ===

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);

return (ulong)M[0][0];

}

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);

if (n % 2 == 0) M *= N;

}

 

=== Array (Table) Lookup ===

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

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

return fibs[n+46];

}

===Arbitrary Precision===

{{libheader|System.Numerics}}

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;

Console.Write("partial: {0}...{1}", v / BI.Pow(10, vlen - digs), v % BI.Pow(10, digs));

}

{{out}}

<pre>137.209 ms to calculate the 2,000,000th Fibonacci number, number of digits is 417975

partial: 85312949175076415430516606545038251...91799493108960825129188777803453125

</pre>

 

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

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

 

int main()

 

return 0;

 

 

This version does not have an upper bound.

 

#include <gmpxx.h>

 

}

return 0;

 

Version using transform:

#include <vector>

#include <functional>

// "v" now contains the Fibonacci sequence from 0 up

return v[n];

 

Far-fetched version using adjacent_difference:

#include <vector>

#include <functional>

return v[n-1];

}

 

Version which computes at compile time with metaprogramming:

 

template <int n> struct fibo

std::cout<<fibo<46>::value<<std::endl;

return 0;

 

The following version is based on fast exponentiation:

 

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

std::cout << fibonacci(i) << " ";

std::cout << std::endl;

{{out}}

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

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

return 0;

}

{{out}}

<pre>

===Using Standard Template Library===

Possibly less "Far-fetched version".

// Use Standard Template Library to display Fibonacci sequence.

// Nigel Galloway March 30th., 2013

return 0;

}

{{out}}

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

 

=={{header|Cat}}==

dup 1 <=

[]

[dup 1 - fib swap 2 - fib +]

if

 

=={{header|Chapel}}==

var a = 0, b = 1;

 

(a, b) = (b, b + a);

}

 

=={{header|Chef}}==

 

An unobfuscated iterative implementation.

Pour contents of the 4th mixing bowl into baking dish.

 

 

=={{header|Clio}}==

Clio is pure and functions are lazy and memoized by default

 

if n < 2: n

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

 

 

=={{header|Clojure}}==

===Lazy Sequence===

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

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

(fn [[a b]] ;; to produce the next pair, call this function on the current pair

[b (+ a b)]) ;; new prev is old curr, new curr is sum of both previous numbers

 

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

Then, to see the first ten,

 

===Iterative===

 

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)

(if (< max 2)

max

"defn-" means that the function is private (for use only inside this library). The "N" suffixes on integers tell Clojure to use arbitrary precision ints for those.

 

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]

[d (+' c d)]))))]

(first (fib* n))))

 

===Recursive===

A naive slow recursive solution:

 

(case n

0 0

1 1

(+ (fib (- n 1))

 

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]

1 1

(+ (fib (- n 1))

 

=== Using core.async ===

(require '[clojure.core.async

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

(for [i (range 10)]

(println (<!! c))))))

 

=={{header|CLU}}==

fib = iter () yields (int)

a: int := 0

|| int$unparse(nth[int](fib, n)))

end

{{out}}

<pre>F(0) = 0

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

 

set_property(GLOBAL PROPERTY fibonacci_1 1)

set_property(GLOBAL PROPERTY fibonacci_next 2)

get_property(answer GLOBAL PROPERTY fibonacci_${n})

set(${var} ${answer} PARENT_SCOPE)

 

set(s "")

foreach(i RANGE 0 9)

set(s "${s} ${f}")

endforeach(i)

 

<pre> 0 1 1 2 3 5 8 13 21 34 ... 75025 121393 196418 317811 514229 832040</pre>

=={{header|COBOL}}==

===Iterative===

Data Division.

Working-Storage Section.

Move INTERM-RESULT to FORMATTED-RESULT.

Unstring FORMATTED-RESULT delimited by all spaces into FORMATTED-SPACE,FORMATTED-RESULT.

 

===Recursive===

{{works with|GNU Cobol|2.0}}

IDENTIFICATION DIVISION.

PROGRAM-ID. fibonacci-main.

END-EVALUATE

.

 

=={{header|CoffeeScript}}==

===Analytic===

sqrt = Math.sqrt

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

 

===Iterative===

return n if n < 2

[prev, curr] = [0, 1]

[prev, curr] = [curr, curr + prev] for i in [1..n]

 

===Recursive===

 

=={{header|Comefrom0x10}}==

 

===Iterative===

a = 1

i = 1 # start

b = next_b

 

 

=={{header|Common Lisp}}==

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

===Iterative===

(case n

(0 f0)

for a = f0 then b and b = f1 then result

for result = (+ a b)

 

Simpler one:

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

(loop for i from 2 to n do

a b

b c))

 

 

===Recursive===

(if (< n 2)

n

 

 

(if (= n 0)

a

 

Tail recursive and squaring:

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

(fib (ash n -1)

(+ (* q q) (* 2 p q))))) ;p is Fib(2^n-1), q is Fib(2^n).

 

=== Alternate solution ===

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

 

;; Project : Fibonacci sequence

 

(write(+ n 1)) (format t "~a" ": ")

(write (fibonacci n)) (terpri))

Output:

<pre>

 

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

(defmethod fib (n)

(declare ((integer 0 *) n))

 

(defmethod fib ((n (eql 1))) 1)

 

=== List-based iterative ===

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)

(second leo))

leo))

 

{{out}}

we reverse it back when we return it).

 

 

;;; Helper functions

(fibo (1+ lower))

(fibo lower))

{{out}}

<pre>> (fibo 100)

=={{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.

x: 1

y: 1

 

=={{header|Corescript}}==

var previous = 1

var number = 0

 

:kill

 

=={{header|Cowgol}}==

 

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

i := i + 1;

end loop;

 

{{out}}

 

=={{header|Crystal}}==

===Recursive===

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

 

===Iterative===

return n if n < 2

 

 

prevFib

 

===Tail Recursive===

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

 

===Analytic===

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

 

=={{header|D}}==

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

foreach (i, f; fibG(-9))

writef("%d:%d | ", i, f);

{{out}} for n = 85:

<pre>Fib( 85) =

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) {

void main() {

10_000_000.fibonacciMatrix;

 

===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,

void main() {

10_000_000.fibonacci;

 

=={{header|Dart}}==

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

return n;

print(fib(11));

print(fibRec(11));

=={{header|Datalog}}==

Simple recurive implementation for Souffle.

Fib(0, 0).

Fib(1, 1).

Fib(i+2,x+y) :- Fib(i+1, x), Fib(i, y), i+2<=40, i+2>=2.

 

=={{header|DBL}}==

; Fibonacci sequence for DBL version 4 by Dario B.

;

CLOSE 1

 

=={{header|Dc}}==

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

] sF

 

{{out}}

<pre>

 

=== Iterative ===

function FibonacciI(N: Word): UInt64;

var

end;

end;

 

=== Recursive ===

function Fibonacci(N: Word): UInt64;

begin

Result := Fibonacci(N - 1) + Fibonacci(N - 2);

end;

 

=== Matrix ===

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;

 

fib := matrix[0,0];

end;

 

=={{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

 

 

 

=={{header|DWScript}}==

 

begin

if N < 2 then Result := 1

else Result := fib(N-2) + fib(N-1);

 

=={{header|Dyalect}}==

 

if n < 2 {

return n

}

 

 

=={{header|E}}==

var s := [0, 1]

for _ in 0..!n {

}

return s[0]

 

(This version defines <tt>fib(0) = 0</tt> because [http://www.research.att.com/~njas/sequences/A000045 OEIS A000045] does.)

=={{header|EasyLang}}==

 

.

 

Recursive (inefficient):

 

.

 

=={{header|EchoLisp}}==

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

(define (fib n)

(if (< n 2) n

(for ((i 12)) (write (fib i)))

0 1 1 2 3 5 8 13 21 34 55 89

 

=={{header|ECL}}==

===Analytic===

 

 

 

RETURN FibSeq;

 

=={{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.

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

[ 20 ] P0F [ used to clear a ]

 

{{out}}

<pre>00000000000110111</pre>

 

=={{header|Eiffel}}==

class

APPLICATION

 

end

 

=={{header|Ela}}==

Tail-recursive function:

where fib' a b 0 = a

Infinite (lazy) list:

 

=={{header|Elena}}==

{{trans|Smalltalk}}

fibu(n)

else

{

{

int t := ac[1];

public program()

{

{

console.printLine(fibu(i))

}

{{out}}

<pre>

=== 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())

};

console.readChar()

 

=={{header|Elixir}}==

def fib(0), do: 0

def fib(1), do: 1

end

 

 

Using Stream:

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

 

{{out}}

 

=={{header|Elm}}==

Naïve recursive implementation.

fibonacci n = if n < 2 then

n

else

 

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

===version 1===

 

(cond

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

(if (< n 2)

n

 

===version 2===

 

(let (vec i j k)

(if (< n 2)

j (1+ j)

k (1+ k)))

 

<b>Eval:</b>

 

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

 

{{out}}

=={{header|Erlang}}==

===Recursive ===

-module(fib).

-export([fib/1]).

fib(1) -> 1;

fib(N) -> fib(N-1) + fib(N-2).

 

===Iterative ===

-module(fiblin).

-export([fib/1])

fib(N, A, B) -> if N < 1 -> B; true -> fib(N-1, B, A+B) end.

 

 

<b> Evaluate:</b>

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

 

<b> Output:</b>

 

===Iterative 2===

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

 

fib(Iter, Result, Next) -> fib(Iter-1, Next, Result+Next).

 

 

=={{header|ERRE}}==

! derived from my book "PROGRAMMARE IN ERRE"

! iterative solution

 

END PROGRAM

{{out}}

<pre>

==='Recursive' version===

{{works with|Euphoria|any version}}

function fibor(integer n)

if n<2 then return n end if

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

end function

 

==='Iterative' version===

{{works with|Euphoria|any version}}

function fiboi(integer n)

integer f0=0, f1=1, f

return f

end function

 

==='Tail recursive' version===

{{works with|Euphoria|4.0.0}}

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

if n < 1 then

-- example:

? fibot(10) -- says 55

 

==='Paper tape' version===

{{works with|Euphoria|4.0.0}}

include std/mathcons.e -- for PINF constant

 

end while

 

 

=={{header|Excel}}==

 

{{Works with|Office 365 Betas 2021}}

=LAMBDA(n,

APPLYN(n - 2)(

)

)({1;1})

 

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

=LAMBDA(xs,

LAMBDA(ys,

)

)

 

{{Out}}

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

 

=LAMBDA(n,

INDEX(

1

)

 

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

 

=LAMBDA(xs,

LAMBDA(ys,

SEQUENCE(1, COLUMNS(xs))

)

{{Out}}

{| class="wikitable"

=={{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 =

f (bigint 0) (bigint 1) n

> fibonacci 100;;

Lazy evaluated using sequence workflow:

 

The above is extremely slow due to the nested recursions on sequences, which aren't very efficient at the best of times. The above takes seconds just to compute the 30th Fibonacci number!

 

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

fibonacci |> Seq.nth 10000

 

Approach similar to the Matrix algorithm in C#, with some shortcuts involved.

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

iter1 1 1I 1I 0I

|> iter2

 

=={{header|Factor}}==

===Iterative===

dup 2 < [

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

drop

 

===Recursive===

dup 2 < [

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

 

===Tail-Recursive===

dup 1 <

[ 2drop ]

[ [ swap [ + ] keep ] dip 1 - fib2 ]

if ;

 

===Matrix===

{{trans|Ruby}}

 

: fib ( n -- m )

[ { { 0 1 } { 1 1 } } ] dip 1 - m^n

second second

 

=={{header|Falcon}}==

===Iterative===

 

if n < 2: return n

end

return fib

===Recursive===

if n < 2 : return n

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

===Tail Recursive===

return fib_aux(n,0,1)

end

default: return fib_aux(n-1,a+b,a)

end

 

=={{header|FALSE}}==

20n: {First 20 numbers}

 

=={{header|Fancy}}==

def fib {

match self -> {

x fib println

}

 

=={{header|Fantom}}==

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

 

class Main

{

}

}

 

=={{header|Fermat}}==

Array fib[n+1];

fib[1] := 0;

fi;

fi;

 

=={{header|Fexl}}==

 

# (fib n) = the nth Fibonacci number

\fib=

# Now test it:

for 0 20 (\n say (fib n))

 

{{out}}

=={{header|Fish}}==

Outputs Fibonacci numbers until stopped.

 

=={{header|FOCAL}}==

01.20 ASK "N =", N

01.30 SET A=0

02.10 SET T=B

02.20 SET B=A+B

{{out}}

<pre>FIBONACCI NUMBERS

 

=={{header|Forth}}==

 

Or, for negative-index support:

 

rot dup 0 = if drop drop exit then

dup 0 > if 1 - rot rot dup rot +

else 1 + rot rot over - swap then

 

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 ;

16 fibonacci . 987 ok

#F/64 . 93 ok

 

=={{header|Fortran}}==

===FORTRAN IV===

NN=46

DO 1 I=0,NN

5 IFN=IFNM1+IFNM2

9 IFIBO=IFN

{{out}}

<pre>

</pre>

===FORTRAN 77===

FUNCTION IFIB(N)

IF (N.EQ.0) THEN

IFIB=ITEMP0

END

Test program

EXTERNAL IFIB

CHARACTER*10 LINE

901 FORMAT(3(X,I10))

END

{{out}}

<pre>

===Recursive===

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

contains

recursive function fibR(n) result(fib)

case default; fib = fibR(n-1) + fibR(n-2)

end select

===Iterative===

In ISO Fortran 90 or later:

integer, intent(in) :: n

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

end select

end function fibI

 

Test program

use fibonacci

print *, fibr(i), fibi(i)

end do

 

{{out}}

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

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

/// domain for Fibonacci function

/// where result is within nativeUInt

// assign to previous, bc f[current] = f[next] for next iteration

fibonacci := f[previous];

 

=={{header|Frink}}==

All of Frink's integers can be arbitrarily large.

fibonacciN[n] :=

{

return a

}

 

=={{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

POP R1

 

 

=={{header|FunL}}==

=== Recursive ===

fib( 0 ) = 0

fib( 1 ) = 1

 

=== Tail Recursive ===

def

_fib( 0, prev, _ ) = prev

_fib( n, prev, next ) = _fib( n - 1, next, next + prev )

 

 

=== Lazy List ===

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

 

_fib( 0, 1 )

 

 

{{out}}

 

=== Iterative ===

a, b = 0, 1

 

a, b = b, a+b

 

 

=== Binet's Formula ===

 

def fib( n ) =

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

 

=== Matrix Exponentiation ===

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

 

 

for i <- 0..10

 

{{out}}

=== Iterative ===

 

fun main(n: int): int =

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

(b, a + b)

in a

 

=={{header|FutureBasic}}==

=== Iterative ===

 

local fn Fibonacci( n as long ) as long

print : printf @"Compute time: %.3f ms",(fn CACurrentMediaTime-t)*1000

 

Output:

<pre>

 

Compute time: 2.143 ms</pre>

 

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

 

 

 

 

=={{header|GAP}}==

local a;

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

return a[1][2];

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

}

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