DEV Community

Fibonacci in Every Language

Jeremy Grifski on May 22, 2019

Once again, I thought it would be fun to kick off one of these challenges in as many programming languages as possible. Last time, we tried our han...

Read full post

Jon Bristow • May 22 '19 • Edited

Python: (constant time solution)

import math
from decimal import Decimal, getcontext

getcontext().prec = 1000
ONE = Decimal(1)
SQRT_FIVE = Decimal(5).sqrt()
HALF = Decimal(0.5)
PHI = (ONE + SQRT_FIVE) * HALF


def fibonacci(n):
    if n == 0:
        return 0
    return math.floor((PHI ** n) / SQRT_FIVE + HALF)

>>> fib.fibonacci(1000)
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

Edit: This is accurate until F₄₇₆₇ with the given precision.

Jeremy Grifski • May 23 '19

Clever! I didn't realize there was an equation that could so closely approximate the series.

Riccardo Bernardini • May 23 '19 • Edited

It turns out also in DSP, it is a classical example of use of z-trasform for beginners. Actually, the exact form has two terms: phi above and 1/phi and the n-th term is something like C*(phiⁿ +1/phiⁿ ) (more or less, I am going by memory and I am too lazy now to do the computation... ;-)). Of course, since 1/phi is smaller than one, 1/phiⁿ goes rapidly to zero and you get a wonderful approximation with only phiⁿ already for small n.

Jon Bristow • May 23 '19 • Edited

I only know it because my Theory of Computability professor used the “one trillionth Fibonacci number” as a limit to our newfound power understanding recursive solutions. (To find the F_n, you need to find F_n-1 + F_n-2. To find those two numbers, you need to find F_n-2 + 2*F_n-3+F_n-4. This gets towards heat death of the universe level amount of instructions fairly quickly. The loop with saved state gets you down to hours IIRC.)

Then he dropped that this equation existed and my mind kinda exploded.

It wasn’t until trying to get that Project Euler question 2 to complete in under 30 seconds that I ever implemented this. It’s simpler than I expected going in.

Jeremy Grifski • May 23 '19 • Edited

Yeah, it’s not too hard to put together an inefficient solution using recursion (since that’s how the equation is written). If you’re clever, you might save computations in a list. Or, maybe you write an iterative solution which only needs two variables at any give time.

That said, an equation like this is next level. Haha

George Calianu • May 22 '19 • Edited

Solution in Go language:

package main

import (
    "fmt"
    "os"
    "strconv"
)

func fib(n int) {
    a, b := 0, 1
    for i := 0; i < n; i++ {
        a, b = b, a+b
        fmt.Printf("%d: %d\n", i+1, a)
    }
}

const msg = "Usage: please input the count of fibonacci numbers to output"

func main() {
    if len(os.Args) == 1 {
        fmt.Println(msg)
        return
    }
    if os.Args[1] == "" {
        fmt.Println(msg)
        return
    }
    n, err := strconv.Atoi(os.Args[1])
    if err != nil {
        fmt.Println(msg)
        return
    }
    fib(n)
}

Riccardo Bernardini • May 23 '19

Ada (unfortunately seems that no syntax highlighting is available for Ada)

with Ada.Command_Line;
with Ada.Text_IO; use Ada.Text_IO;

use Ada;

procedure Fib is
   Old   : Natural := 1;
   Older : Natural := 0;
   Limit : Positive;
   Tmp   : Positive;

   Bad_Command_Line : exception; 
begin 
   if Command_Line.Argument_Count /= 1 Then
      raise Bad_Command_Line;
   end if;

   Limit := Positive'Value (Command_Line.Argument (1));

   for K in 1..Limit Loop
      Put_Line (Standard_Error, Integer'Image (K) & ":" & Integer'Image(Old));
      Tmp := Old + Older;
      Older := Old;
      Old := Tmp;
   end loop;
exception
   when Bad_Command_Line | Constraint_Error => 
      Put_Line(Standard_Error, 
               "Usage : Please Input The Count of Fibonacci Numbers To Output");

      Command_Line.Set_Exit_Status(Command_Line.Failure);
end Fib;

MagedSaeed • May 25 '19 • Edited

This is my first post here. I am intrigued by such kinds of problems. this is a simple enough JS code, I hope, to achieve the goal.
It is a recursive function, hence I am not expecting very match in terms of performance.

function fib(i){ 
    if (i<=0) return -1;
    else if (i==1) return 1;
    else if (i==2) return 1;
    else return fib(i-1)+fib(i-2)
}

// some examples
//fib(3) returns 2
//fib(5) returns 5

You may try this on chrome dev tools for quick tests.

Avalander • May 24 '19

Racket:

(define (fib n)
  (define (fib-iter i n current previous)
    (if (>= i n)
        current
        (fib-iter (+ i 1) n (+ current previous) current)))
  (fib-iter 0 n 1 0))

mlaj • May 22 '19 • Edited

For anyone interested, this challenge is also available here in 257 languages : rosettacode.org/wiki/Fibonacci_seq...

Jon Bristow • May 22 '19

Also related, Project Euler problem #2

Burdier • May 23 '19 • Edited

haskell

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

Juan F Gonzalez • May 26 '19

Love that the example solution for this challenge was implemented in Haskell. Even being a beginner, I appreciate all that functional goodness.