DEV Community

Jeremy Grifski
Jeremy Grifski

Posted on

Fibonacci in Every Language

#challenge #polyglot #beginners #opensource

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 hand at Fizz Buzz in Every Language. If you haven't gotten a chance to share a solution in your favorite language, go for it! Otherwise, we're going to tackle Fibonacci in Every Language today.

The Challenge

As many of you are probably aware, Fibonacci is a term often associated with a particular sequence of numbers where the nth term is the sum of the previous two terms—or more formally: Fn = Fn-1 + Fn-2. For our purposes, we'll start the sequence with a pair of ones:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

The goal in this challenge is to write a program in a language of your choice to output the sequence up to the nth term. In other words, the program should be able to be executed like:

./fib 5
Enter fullscreen mode Exit fullscreen mode

and, output the sequence above up to the fifth term:

1, 1, 2, 3, 5
Enter fullscreen mode Exit fullscreen mode

If you're feeling adventurous, you could try making your program conform to the requirements outlined in the Sample Programs repo. In addition to outputting the sequence, you should also output the index of each term:

1: 1
2: 1
3: 2
4: 3
5: 5
Enter fullscreen mode Exit fullscreen mode

Either style is fine for the purposes of this challenge. That said, if you follow the second convention, it'll be much easier to transition into the repo!

The Solution

As always, I'll kick off the fun with a solution in Haskell brought to you by a couple of our contributors (Parker Johansen and Panagiotis Georgiadis):

module Main where

import System.Environment
import Text.Read

fibonacci :: Int -> [Integer]
fibonacci = flip (take) fibs

fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

headMaybe :: [a] -> Maybe a
headMaybe []     = Nothing
headMaybe (x:xs) = Just x

-- Takes a list of values and returns a list of strings in the format "ONE_BASED_INDEX: VALUE"
printWithIndex :: (Show a) => [a] -> [[Char]]
printWithIndex = zipWith (\i x -> (show i) ++ ": " ++ (show x)) [1..]


-- Prints out the first N numbers from the fibonacci sequence
-- where N equals to the first command line argument.
main :: IO ()
main = do
  args <- getArgs
  let n = headMaybe args
  case n >>= readMaybe of
    Nothing -> putStrLn "Usage: please input the count of fibonacci numbers to output"
    Just n  -> mapM_ (putStrLn) $ (printWithIndex . fibonacci) n
Enter fullscreen mode Exit fullscreen mode

For those of you that maybe haven't seen functional programming before, this solution probably looks pretty wild. That said, I think Haskell is far more readable than anything Lisp-based, so you can probably get the gist of how this works.

Unfortunately, we don't currently have this solution documented in our collection, so maybe one of you can help out. We'd appreciate the support!

Top comments (13)

Collapse
 
jbristow profile image
Jon Bristow • • 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 F4767 with the given precision.

Collapse
 
renegadecoder94 profile image
Jeremy Grifski •

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

Collapse
 
pinotattari profile image
Riccardo Bernardini • • 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*(phin +1/phin ) (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/phin goes rapidly to zero and you get a wonderful approximation with only phin already for small n.

Collapse
 
jbristow profile image
Jon Bristow • • 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 Fn, you need to find Fn-1 + Fn-2. To find those two numbers, you need to find Fn-2 + 2*Fn-3+Fn-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.

Thread Thread
 
renegadecoder94 profile image
Jeremy Grifski • • 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

Collapse
 
geosoft1 profile image
George Calianu • • 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)
}
Collapse
 
pinotattari profile image
Riccardo Bernardini •

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;
Collapse
 
_magedsaeed_ profile image
MagedSaeed • • 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.

Collapse
 
avalander profile image
Avalander •

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))
Collapse
 
keptoman profile image
mlaj • • Edited

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

Collapse
 
jbristow profile image
Jon Bristow •

Also related, Project Euler problem #2

Collapse
 
burdier profile image
Burdier • • Edited

haskell 

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
Collapse
 
juanfrank77 profile image
Juan F Gonzalez •

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

View full discussion (13 comments)

Read next

clericcoder profile image

Mastering Trace Analysis with Span Links using openTelemetry and Signoz (A Practical Guide,Part 2)

Abdulsalaam Noibi -

usman_awan_003 profile image

Optimizing React Performance with Concurrent Mode and Key APIs

Usman Awan -

clericcoder profile image

Mastering Trace Analysis with Span Links using OpenTelemetry and Signoz (A Practical Guide, Part 1)

Abdulsalaam Noibi -

osmarmontesinos profile image

How to win a hackaton (spoiler: Power of Friendship)

Osmar Montesinos 🇦🇶 -