Algorithm Implementation/Mathematics/Fibonacci Number Program (original) (raw)

Fibonacci is similar to a "hello world" for many functional programming languages, since it can involve paradigms like pattern matching, memoization, and bog-standard tail recursion (which is equivalent to iteration). However, iteration or tail-recursion in linear time is only the first step: more clever exponentiation runs in logarithmic time.

Although the Binet/Lucas formula is technically also exponentiation, its use of floating-point numbers makes it less attractive than the matrix-based solution. In addition, the above discussion of complexity and indeed most of the code here assumes that both addition and multiplication are done in a single step, which is not the case for big, exponentially-growing numbers easily created by fibonacci calculation.

An explanation of many of the following above can be found in nayuki's post.

unsigned int fib(unsigned int n) { // This is exactly the same as a ternary expression if (n < 2) return n; else return fib(n - 1) + fib(n - 2); }

// C++ default arguments used. If implemented in C, call with fib(n, 0, 1) instead. unsigned int fib(unsigned int n, unsigned int acc = 0, unsigned int prev = 1) { if (n < 1) return acc; else return fib(n - 1, prev + acc, acc); }

#include <math.h>

const static double phi = (1 + sqrt(5)) / 2; long fib(unsigned int n) { return (pow(phi, n) - pow(1 - phi, n)) / sqrt(5); }

unsigned int fib(unsigned int n) { unsigned int i = 0, j = 1, t; if (n == 0) return 0; for (k = 1; k < n; ++k) { t = i + j; i = j; j = t; } return j; }

// This version is more "parallel" in the sense of a more unrolled loop. unsigned int fib(int n) { unsigned int i = 0, j = 1, k = 1; for (; n >= 3; n -= 3) { i = j + k; j = i + k; k = i + j; } return n == 0 ? i : n == 1 ? j : k; }

// A 2x2 matrix: m00, m01; m10, m11. typedef struct mat22_s { unsigned int m00, m01, m10, m11; } mat22_t;

// Matrix multiplication. inline static mat22_t mat22_mul(mat22_t a, mat22_t b) { return (mat22_t){ a.m00 * b.m00 + a.m01 * b.m10, a.m00 * b.m01 + a.m01 * b.m11, a.m10 * b.m00 + a.m11 * b.m10, a.m10 * b.m01 + a.m11 * b.m11}; }

// This is a less concise version written for clarity. The compiler should be able to optimize the boilerplate out. unsigned int fib(unsigned int n) { // Matrix holds F(N-1), F(N); F(N), F(N+1). // This is an identity matrix, also the 0th power of matrix. mat22_t result = {1, 0, 0, 1}; mat22_t matrix = {1, 1, 1, 0}; for (; n > 0; n /= 2) { if (n % 2 == 1) { result = mat22_mul(matrix, result); } matrix = mat22_mul(matrix, matrix); } return result.m10; }

// A moderately compact version of the matrix calculation. unsigned int fib(unsigned int n) { // [a b] is "result"; [c d] is "matrix". unsigned int a = 1, b = 0, c = 0, d = 1, t; if (n == 0) return 0; n = n - 1; while (n > 0) { if (n % 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; n = n / 2; } return a + b; }

A similar alternative is based on Lucas numbers.

// Nayuki's fast doubling code. Runs from high to low bits. #include <limits.h>

static inline unsigned int log2i(unsigned int n) { #if defined(__has_builtin) && __has_builtin(__builtin_clz) return sizeof (unsigned int) * CHAR_BIT - __builtin_clz(n) - 1; #else return sizeof (unsigned int) * CHAR_BIT - 1; // pessimistic guess #endif }

unsigned int fib(unsigned int n) { // Two numbers for iteration. At the end, a = F(N) and b = F(N+1). unsigned int a = 0, b = 1; // log2i is not reliable for n = 0. We know better. unsigned int mask = n == 0 ? 0 : 1 << log2i(n);

for (; mask > 0; mask /= 2) {
    // F(2k)   = F(k) * (2 * F(k+1) + F(k))
    unsigned int new_a = a * (b * 2 - a);
    // F(2k+1) = F(k+1)**2 + F(k)**2
    unsigned int new_b = a * a + b * b;
    a = new_a;  
    b = new_b;
    if (n & mask) {
         new_b = a + b;
         a = b;
         b = new_b;
    }
}
return a;

}

C# code is essentially the same as C with some static method specifiers.

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

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

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

}

ulong fib(uint n){ return (n < 2) ? n : fib(n - 1) + fib(n - 2); }

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

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

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

fib(N) -> S = math:sqrt(5), round(math:pow(((1 + S) / 2), N) / S).

algorithm taken from the Pascal "more efficient" version, below

let rec fib x = if x < 2I then x else fib(x - 1I) + fib(x - 2I)

This version uses F# System.Numerics.BigInteger type

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

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)

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

let fibSeq = Seq.unfold (fun (a, b) -> Some(a, (b, a + b))) (0I, 1I)

let fib n = fibSeq |> (Seq.skip n) |> Seq.head

: fib ( n -- fib ) 0 1 rot 0 ?do over + swap loop drop ;

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

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

}

fib n = fibs 0 1 !! n where fibs a b = a : fibs b (a + b)

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)

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

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)

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 = aa - getRoot x * bb

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

fibonacci?{
 ??0 1  ?=0:??? (1??,+/?)? ?-1 }

fibonacci?{+/{?!??}(??)-?IO}

See Fibonacci at the Dynamic Functions Database

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

Number fibonacci := method((self - 1) fibonacci + (self -2) fibonacci) 1 fibonacci = 1 0 fibonacci = 0

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

/* Recursive versions. Horribly inefficient. Use iterative/memoized versions instead */ public long fib(long n) { if (n < 2) { return 1; } return fib(n - 1) + fib(n - 2); }

public long fib2(long n) { return (n < 2) ? n : getValue(n - 1) + getValue(n - 2); }

/**

/**

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

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

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)

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

function fib(n) local a, b = 0, 1 while n > 0 do a, b = b, a + b n = n - 1 end return a end

function fib(n) if n > 1 then n = fib(n - 1) + fib(n - 2) end return n end

function F = fibonacci_recursive(n) if n < 2 F = n; else F = fibonacci_recursive(n-1) + fibonacci_recursive(n-2); end

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;

fib(n):= if n < 2 then n else fib(n - 1) + fib(n - 2) $

fib(n):=(%phi^n-(-%phi)^-n)/sqrt(5);

fib(n) := block( [i,j,k], i : 1, j : 0, for k from 1 thru n do [i,j] : [j,i + j], return(j) )$

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]) )$

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

function F(n: integer): integer; begin case n of 1,2: Result:=1 else Result:=F(n-1)+F(n-2) end; end;

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.

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:

sub fib { my ($n, a,a, a,b) = (shift, 0, 1); ($a, b)=(b) = (b)=(b, a+a + a+b) while $n-- > 0; $a; }

sub fib { my $n = shift; return nifn if nifn < 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[-1] + fib[−1]+fib[-2]); }

sub fibo; sub fibo {$_ [0] < 2 ? [0]:fibo(_ [0] : fibo ([​0]:fibo(_ [0] - 1) + fibo ($_ [0] - 2)}

Runs in Θ(F(n)) time, which is Ω(1.6_n_).

use Memoize; memoize 'fibo'; sub fibo; sub fibo {$_ [0] < 2 ? [0]:fibo(_ [0] : fibo ([​0]:fibo(_ [0] - 1) + fibo ($_ [0] - 2)}

sub fibo { my ($n, a,a, a,b) = (shift, 0, 1); ($a, b)=(b) = (b)=(b, a+a + a+b) while $n-- > 0; $a; }

function generate_fibonacci_sequence($length) { for($l = [0, 1], i=2,i = 2, i=2,x = 0; i<i < i<length; $i++) { l[]=l[] = l[]=l[$x++] + l[l[l[x]; }

return $l; }

function fib($n) { if ($n < 2) { return $n; }

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

function fib($n) { return ($n < 2) ? n:fib(n : fib( n:fib(n-1 )+fib( $n-2 ); }

class Fibonacci { public $Begin = 0; public $Next; public $Amount; public $i;

 public function __construct( <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>B</mi><mi>e</mi><mi>g</mi><mi>i</mi><mi>n</mi><mo separator="true">,</mo></mrow><annotation encoding="application/x-tex">Begin, </annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8778em;vertical-align:-0.1944em;"></span><span class="mord mathnormal" style="margin-right:0.05017em;">B</span><span class="mord mathnormal">e</span><span class="mord mathnormal" style="margin-right:0.03588em;">g</span><span class="mord mathnormal">in</span><span class="mpunct">,</span></span></span></span>Amount ) {
 
     $this->Begin	= 0;
     $this->Next		= 1;
  <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>t</mi><mi>h</mi><mi>i</mi><mi>s</mi><mo>−</mo><mo>&gt;</mo><mi>A</mi><mi>m</mi><mi>o</mi><mi>u</mi><mi>n</mi><mi>t</mi><mo>=</mo></mrow><annotation encoding="application/x-tex">this-&gt;Amount	= </annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7778em;vertical-align:-0.0833em;"></span><span class="mord mathnormal">t</span><span class="mord mathnormal">hi</span><span class="mord mathnormal">s</span><span class="mord">−</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">&gt;</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathnormal">A</span><span class="mord mathnormal">m</span><span class="mord mathnormal">o</span><span class="mord mathnormal">u</span><span class="mord mathnormal">n</span><span class="mord mathnormal">t</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span></span></span></span>Amount;
 
 }
 
 public function _do() {
 
     for( <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>t</mi><mi>h</mi><mi>i</mi><mi>s</mi><mo>−</mo><mo>&gt;</mo><mi>i</mi><mo>=</mo><mn>0</mn><mo separator="true">;</mo></mrow><annotation encoding="application/x-tex">this-&gt;i = 0; </annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7778em;vertical-align:-0.0833em;"></span><span class="mord mathnormal">t</span><span class="mord mathnormal">hi</span><span class="mord mathnormal">s</span><span class="mord">−</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">&gt;</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6595em;"></span><span class="mord mathnormal">i</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.8389em;vertical-align:-0.1944em;"></span><span class="mord">0</span><span class="mpunct">;</span></span></span></span>this->i < <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>t</mi><mi>h</mi><mi>i</mi><mi>s</mi><mo>−</mo><mo>&gt;</mo><mi>A</mi><mi>m</mi><mi>o</mi><mi>u</mi><mi>n</mi><mi>t</mi><mo separator="true">;</mo></mrow><annotation encoding="application/x-tex">this-&gt;Amount; </annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7778em;vertical-align:-0.0833em;"></span><span class="mord mathnormal">t</span><span class="mord mathnormal">hi</span><span class="mord mathnormal">s</span><span class="mord">−</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">&gt;</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.8778em;vertical-align:-0.1944em;"></span><span class="mord mathnormal">A</span><span class="mord mathnormal">m</span><span class="mord mathnormal">o</span><span class="mord mathnormal">u</span><span class="mord mathnormal">n</span><span class="mord mathnormal">t</span><span class="mpunct">;</span></span></span></span>this->i++ ) {

      <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>V</mi><mi>a</mi><mi>l</mi><mi>u</mi><mi>e</mi><mo>=</mo><mo stretchy="false">(</mo></mrow><annotation encoding="application/x-tex">Value = ( </annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6944em;"></span><span class="mord mathnormal">Va</span><span class="mord mathnormal" style="margin-right:0.01968em;">l</span><span class="mord mathnormal">u</span><span class="mord mathnormal">e</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span></span></span></span>this->Begin + $this->Next );

         echo <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>t</mi><mi>h</mi><mi>i</mi><mi>s</mi><mo>−</mo><mo>&gt;</mo><mi>B</mi><mi>e</mi><mi>g</mi><mi>i</mi><mi>n</mi><msup><mi mathvariant="normal">.</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup><msup><mo>+</mo><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup><mi mathvariant="normal">.</mi></mrow><annotation encoding="application/x-tex">this-&gt;Begin . &#x27; + &#x27; . </annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7778em;vertical-align:-0.0833em;"></span><span class="mord mathnormal">t</span><span class="mord mathnormal">hi</span><span class="mord mathnormal">s</span><span class="mord">−</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">&gt;</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.9463em;vertical-align:-0.1944em;"></span><span class="mord mathnormal" style="margin-right:0.05017em;">B</span><span class="mord mathnormal">e</span><span class="mord mathnormal" style="margin-right:0.03588em;">g</span><span class="mord mathnormal">in</span><span class="mord"><span class="mord">.</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.7519em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">′</span></span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin"><span class="mbin">+</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.7519em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">′</span></span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.1056em;"></span><span class="mord">.</span></span></span></span>this->Next . ' = ' . $Value . '<br />';

      <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>t</mi><mi>h</mi><mi>i</mi><mi>s</mi><mo>−</mo><mo>&gt;</mo><mi>B</mi><mi>e</mi><mi>g</mi><mi>i</mi><mi>n</mi><mo>=</mo></mrow><annotation encoding="application/x-tex">this-&gt;Begin	= </annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7778em;vertical-align:-0.0833em;"></span><span class="mord mathnormal">t</span><span class="mord mathnormal">hi</span><span class="mord mathnormal">s</span><span class="mord">−</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">&gt;</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.8778em;vertical-align:-0.1944em;"></span><span class="mord mathnormal" style="margin-right:0.05017em;">B</span><span class="mord mathnormal">e</span><span class="mord mathnormal" style="margin-right:0.03588em;">g</span><span class="mord mathnormal">in</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span></span></span></span>this->Next;
      <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>t</mi><mi>h</mi><mi>i</mi><mi>s</mi><mo>−</mo><mo>&gt;</mo><mi>N</mi><mi>e</mi><mi>x</mi><mi>t</mi><mo>=</mo></mrow><annotation encoding="application/x-tex">this-&gt;Next		= </annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7778em;vertical-align:-0.0833em;"></span><span class="mord mathnormal">t</span><span class="mord mathnormal">hi</span><span class="mord mathnormal">s</span><span class="mord">−</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">&gt;</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathnormal" style="margin-right:0.10903em;">N</span><span class="mord mathnormal">e</span><span class="mord mathnormal">x</span><span class="mord mathnormal">t</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span></span></span></span>Value;
         
     }
 
 }

}

$Fib = new fibonacci( 0, 6 ); echo $Fib->_do();

function fib($n) { return round(pow(1.6180339887498948482, $n) / 2.2360679774998); }

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 )

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]

def fib(n): phi = (1 + sqrt(5))/2 return int((phin - (-phi)-n)/sqrt(5))

def fib(n): i,j = 1,0 for k in range(1,n + 1): i,j = j, i + j return j

def fib(n): a,b = 1,0 for i in range(n): yield b a, b = b, a+b

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 = db + ca, d*(b + a) + cb c,d = c2 + d2, d(2*c + d) i = i >> 1 return a + b

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

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, 2u + 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

fib: func [n [integer!]] [ either n < 2 [n] [(fib n - 1) + (fib n - 2)] ]

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

def fib n return n if n < 2 fib(n - 1) + fib(n - 2) end

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

def f(n) ((((1+Math.sqrt(5))/2)**n)/Math.sqrt(5)+0.5).floor end

fibmemo=Hash.new{|h,k| h[k-1]+h[k-2]} fibmemo[0]=1 fibmemo[1]=1

def fib n fibmemo[n] end

(define (fib n) (if (<= n 1) n (+ (fib (- n 1)) (fib (- n 2)))))

(define (fib n) (define (iter a b count) (if (<= count 0) a (iter b (+ a b) (- count 1)))) (iter 0 1 n))

(define (fib n) (let loop ((a 0) (b 1) (count n)) (if (<= count 0) a (loop b (+ a b) (- count 1))))))

(define fib (let* ((sqrt5 (inexact->exact (sqrt 5))) (fi (/ (+ sqrt5 1) 2))) (lambda (n) (round (/ (- (expt fi n) (expt (- fi 1) n)) sqrt5)))))

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

to fib :n output (cascade :n [?1+?2] 1 [?1] 0) end

to fib :n if :n<2 [output 1] output (fib :n-1)+(fib :n-2) end

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

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

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

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.

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.

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

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

function fibonacci(n) { var sqrt5 = Math.sqrt(5); return Math.round(Math.pow(((1 + sqrt5) / 2), n) / sqrt5); }

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

(defun fib (x) (if (or (zerop x) (= x 1)) 1 (+ (fib (- x 1)) (fib (- x 2)))))

(print (fib 10))

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

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

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;