Algorithm Implementation/Mathematics/Fibonacci Number Program
< Algorithm Implementation < MathematicsC
Recursive version
unsigned int fib(unsigned int n){
if (n < 2)
return n;
else
return fib(n - 1) + fib(n - 2);
}
Ternary Recursive version
unsigned int fib(unsigned int n){
return (n < 2) ? n : fib(n - 1) + fib(n - 2);
}
Tail recursive version
// C++ default arguments used. If implemented in C, call with fib(n, 0, 1) instead.
unsigned int fib(unsigned int n, unsigned int a = 0, unsigned int b = 1) {
if(n < 1) return a;
else return fib(n - 1, a + b, a);
}
Using Binet's formula
#include <math.h>
long fib(unsigned int n) {
double fi = (1 + sqrt(5))/2;
return (pow(fi, n) - pow(1-fi, n)) / sqrt(5);
}
Iterative version
unsigned int fib(unsigned int n)
{
unsigned int i = 0, j = 1, k, t;
for (k = 1; k <= n; ++k)
{
t = i + j;
i = j;
j = t;
}
return j;
}
Exponentiation by squaring
unsigned int fib(unsigned int n){
unsigned int i = n - 1, a = 1, b = 0, c = 0, d = 1, t;
if (n <= 0)
return 0;
while (i > 0){
if (i % 2 == 1){
t = d*(b + a) + c*b;
a = d*b + c*a;
b = t;
}
t = d*(2*c + d);
c = c*c + d*d;
d = t;
i = i / 2;
}
return a + b;
}
Alternate exponentiation by squaring
unsigned int fib(unsigned int n){
unsigned int i = n - 1, a = 1, b = 0, c = 0, d = 1, t;
if (n <= 0)
return 0;
while (i > 0){
while (i % 2 == 0){
t = d*(2*c + d);
c = c*c + d*d;
d = t;
i = i / 2;
}
t = d*(b + a) + c*b;
a = d*b + c*a;
b = t;
i--;
}
return a + b;
}
With matrices
unsigned int fib(unsigned int n){
unsigned int a = 1, ta,
b = 1, tb,
c = 1, rc = 0, tc,
d = 0, rd = 1;
while (n)
{
if (n & 1)
{
tc = rc;
rc = rc*a + rd*c;
rd = tc*b + rd*d;
}
ta = a; tb = b; tc = c;
a = a*a + b*c;
b = ta*b + b*d;
c = c*ta + d*c;
d = tc*tb+ d*d;
n >>= 1;
}
return rc;
}
C#
Iterative version
static int fib(int n)
{
int fib0 = 0, fib1 = 1;
for (int i = 2; i <= n; i++)
{
int tmp = fib0;
fib0 = fib1;
fib1 = tmp + fib1;
}
return (n > 0 ? fib1 : 0);
}
Binet's formula
static int fibBINET(int n)
{
double sqrt5 = Math.Sqrt(5.0);
double phi = (1 + sqrt5 ) / 2;
return (int)((Math.Pow(phi, n) - Math.Pow(-phi, -n)) / sqrt5);
}
Using long numbers
static Num FibonacciNumber(int n)
{
Num n1 = new Num(0);
Num n2 = new Num(1);
Num n3 = new Num(1);
for (int i = 2; i <= n; i++)
{
n3 = n2 + n1;
n1 = n2;
n2 = n3;
}
return n3;
}
struct Num
{
const int digit_base = 0x40000000; // 2^30
List<int> digits;
public int Length { get { return digits.Count; } }
public int this[int index] { get { return digits[index]; } private set { digits[index] = value; } }
public Num(int i)
{
digits = new List<int>();
while (i > 0)
{
digits.Add(i % digit_base);
i /= digit_base;
}
}
public static Num operator +(Num a, Num b)
{
Num n = new Num();
n.digits = new List<int>();
int l = Math.Min(a.Length,b.Length);
int remainder = 0;
for (int i = 0; i < l; i++)
{
n.digits.Add((a[i] + b[i] + remainder) % digit_base);
remainder = (a[i] + b[i] + remainder) / digit_base;
}
Num longer = a.Length > b.Length ? a : b;
for (; l < longer.Length; l++)
{
n.digits.Add((longer[l] + remainder) % digit_base);
remainder = (longer[l] + remainder) / digit_base;
}
if (remainder > 0) n.digits.Add(remainder);
return n;
}
public override string ToString()
{
StringBuilder sb = new StringBuilder();
for (int i = Length - 1; i >= 0; i--)
{
sb.AppendFormat("{0:D" + (digit_base.ToString().Length-1) + "}", this[i]);
}
return sb.ToString();
}
}
D
Basic Recursive Version
ulong fib(uint n){
return (n < 2) ? n : fib(n - 1) + fib(n - 2);
}
Iterative Version
ulong fib(uint n) {
ulong fib0 = 0;
ulong fib1 = 1;
for (auto i = 2; i <= n; i++) {
auto tmp = fib0;
fib0 = fib1;
fib1 = tmp + fib1;
}
return (n > 0 ? fib1 : 0);
}
Memoized Recursive Version
ulong fib(uint n){
static ulong[] memo;
if (n < 0)
return n;
if (n < memo.length)
return memo[n];
auto result = (n < 2) ? n : fib(n - 1) + fib(n - 2);
memo.length = n + 1;
memo[n] = result;
return result;
}
Erlang
fib(0) -> 0;
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).
Arithmetic version
fib(N) ->
S = math:sqrt(5),
round(math:pow(((1 + S) / 2), N) / S).
algorithm taken from the Pascal "more efficient" version, below
F#
Simple recursive
let rec fib x = if x < 2I then x else fib(x - 1I) + fib(x - 2I)
This version uses F# System.Numerics.BigInteger type
Memoized recursive
open System.Collections.Generic
let rec fib n =
let memo = Dictionary<_, _>()
let rec fibInner = function
| n when n = 0I -> 0I
| n when n = 1I -> 1I
| n -> fib(n - 1I) + fib(n - 2I)
if memo.ContainsKey(n) then memo.[n]
else
let res = fibInner n
memo.[n] <- res
res
Tail recursive
let fib n =
let rec fibInner (n, a, b) =
if (n = 0I) then a
else fibInner ((n - 1I), b, (a + b))
fibInner (n, 0I, 1I)
Iterative
let fib n =
if n < 2I then
n
else
let mutable fib1 = 0I
let mutable fib2 = 1I
let mutable i = 2I
let mutable tmp = 0I
while (i <= n) do
i <- i + 1I
tmp <- fib1
fib1 <- fib2
fib2 <- tmp + fib2
fib2
Infinite Sequence Generator
let fibSeq =
Seq.unfold (fun (a, b) -> Some(a, (b, a + b))) (0I, 1I)
let fib n =
fibSeq |> (Seq.skip n) |> Seq.head
Forth
: fib ( n -- fib ) 0 1 rot 0 ?do over + swap loop drop ;
Go
Recursive Solution
func fib(n int) int {
if n < 2 {
return n;
}
return fib(n-1) + fib(n-2);
}
Iterative Solution
func fib(n int) int {
if n == 0 {
return 0
}
a, b := 0, 1
for i := 1; i < n; i++ {
a, b = b, a+b
}
return b
}
Haskell
List version
fib n = fibs 0 1 !! n
where
fibs a b = a : fibs b (a + b)
Tail-recursive version
fib n | n < 0 = undefined
| otherwise = fib' n 0 1
where
fib' 0 a _ = a
fib' n a b = fib' (n - 1) b (a + b)
Simple recursive version
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
Awesome recursive version
fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)]
Or :
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Or :
fibs = map fst $ iterate (\(a,b)->(b,a+b)) (0,1)
Closed-form version
Defines arithmetic operations on a custom data type, and then uses it to run the explicit formula without going via floating point - no rounding or truncation. Calculates the ten millionth fibonacci number in a few seconds (it has roughly two million digits).
module Fib where
-- A type for representing a + b * sqrt n
-- The n is encoded in the type.
data PlusRoot n a = a :+/ a
deriving (Eq, Read, Show)
infix 6 :+/
-- Fetch the n in the root.
class WithRoot n where
getRoot :: Num b => PlusRoot n a -> b
instance (WithRoot n, Num a) => Num (PlusRoot n a) where
(a :+/ b) + (c :+/ d) = (a + c) :+/ (b + d)
x@(a :+/ b) * (c :+/ d) = (a * c + getRoot x * b * d) :+/ (a * d + b * c)
negate (a :+/ b) = negate a :+/ negate b
fromInteger = (:+/ 0) . fromInteger
-- I could implement these with (Ord a) but then we can't use the type
-- with e.g. complex numbers.
abs _ = error "PlusRoot.abs: unimplemented"
signum _ = error "PlusRoot.signum: unimplemented"
instance (WithRoot n, Fractional a) => Fractional (PlusRoot n a) where
fromRational = (:+/ 0) . fromRational
recip x@(a :+/ b) = (a / r) :+/ (negate b / r)
where
r = a*a - getRoot x * b*b
-- Type parameter to PlusRoot. It would be easy to declare similar
-- types for Two or whatever, and get all the above arithmetic for free.
newtype Five = Five Five
instance WithRoot Five where
getRoot _ = 5
-- The formula is phi^n - xi^n / sqrt 5
-- but it's always an integer, i.e. phi^n - xi^n is always a multiple
-- of sqrt 5, so the division isn't strictly necessary - just grab the
-- relevant coefficient.
fib :: Integer -> Integer
fib n = case phi^n - xi^n of
-- The 'round' here is to make the types match; as discussed previously
-- n must be an integer so no actual rounding is done.
_ :+/ n -> round n
where
phi :: PlusRoot Five Rational
phi = (1 :+/ 1) / 2
xi = (1 :+/ negate 1) / 2
For other versions, see :
Dyalog APL
Basic Tail-Recursive Version
fibonacci?{
??0 1
?=0:???
(1??,+/?)? ?-1
}
Array-Oriented Version
fibonacci?{+/{?!??}(??)-?IO}
Other Versions
See Fibonacci at the Dynamic Functions Database
Io
Generic method version
fib := method(n,
if(n < 4,
(n + n % 2) / 2,
(n % 2 * 2 - 1) * fib((n + n % 3) / 2 - 1) ** 2 + fib((n - n % 3) / 2 + 1) ** 3
)
)
Polymorphic method version
Number fibonacci := method((self - 1) fibonacci + (self -2) fibonacci)
1 fibonacci = 1
0 fibonacci = 0
Java
Recursive version
public void run(int n)
{
if (n <= 0)
{
return;
}
run(n,1,0);
}
private void run(int n, int eax, int ebx)
{
n--;
if (n == 0)
{
System.out.println(eax+ebx);
return;
}
run(n,ebx,eax+ebx);
}
Variations on the recursive version
/* Recursive versions. Horribly inefficient. Use iterative/memoized versions instead */
public long fib(long n) {
if (n<2) {
return n;
}
return fib(n-1) + fib(n-2);
}
public long fib2(long n) {
return (n < 2) ? n : getValue(n - 1) + getValue(n - 2);
}
Iterative version
/**
* Source based on
* http://20bits.com/2007/05/08/introduction-to-dynamic-programming/
* as at 9-May-2007
*/
private long fibonacci(int n)
{
long n2 = 0;
long n1 = 1;
long tmp;
for (int i=n ; i>2 ; i--) {
tmp = n2;
n2 = n1;
n1 = n1 + tmp;
}
return n2 + n1;
}
Simpler Iterative Version
/**
* returns the Nth number in the Fibonacci sequence
*/
public int fibonacci(int N) {
int lo = 0;
int hi = 1;
for (int i = 0; i < N; i++) {
hi = lo + hi;
lo = hi - lo;
}
return lo;
}
Memoized version
private int[] fibs; // array for memoized fibonacci numbers
public int fib(int n) {
if (n < 2) {
return n;
}
if (fibs == null) { // initialise array to first size asked for
fibs = new int[n + 1];
} else if (fibs.length < n) { // expand array
int[] newfibs = new int[n + 1]; // inefficient if looping through values of n
System.arraycopy(fibs, 0, newfibs, 0, fibs.length);
fibs = newfibs;
}
if (fibs[n] == 0) {
fibs[n] = fib(n - 1) + fib(n - 2);
}
return fibs[n];
}
Iterative Memoized version
public int fib(int n) {
if (n < 2) {
return n;
}
int[] f = new int[n+1];
f[0] = 0;
f[1] = 1;
for(int i = 2;i<=n;i++) {
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
Linotte
Fibonacci: Principal : Rôles : n :: nombre Actions : "Entrez un nombre :" ! n ? fibo(n) ! Fibo : Rôles : * n :: nombre Actions : si n < 2 alors retourne n retourne fibo(n-1) + fibo(n-2)
Lexico (in spanish)
clase Fib
publicos:
mensajes:
Fib nop
Fibonacci(deme n es una cantidad) es_funcion cantidad
{
los objetos uno, dos, tres, i, respuesta son cantidades
copie 0 en uno
copie 1 en dos
variando i desde 1 hasta n haga:
{
copie uno en respuesta
copie uno + dos en tres
copie dos en uno
copie tres en dos
}
retornar uno
}
/**********************************/
tarea
{
el objeto f es un Fib
muestre "el 5: ", f.Fibonacci(doy 5)
}
Lua
function fib(n)
local a, b = 0, 1
while n > 0 do
a, b = b, a + b
n = n - 1
end
return a
end
Recursive version
function fib(n)
if n > 1 then n = fib(n - 1) + fib(n - 2) end
return n
end
Matlab
Recursive snippet
function F = fibonacci_recursive(n)
if n < 2
F = n;
else
F = fibonacci_recursive(n-1) + fibonacci_recursive(n-2);
end
Iterative snippet
function F = fibonacci_iterative(n)
first = 0;
second = 1;
third = 0;
for q = 1:n,
third = first + second;
first = second;
second = third;
end
F = first;
Maxima
Recursive version
fib(n):=
if n < 2 then
n
else
fib(n - 1) + fib(n - 2)
$
Lucas form
fib(n):=(%phi^n-(-%phi)^-n)/sqrt(5);
Iterative version
fib(n) := block( [i,j,k], i : 1, j : 0, for k from 1 thru n do [i,j] : [j,i + j], return(j) )$
Exponentiation by squaring
fib(n) := block( [i,F,A], if n <= 0 then return(0), i : n - 1, F : matrix([1,0],[0,1]), A : matrix([0,1],[1,1]), while i > 0 do block( if oddp(i) then F : F.A, A : A^^2, i : quotient(i,2) ), return(F[2,2]) )$
O'Caml
let fib n =
let rec fibonacci n =
match n with
| 0 -> (0, 0)
| 1 -> (0, 1)
| m ->
let (a, b) = fibonacci (m-1) in
(b, a+b)
in
let (_, k) = fibonacci n in
k;;
Pascal
function F(n: integer): integer;
begin
case n of
1,2: Result:=1
else Result:=F(n-1)+F(n-2) end;
end;
A bit more efficient
function F(n: integer): integer;
begin
Result:=Round(Power((1+sqrt(5))/2, n)/sqrt(5));
end;
Note that Power is usually defined in Math, which is not included by default.
For most compilers it's possible to improve performance by using the Math.IntPower instead of the Math.Power.
Iterative version also for negative arguments
function fib(n:integer):extended;
var i:integer;
fib0,fib1:extended;
begin
fib0:=0;
fib1:=1;
for i:=1 to abs(n) do
begin
fib0:=fib0+fib1;
fib1:=fib0-fib1;
end;
if (n<0)and(not odd(n)) then fib0:=-fib0;
fib:=fib0;
end:
Perl
sub fib {
my ($n, $a, $b) = (shift, 0, 1);
($a, $b) = ($b, $a + $b) while $n-- > 0;
$a;
}
Recursive versions
sub fib {
my $n = shift;
return $n if $n < 2;
return fib($n - 1) + fib($n - 2);
}
# returns F_n in a scalar context
# returns all elements in the sequence up to F_n in a list context
# only one recursive call
sub fib {
my ($n) = @_;
return (0) if ($n == 0);
return (0, 1) if ($n == 1);
my @fib = fib($n - 1);
return (@fib, $fib[-1] + $fib[-2]);
}
Binary recursion, snippet
sub fibo;
sub fibo {$_ [0] < 2 ? $_ [0] : fibo ($_ [0] - 1) + fibo ($_ [0] - 2)}
Runs in Θ(F(n)) time, which is Ω(1.6n).
Binary recursion with special Perl "caching", snippet
use Memoize;
memoize 'fibo';
sub fibo;
sub fibo {$_ [0] < 2 ? $_ [0] : fibo ($_ [0] - 1) + fibo ($_ [0] - 2)}
Iterative, snippet
sub fibo
{
my ($n, $a, $b) = (shift, 0, 1);
($a, $b) = ($b, $a + $b) while $n-- > 0;
$a;
}
PHP
Iterative version
function generate_fibonacci_sequence($length)
{
for($l = [0, 1], $i = 2, $x = 0; $i < $length; $i++) {
$l[] = $l[$x++] + $l[$x];
}
return $l;
}
Recursive version
function fib($n)
{
if ($n < 2) {
return $n;
}
return fib($n - 1) + fib($n - 2);
}
Ternary version
function fib($n)
{
return ($n < 2) ? $n : fib( $n-1 )+fib( $n-2 );
}
OOP version
class Fibonacci
{
public $Begin = 0;
public $Next;
public $Amount;
public $i;
public function __construct( $Begin, $Amount ) {
$this->Begin = 0;
$this->Next = 1;
$this->Amount = $Amount;
}
public function _do() {
for( $this->i = 0; $this->i < $this->Amount; $this->i++ ) {
$Value = ( $this->Begin + $this->Next );
echo $this->Begin . ' + ' . $this->Next . ' = ' . $Value . '<br />';
$this->Begin = $this->Next;
$this->Next = $Value;
}
}
}
$Fib = new fibonacci( 0, 6 );
echo $Fib->_do();
Alternate version
function fib($n) {
return round(pow(1.6180339887498948482, $n) / 2.2360679774998);
}
Python
Recursive version
def fib(n):
if n < 2: return n
return fib(n - 1) + fib(n - 2)
Or :
def fib( n ):
return n if n < 2 else fib( n - 1 ) + fib( n - 2 )
Recursive with memoization
m = {0: 1, 1: 1}
def fib(n):
#assert n >= 0
if n not in m:
m[n] = fib(n-1) + fib(n-2)
return m[n]
Lucas form
def fib(n):
fi = (1 + sqrt(5))/2
return (fi**n - (-fi)**-n)/sqrt(5)
Iterative version
def fib(n):
i,j = 1,0
for k in range(1,n + 1):
i,j = j, i + j
return j
Exponentiation by squaring
def fib(n):
if n <= 0:
return 0
i = n - 1
a,b = 1,0
c,d = 0,1
while i > 0:
if i % 2 == 1:
a,b = d*b + c*a, d*(b + a) + c*b
c,d = c**2 + d**2, d*(2*c + d)
i = i / 2
return a + b
Lucas sequence identities
def fib(n):
if n <= 0:
return 0
# n = 2**r*s where s is odd
s, r = n, 0
while s & 1 == 0:
r, s = r+1, s/2
# calculate the bit reversal t of (odd) s
# e.g. 19 (10011) <=> 25 (11001)
t = 0
while s > 0:
if s & 1 == 1:
t, s = t+1, s-1
else:
t, s = t*2, s/2
# use the same bit reversal process
# to calculate the sth Fibonacci number
# using Lucas sequence identities
u, v, q = 0, 2, 2
while t > 0:
if t & 1 == 1:
# u, v of x+1
u, v = (u + v) / 2, (5*u + v) / 2
q, t = -q, t-1
else:
# u, v of 2*x
u, v = u * v, v * v - q
q, t = 2, t/2
# double s until we have
# the 2**r*sth Fibonacci number
while r > 0:
u, v = u * v, v * v - q
q, r = 2, r-1
return u
Lucas sequence identities, recursion
As with the iterative version, this solution is also O(log n) with arbitrary precision.
def fib(n):
def fib_inner(n):
if n == 0:
return 0, 2
m = n >> 1
# q = 2*(-1)**m
q = -2 if (m & 1) == 1 else 2
u, v = fib_inner(m)
u, v = u * v, v * v - q
if n & 1 == 1:
# u, v of 2m+1
u1 = (u + v) >> 1
return u1, 2*u + u1
else:
# u, v of 2m
return u, v
if n <= 0:
return 0
# the outermost loop is unrolled
# to avoid calculating an unnecessary v
m = n >> 1
u, v = fib_inner(m)
if n & 1 == 1:
# u of m+1
u1 = (u + v) >> 1
# u of 2m+1
return u*u + u1*u1
else:
# u of 2m
return u * v
REBOL
Recursive version
fib: func [n [integer!]] [
either n < 2 [n] [(fib n - 1) + (fib n - 2)]
]
Ruby
class Integer
def fib
@n = self.abs
if @n < 2
return @n
else
return (@n-1).fib + (@n-2).fib
end
end
end
Alternate:
class Integer
def fib
@n = self.abs
(@n<2)?(return @n):(return (@n-1).fib+(@n-2).fib)
end
end
# you run it like this
puts 10.fib # output: 55
puts 15.fib # output: 610
Recursive
def fib n
return n if n < 2
fib(n - 1) + fib(n - 2)
end
Generator
class FibGenerator
def initialize(n)
@n = n
end
def each
a, b = 1, 1
@n.times do
yield a
a, b = b, a+b
end
end
include Enumerable
end
def fibs(n)
FibGenerator.new(n)
end
#use like this
fibs(6).each do |x|
puts x
end
Arithmetic version
def f(n)
((((1+Math.sqrt(5))/2)**n)/Math.sqrt(5)+0.5).floor
end
Memoized Version
fibmemo=Hash.new{|h,k| h[k-1]+h[k-2]}
fibmemo[0]=1
fibmemo[1]=1
def fib n
fibmemo[n]
end
Scheme
Tree-recursive version
(define (fib n)
(if (<= n 1)
n
(+ (fib (- n 1)) (fib (- n 2)))))
Iterative (tail-recursive) version
(define (fib n)
(define (iter a b count)
(if (<= count 0)
a
(iter b (+ a b) (- count 1))))
(iter 0 1 n))
Named-let, Iterative version
(define (fib n)
(let loop ((a 0) (b 1)
(count n))
(if (<= count 0) a
(loop b (+ a b) (- count 1))))))
Lucas form
(define fib
(let* ((sqrt5 (inexact->exact (sqrt 5)))
(fi (/ (+ sqrt5 1) 2)))
(lambda (n)
(round (/ (- (expt fi n) (expt (- fi 1) n)) sqrt5)))))
Logarithmic-time Version
This version squares the Fibonacci transformation, allowing calculations in log2(n) time:
(define (fib-log n)
"Fibonacci, in logarithmic time."
(define (fib-iter a b p q count)
(cond ((= count 0) b)
((even? count)
(fib-iter a b
(+ (* p p) (* q q))
(+ (* 2 p q) (* q q))
(/ count 2)))
(else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p q
(- count 1)))))
(fib-iter 1 0 0 1 n))
UCBLogo
to fib :n output (cascade :n [?1+?2] 1 [?1] 0) end
Recursive version
to fib :n if :n<2 [output 1] output (fib :n-1)+(fib :n-2) end
VB.NET
Array oriented version
Dim i As Integer = 2
Dim sequencelength As Integer = 50
Dim fibonacci(sequencelength) As Integer
fibonacci(0) = 0
fibonacci(1) = 1
While i <> sequencelength
fibonacci(i) = fibonacci(i - 1) + fibonacci(i - 2)
i += 1
End While
Recursive Version
Private Function fibonacci(ByVal i as integer) As Integer
If i < 1 Then
Return -1
ElseIf i < 2 Then
Return i
Else
Return fibonacci(i-1) + fibonacci(i-2)
End If
End Function
JavaScript
Recursive version
function fib(n) {
return n < 2 ? n : fib(n - 1) + fib(n - 2);
}
Alternative recursive version
function fib(n, prev, cur) {
if (prev == null) prev = 0;
if (cur == null) cur = 1;
if (n < 2) return cur;
return fib(n--, cur, cur + prev);
}
Prev and cur is optional arguments.
Iterative version
function fibonacci(n) {
var i = 1, j = 0, k, t;
for (k = 1; k <= Math.abs(n); k++) {
t = i + j;
i = j;
j = t;
}
if (n < 0 && n % 2 === 0) j = -j;
return j;
}
This example supports negative arguments.
Lucas form
function fibonacci(n) {
var sqrt5 = Math.sqrt(5);
var fi = (1 + sqrt5) / 2;
return Math.round((Math.pow(fi, n) - Math.pow(-fi, -n)) / sqrt5);
}
Binets formula
function fibonacci(n) {
var sqrt5 = Math.sqrt(5);
var fi = (1 + sqrt5) / 2;
return Math.round((Math.pow(fi, n + 1) - Math.pow(1 - fi, n + 1)) / sqrt5);
}
Algorithm from the Pascal "more efficient" version
function fibonacci(n) {
var sqrt5 = Math.sqrt(5);
return Math.round(Math.pow(((1 + sqrt5) / 2), n) / sqrt5);
}
Common Lisp
Lucas form
(defun fib (n)
(cond
((= n 0) 0)
((or (= n 1) (= n 2)) 1)
((= 0 (mod n 2)) (-
(expt (fib (+ (truncate n 2) 1)) 2)
(expt (fib (- (truncate n 2) 1)) 2)))
(t (+ (expt (fib (truncate n 2)) 2)
(expt (fib (+ (truncate n 2) 1)) 2)))))
(fib (parse-integer (second *posix-argv*))) ;
Recursive version
(defun fib (x)
(if (or (zerop x) (= x 1)) 1
(+ (fib (- x 1)) (fib (- x 2)))))
(print (fib 10))
PostScript
Iterative
20 % how many Fibonacci numbers to print
1 dup
3 -1 roll
{
dup
3 -1 roll
dup
4 1 roll
add
3 -1 roll
=
}
repeat
Stack recursion
This example uses recursion on the stack.
% the procedure
/fib
{
dup dup 1 eq exch 0 eq or not
{
dup 1 sub fib
exch 2 sub fib
add
} if
} def
% prints the first twenty fib numbers
/ntimes 20 def
/i 0 def
ntimes {
i fib =
/i i 1 add def
} repeat
PL/SQL
Iterative snippet
CREATE OR REPLACE PROCEDURE fibonacci(lim NUMBER) AS
fibupper NUMBER(38);
fiblower NUMBER(38);
fibnum NUMBER(38);
i NUMBER(38);
BEGIN
fiblower := 0;
fibupper := 1;
fibnum := 1;
FOR i IN 1 .. lim
LOOP
fibnum := fiblower + fibupper;
fiblower := fibupper;
fibupper := fibnum;
DBMS_OUTPUT.PUT_LINE(fibnum);
END LOOP;
END;
This article is issued from Wikibooks. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.