DEV Community

Cover image for Let's Get Clever #1: Fibonacci Sequence

Let's Get Clever #1: Fibonacci Sequence

Jason C. McDonald on August 13, 2019

We spend a lot of time trying to write good code. I don't know about you, but I get weary of hearing the (apt) admonishment "don't be clever". Eve...
Collapse
 
smammar profile image
SMAmmar • Edited
#include <stdio.h>
int fib(int number)
{
if (number <= 1)
return number;
return fib(number-1) + fib(number-2);
}

int main ()
{
int number;
scanf("%d", &number);
printf("%d", fib(number));

return 0;
}

How is it , took help geek from geeks ,though

Collapse
 
codemouse92 profile image
Jason C. McDonald • Edited

Don't forget to wrap your code in triple backquotes (`) above and below! That sets it out from the rest of your post, like I have in my comment. You can also force syntax highlighting by naming the language after the first three backticks.

Collapse
 
smammar profile image
SMAmmar

thank you ,sir for guiding.Actually I am new to this forum

Thread Thread
 
codemouse92 profile image
Jason C. McDonald • Edited

Ah, then welcome!

Take a look at our Editor Guide for more about the neat things you can do in posts and comments.

Also, be sure to drop in on the Welcome Thread

Thread Thread
 
smammar profile image
SMAmmar

was my code alright ?

Thread Thread
 
codemouse92 profile image
Jason C. McDonald

Ah yeah, mate. Sweet and simple!

Thread Thread
 
smammar profile image
SMAmmar

wew, though I have left this type programming and switched onto web dev , but still like to solve these odd problems.

Thread Thread
 
codemouse92 profile image
Jason C. McDonald • Edited

Well, how would you solve it with web dev technologies? (repl.it is awesome if you need a sandbox for any language). I bet you'd have some clever solution with, say, Javascript!

Thread Thread
 
smammar profile image
SMAmmar

sir it's like that, i have studied these logics in my programming courses at my university.So just got the idea from there.As for sandboxes I am up for it anyday.Plus, I am a begginer at JS still revising my basics and getting onto the advanced version and then onto the Angular framework

Collapse
 
codemouse92 profile image
Jason C. McDonald • Edited

Waaaaaaaaaait....I just took a closer look at your code.

It works great.

...and....HOW? I mean, it's staring me in the face, I can feel how it's working. I can even see it. But it just...doesn't look like it should?

Woah.

(Definitely edit and wrap it in backticks [and fix the #include]. It deserves to be displayed in all its brilliance.)

Collapse
 
smammar profile image
SMAmmar

done :)

Thread Thread
 
codemouse92 profile image
Jason C. McDonald

Oh...close, but, yeah, not quite. Try this.

Thread Thread
 
smammar profile image
SMAmmar

thank you for the guidance.

Collapse
 
_bigblind profile image
Frederik 👨‍💻➡️🌐 Creemers • Edited

Python solution that uses the fact that the ratio of consecutive numbers in the sequence approaches Phi

def fib(n):
    if n < 3:
        return 1
    return int(round(1.618 * fib(n-1)))
Enter fullscreen mode Exit fullscreen mode
Collapse
 
mortoray profile image
edA‑qa mort‑ora‑y

This is closely related to my closed form solution, as they are both based on Binet's Formula

Using a hard-coded value, mine can be reduced as well:

import math

sq5 = math.sqrt(5.0)
φ = (1.0 + sq5)/2.0
ψ = -1/φ

def fib_x( n ):
    return  int( (φ ** n - ψ ** n) / sq5 )

for i in range(20):
    print(fib_x(i))

Where φ is the Phi value you are using.

Collapse
 
kamalhm profile image
Kamal

Wow, so we can actually get O(1) with this? Amazing

Thread Thread
 
radu1999 profile image
Chivereanu Radu

It s not actually O(1) since ** n takes time too :))

Collapse
 
kamalhm profile image
Kamal

I tried running the code but when I tried to run fib(10) it returns 1, did i do something wrong?

Collapse
 
_bigblind profile image
Frederik 👨‍💻➡️🌐 Creemers

Nope, I made a stupid mistake when writing this function on Dev.to, I originally wrote it in the REPL. Fixing it now.

Collapse
 
grumpytechdude profile image
Alex Sinclair

Excellent stuff!

Collapse
 
codemouse92 profile image
Jason C. McDonald

This one is absolutely beautiful.

Collapse
 
chsanch profile image
Christian Sánchez • Edited

In Perl 6 you can do something like this:

my @fib = 0, 1, * + * ... *

This make uses of the ... sequence operator, which will produce (possibly lazy) generic sequences on demand.

Then you can get the first 10 Fibonacci numbers:

@fib[0..10]

More detailed explanation about this (not mine) could be found at: perl6.online/2018/12/15/playing-wi... and perl6advent.wordpress.com/2010/12/...

Collapse
 
codemouse92 profile image
Jason C. McDonald • Edited

If you could get this to return a single number for value n, you'd be set up to get the bonus points for no loops or recursion! 🔂

Collapse
 
jasman7799 profile image
Jarod Smith • Edited
// better space complexity
function fancyFib(n) {
  const computed = [0,1];
  if(n <= 1) return computed[n];
  for(i = 2; i <= n; i++)
    computed[i%2] = computed[0] + computed[1];
  return computed[n%2];
}

// maintains fidelity
function fibdelity(n) {
  const computed = [0,1];
  for(i = 2; i <= n; i++)
    computed.push(computed[i-1] + computed[i-2]);
  console.log(computed);
  return computed[n];
}

Here is the DP solution in javascript.
O(n) runtime complexity
O(1) space complexity

some loss in the fidelity of the computation since computations used to build upto fib(n) are lost.

maintaining fidelity would probably be better in practical use since saving the pre-computed values would lead to O(1) complexity for values already computed.

In compiled languages you could do this step in compile time and then cache them for O(1) runtime, but you would sacrifice some space O(n) space complexity

Collapse
 
jasman7799 profile image
Jarod Smith

for some reason I started on a mission to calculate fib of 1 million, so I edited the above code to include an execution time, and use big ints from javascript this let me calculate fib(1,000,000) in 88s

function bigFib(n)
{
  let start = process.hrtime();
  const computed = [0n,1n];
  for(i = 2; i <= n; i++) computed[i%2] = (computed[0] + computed[1]);
  hrend = process.hrtime(start);
  console.info('Execution time: %ds %dms', hrend[0], hrend[1] / 1e6);
  return computed[n%2];
}
Collapse
 
codemouse92 profile image
Jason C. McDonald • Edited

+1 for one-upping yourself, mate! ;)

I wonder how long n=(2^63)−1 would take. It may not even be achievable. My own code won't even manage it.

...I should tweak the spec to limit it to (2^16)-1 ;)

Thread Thread
 
jasman7799 profile image
Jarod Smith

given 1e6 is 88s, and 2e63/1e6 = 9.223e12, I would guess 8.116e14 seconds or 25,737,466.3636 years

Thread Thread
 
codemouse92 profile image
Jason C. McDonald

So, not long at all. ;)

Thread Thread
 
jasman7799 profile image
Jarod Smith • Edited

though JavaScript's Big Int library should allow for a number as big as your memory can hold. I think 4GB = 16gb = 16e+9 bits or digits, so theoretically if I could get absolute precision working with the closed form solution mentioned by edA‑qa mort‑ora‑y. Then the largest theoretical number I can handle would be 9.99999...e+16,000,000,000.

Collapse
 
oinak profile image
Oinak

Ruby hashes (a.k.a dictionaries) accept a block to calculate missing entries.

You can abuse this mechanism and store only 0 and 1, and then use the default_proc for everything else:

fib = Hash.new do |hash, key|
  hash[key] = hash[key - 1] + hash[key - 2]
end.merge({ 0 => 0, 1 => 1})

(0..10).each do |n|
  puts fib[n]
end
# 0
# 1
# 1
# 2
# 3
# 5
# 8
# 13
# 21
# 34
# 55
# => 1..10
Collapse
 
codemouse92 profile image
Jason C. McDonald

I couldn't resist one more pass, using C.

int fib(n) {
    int p[2] = {0,1};
    int* r = &(p[n%2]);
    g: p[(n--)%2] = p[0]+p[1];
    if (n) {goto g;}
    return *r;
}

I'm using a pair to calculate the sequence, ergo the 2-element integer array.

Before I can do anything, though, I need to know where my answer will show up, so I create a pointer to the element which will eventually hold the result. That way, I can mutate n without fear. How this works will become apparent in a second.

This next line has a label, g, which I'll be using in a moment. In this math, I'm alternating which of the two elements in the pair are used to store the sum, and I'm switching between them by checking if n is even or odd (n%2), yielding either 1 (odd) or 0 (even). In the middle of that, I'm also decrementing n after I've used its value. I take the sum of the two elements, and save it in the target position in the pair. This way, I always have the latest two elements.

On the next line, if n has a non-zero value, I jump back to that previous line, using its g label. I'm using a goto statement, instead of an explicit loop or recursion (so, technically I hit one of the bonus goals? Debatable.)

Once I'm done, and n has reached zero, I return whatever was in the position I originally stored to look for the answer in. Remember how I was using the modulo to alternate spots? That same logic is at work here. If the original n was even, then the last value will get written to the first spot in the pair; if the original n is odd, then the second spot will be used.

Collapse
 
loki profile image
Loki Le DEV

Nice compact answer, goto still counts as a loop though ;)

Collapse
 
grumpytechdude profile image
Alex Sinclair • Edited
const fib = (num) => {
  if (num == 0) return 0
  let x = 'I', y = ''
  for (let i = 0; i < num; i++) {
    if (i % 2 == 0)
      x += y
    else
      y += x

    return Math.max(x.length, y.length);
  }
}

Golly that was hard to do on mobile!
No need for maths or recursion here, let's use base 0 with a loop!

Collapse
 
codemouse92 profile image
Jason C. McDonald

Which language is this? I suspect Java, but I'm not sure at a glance.

This reminds me a bit of my alternating pair approach (in C), but it's strangely lovely. Nice work.

P.S. Did you mean for y += X to have an upper case X?

Collapse
 
grumpytechdude profile image
Alex Sinclair

Thank you! It's JavaScript, easiest thing for me on my phone. And I did not, thank you! I'll change it now.

I figure it could probably be made much fancier, but I'm not up for it right now!

Thread Thread
 
codemouse92 profile image
Jason C. McDonald

Shoot, bonus points for typing it on mobile at all, mate. ;-)

Collapse
 
mortoray profile image
edA‑qa mort‑ora‑y • Edited

I'm going for the bonus points, no explicit loops nor recursion, and O(1) time*.

import math

sq5 = math.sqrt(5.0)
def fib( n ):
    a = ((1.0 + sq5)/2) ** n
    b = ((1.0 - sq5)/2 ) ** n
    return  int( (a - b) / sq5 )

for i in range(20):
    print(fib(i))

This is a closed form evaluation of the n-th fibonnaci number.

The int cast is because the double isn't precise enough, thus a bit of error value accumulates. Remove it to see how much.

** Time complexity, you might get picky here and we can debate what the time complexity of **n is. In worst case it shouldn't be more than log(n) given that the generic pow is log(n).

Collapse
 
codemouse92 profile image
Jason C. McDonald • Edited

HA! I was getting worried that the efficiency bonus goal was actually impossible, but I just had that nagging feeling there was some algorithmic way of solving this without generating each preceding element.

Fan-TAS-tic

Collapse
 
mortoray profile image
edA‑qa mort‑ora‑y • Edited

Everything is more fun with unicode:

import math

sq5 = math.sqrt(5.0)
φ = (1.0 + sq5)/2.0
ψ = -1/φ

def fib_x( n ):
    return  int( (φ ** n - ψ ** n) / sq5 )

for i in range(20):
    print(fib_x(i))

Collapse
 
jasman7799 profile image
Jarod Smith

Interesting in javascript this will have precision errors after fib(75).
Probably because of the limitations on floating point math precision.

Collapse
 
s_anastasov profile image
Stojan Anastasov

Using Kotlin:

fun fib(n: Int): Int = generateSequence(Pair(1, 1)) {
    Pair(it.second, it.first + it.second)
}.elementAt(n).first

Generate a Sequence (infinite stream of data) starting with 1, 1. Each next element is the second number of the pair + their sum. Use elementAt to get the n-th pair. The result is the first number of the pair.

Try it out online: pl.kotl.in/MOeDSCD4v

Collapse
 
mattonem profile image
maxmattone

Lisp version (using emacs)

(cl-defun fibonacci(n)
  (cond
   ((<= n 1) n)
   (t (+ (fibonacci (- n 1))
     (fibonacci (- n 2)))
      )
   )
  )

Collapse
 
ynndvn profile image
La blatte • Edited

How about some ugly oneliner in JS?

f=(n)=>[0,1].concat([...n>1?Array(n-1):'']).map((v,i,a)=>a[i]=i>1?a[i-1]+a[i-2]:v)[n];

It works like that:

  • First, build a prefilled array. [0,1].concat([...Array(n-1)]) will build the following array with n=4: [0, 1, undefined, undefined, undefined]
  • Loop (sorry) through this array and either use the prefilled value (if i<=1), or add up the two last values (a[i-1] + a[i-2])
  • Finally, return the correct value from the array (at nth index)

A few guards had to be added to handle n=0 and n=1 input:

  • Do not add any Array on the concat step ([0, 1].concat([...'']) will return [0, 1])
  • Do not return the last value of the array (.pop()), but the one stored on the nth index
Collapse
 
codemouse92 profile image
Jason C. McDonald • Edited

Here's my own first pass. I love one-liners. (Python 3)

def fib_elem(n, p=(0,1)):
    return fib_elem(n-1, (p[1], sum(p))) if n else p[0]

Unpacking that, the logic is basically:

def fib_elem(n, p=(0,1)):
    if n:
        return fib_elem(n-1, (p[1], sum(p)))
    else:
        return p[0]

My solution is recursive. I start with a pair of numbers (0,1). On each recursive call, I'm generating a new pair such that the old second value is the new first value, and the new second value is the sum of the old pair. On each recursive call, I also pass an n value that is one less.

If n is zero, the conditional statement would fail, and I'd return the first value in the pair instead of doing the next calculation.

I'm aware that this approach would actually generate one more pair than necessary, however, it also allows it to be correct for n=0.

Collapse
 
curtisfenner profile image
Curtis Fenner

Here's Lua, using the matrix-squaring approach.

Specifically, the transition a', b' := b, a+b can be written as a matrix [[a'][b']] = [[0, 1][1, 1]] * [[a][b]]. Then we can use the fact that applying this n times to get the nth Fibonacci number is the same thing as multiplying the initial state of [[1]][[0]] by the nth power of the matrix [[0,1][1,1]].

Computing the nth power of an object can be done faster than merely multiplying n times. Instead, to compute a^n, we can compute (a^(n/2))^2, which halves the number of multiplications we need to do.

local function matmul(a, b, c, d, x, y, z, w)
    return a*x+b*z, a*y+b*w, c*x+d*z, c*y+d*w
end

local function matsq(a, b, c, d)
    return matmul(a, b, c, d, a, b, c, d)
end

local function fib(n)
    local a, b, c, d = 1, 0, 1, 0
    local x, y, z, w = 0, 1, 1, 1
    while n > 0 do
        if n % 2 == 1 then
            a, b, c, d = matmul(x, y, z, w, a, b, c, d)
        end
        n = n // 2
        x, y, z, w = matsq(x, y, z, w)
    end
    return a
end

print(fib(16)) --> 987

If you want really, really big Fibonacci numbers, this algorithm will be much better than the simple for loop approach, because it requires only logarithmically many arithmetic operations instead of linearly many. For very large values, it's also better than the closed-form solution since you don't have to worry about getting arbitrary precision square roots and exponents. The actual time complexity isn't logarithmic, since arithmetic operations themselves are linear in the number of digits of the values; the overall execution time is thus linear in n since the Fibonacci sequence grows exponentially.

 
chsanch profile image
Christian Sánchez

Yes, Perl 6 is a really interesting language, this a very informative review:
evanmiller.org/a-review-of-perl-6....

And if someone is interested on learn the basics here is a good introduction:
perl6intro.com

Collapse
 
codemouse92 profile image
Jason C. McDonald • Edited

<pedantics>Yes, although perhaps not an explicit one? (I did say that in the goal.)</pedantics>

All the same, I agree it doesn't count. The effect is the same: a conditional jump statement.

Collapse
 
loki profile image
Loki Le DEV

This is a classic interview question!

In c++ you can make a constexpr version that will be computed at compile time!

youtube.com/watch?v=hErD6WGqPlA

 
codemouse92 profile image
Jason C. McDonald

Heh. Yay C hackery!

Collapse
 
jamespotz profile image
James Robert Rooke

My Ruby submission

 
codemouse92 profile image
Jason C. McDonald

Ah, heh. Well, that's what comes of my not knowing Perl (yet).

Collapse
 
wakwe profile image
Olisa Wakwe • Edited

This is my submission, in java.

I have gone ahead to call the function with n as 10