Funny because I am a CS 101 student and I did in fact write a recursive function without the help of outside resources for one of the functions needed in a project.

@Michael Depending on the teacher taking the CS101. I am pretty much sure every one in my batch would have written a recursive function over an iterative solution

@Saurabh, Michael Recursive function for Fibonacci will be very inefficient. Its running time will grow exponentially with X. :) Watch this video : http://www.youtube.com/watch?v=GM9sA5PtznY

I hope someone noticedthe point of this post and which in my view is that the more you know things, the more constrained your view becomes, instead of thinking in a straightforward manner, we think of all the ways something could go wrong and more often than not, it holds us back from doing anything.

This is sooo true and really funny.. i have been there and done that for all the different roles [Excpet the cat ofcourse ;)] .... code written at a large comany is the best.. ROFL!

The Math PhD's closed-form answer is less efficient than the basic iterative/recursive solution. It requres 2n (or for the rounding version, n) multiplications to do the exponentiation, while the brute-force solution requires n additions, which on most processors are faster than multiplications.

so no one gives a sh!t about the computational complexity. All the recursive implementations have exponential complexity. And I seriously have no clue what the author tried to prove with the totally gibberish large company or math PhD code.

How about the following: int fibonacci(int x){ if (x <= 2) return 1; else { int sum = 1, oldsum = 1, tmpsum; for (int a = 3; a <= x; a++) { tmpsum = sum; sum = sum + oldsum; oldsum = tmpsum; } return sum; } }

When I took my bachelor degree, I used "cat" species code for my homework. The code worked, but guess what? Got 0 because my teacher didn't understand any sh*t I wrote :))

Replace all of the method and variable names with variations on 'asdfjkl' and change the comments to '//does stuff' and '//does the rest of stuff' and that's basically what everything I code looks like.

Here we go, complete imagination of author went to a toss. And post has become dead ground for recursive algo complexity discussion. Screw you coding wannabes.

I suppose `one()` may return an object with various methods, e.g. `.sign()`, `.magnitude()`, `.negative()` and `.reciprocal()`. This list may be expanded in the future. Not so with the language builtin `1`.

And code written by a student, that paid attention during algoritms, knows how to google and did remember to trust only reliable sources of information...

Just to be pedantic for my CS/math bros: The CS101 code doesn't need recursion or memoization, and that would occur to most students, since that's how people do it by hand: they take the last two numbers, add them together, and get a new number. Then they can forget the oldest number. A simple for loop takes care of that. Admittedly, this is explicit memoization.

But worse, the code by a "math phd" isn't any faster than that, and is inexact if there is rounding error, unless it uses an overcomplicated math framework that handles sqrts symbolically.

Still, if you change the (math phd?) exponentiation function to do successive squaring, you get the best running time so far, O(log n). A CS101 student could even work out how to do it without a heavyweight math library, since all of the intermediate computations are on numbers of the form (a+b*sqrt(5))/2^n where a,b, and n are integers. So you only need integer arithmetic.

There other O(log n) algorithms, such as ones exploiting the recurrences F_(2n-1) = (F_n)^2 + (F_(n-2))^2 and F_(2n) = (2F_(n-1) + F_n)F_n

My most beloved school of coding is so called 'Weimar school'. It used by Germans for writing embedded code, mainly safety critical code. It goes something like this:

#define ONE 0U #define TWO 1U #define E_OK 0U #define THRE 16U #define HUNDRED 100U uint8_t UDS_tx_buff_au8[HUNDRED + ONE]

arguing that: (a) tail recursion would take care of recursion costs, and (b) why bother with control flow if we only need the values.

Reminds me of Perlis' quip: C programmers know the cost of everything and value of nothing, while Lisp programmers know the value of everything but the cost of nothing. :-)

Code written by CS 101 student has too much indentation and looks too clean. In reality, the code would be flush against the left margin, no indents, no whitespace between operators/operands, and would probably have redundant comments on every other line (to please the prof), e.g. "//This is for the case x = 1 //This is for the case x == 2"

Code written by a type theorist. (It calculates Fibonacci numbers in the Haskell type system.)

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies, FlexibleInstances, UndecidableInstances #-} data Zero data Succ n class Add a b c | a b -> c instance Add Zero b b instance Add a b c => Add (Succ a) b (Succ c) class Fibb a b | a -> b instance Fibb Zero Zero instance Fibb (Succ Zero) (Succ Zero) instance (Fibb a r1, Fibb (Succ a) r2, Add r1 r2 b) => Fibb (Succ (Succ a)) b

To calculate, you need to create placeholder values with appropriate types, and ask the interpreter what type the combination of the two would have.

*Main> let fibb = undefined :: (Fibb a b) => a -> b *Main> let six = undefined :: Succ (Succ (Succ (Succ (Succ (Succ Zero))))) *Main> :t fibb six fibb six :: Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))

The real Math Ph.D. wouldn't use `one()` or `add(one(), one(), one(), one(), one())` when there is already a `zero()` defined. Rather he would write it using induction, like `succ(zero())`, or `succ(succ(succ(succ(succ(zero())))))`. Hope that helps ;)

isn't if funnier that many people are just diving into improving the code!!! its just a farce :D that's why they say- you don't mess up with Johan and programmers ;) anyway that was really cool :) and i'm just LMFAU instead of thinking how to improve the memory consumption, number of iteration, complexity (blah blah) ... :D

A CS 101 student would never write a recursive function.

ReplyDeleteFunny because I am a CS 101 student and I did in fact write a recursive function without the help of outside resources for one of the functions needed in a project.

DeleteThis comment has been removed by the author.

Delete@Michael Depending on the teacher taking the CS101. I am pretty much sure every one in my batch would have written a recursive function over an iterative solution

ReplyDeleteThis comment has been removed by the author.

ReplyDelete@Saurabh, Michael

ReplyDeleteRecursive function for Fibonacci will be very inefficient. Its running time will grow exponentially with X. :) Watch this video : http://www.youtube.com/watch?v=GM9sA5PtznY

I hope someone noticedthe point of this post and which in my view is that the more you know things, the more constrained your view becomes, instead of thinking in a straightforward manner, we think of all the ways something could go wrong and more often than not, it holds us back from doing anything.

ReplyDelete@Animesh

ReplyDeleteRecursion is not used without memoization. With it, it's a linear algorithm.

Math guy's program will go in an infinite loop if b is a non integer number :/

ReplyDeleteThis is sooo true and really funny.. i have been there and done that for all the different roles [Excpet the cat ofcourse ;)] .... code written at a large comany is the best.. ROFL!

ReplyDeletewhy u guys senti by looking at this ?

ReplyDeletethis if for fun only :) :)

The Math PhD's closed-form answer is less efficient than the basic iterative/recursive solution. It requres 2n (or for the rounding version, n) multiplications to do the exponentiation, while the brute-force solution requires n additions, which on most processors are faster than multiplications.

ReplyDeleteLOL ! Funny ! I laughed so much when I saw the "Code Written At a Large Company" part ! LOL

ReplyDeleteMy version of fibonacci number:

ReplyDeleteint fibonacci(int n)

{

return rand();

}

so no one gives a sh!t about the computational complexity. All the recursive implementations have exponential complexity. And I seriously have no clue what the author tried to prove with the totally gibberish large company or math PhD code.

ReplyDeleteHow about the following:

int fibonacci(int x){

if (x <= 2)

return 1;

else {

int sum = 1, oldsum = 1, tmpsum;

for (int a = 3; a <= x; a++) {

tmpsum = sum;

sum = sum + oldsum;

oldsum = tmpsum;

}

return sum;

}

}

It has linear complexity.

A database specialist would write

ReplyDeleteSELECT Value FROM dbo.Fibonacci WHERE n = @n;

I would be surprised if a large company has a fibonacci method that runs on O(2^n) time.

ReplyDeleteThis comment has been removed by the author.

ReplyDelete@Unknown -- hahaha my thoughts exactly upon reading this. Just look it up!

ReplyDeletefunny comic

Ey Subhrajit, I´ll buy you a can of humor.

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteI think I should copy cat

ReplyDeleteWhen I took my bachelor degree, I used "cat" species code for my homework. The code worked, but guess what? Got 0 because my teacher didn't understand any sh*t I wrote :))

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteROFL. Had a nice read.

ReplyDeleteNow for the folks who have commented with suggestions on optimizing the algorithm:

Seriously?!! Don't you guys get humour at all? (facepalm)

This comment has been removed by the author.

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteI get the humour, but for those suggesting improvements, here's a simpler one -

ReplyDeletevoid fibonacci(int number_of_terms){

int T1=0, T2=1;

do{

T1 = T1 + T2;

T2 = T1 - T2;

printf("%d\n", T2);

number_of_terms--;

} while(number_of_terms > 0);

}

This is in C btw, and here's a compiled version - http://ideone.com/gs0Duz

the best code is written by your cat.

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteReplace all of the method and variable names with variations on 'asdfjkl' and change the comments to '//does stuff' and '//does the rest of stuff' and that's basically what everything I code looks like.

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteHere we go, complete imagination of author went to a toss. And post has become dead ground for recursive algo complexity discussion. Screw you coding wannabes.

ReplyDeleteToo good post. Don't do CS graffiti here.

This comment has been removed by the author.

ReplyDeleteI love your cat, amazing code :D

ReplyDeleteIt doesn't take a Ph.D. to know the direct formula for the general element in the Fibonacci sequence.

ReplyDeleteI do wonder why the one() instead of numbers.

Hilariously true!!

ReplyDeleteI suppose `one()` may return an object with various methods, e.g. `.sign()`, `.magnitude()`, `.negative()` and `.reciprocal()`. This list may be expanded in the future. Not so with the language builtin `1`.

ReplyDeletei do as

ReplyDeletef(n)=( (1+sqrt(5))^n - (1-sqrt(5))^n ) / (sqrt(5)*2^n)

so what i become ?

There is a solution which runs in O(log(n)) to compute the n'th term. No caching.

ReplyDeleteIt's one() and add() instead of 1 and + because the mathmathic field won't make a difference. So it's way more general!

ReplyDeleteThere's a solution that runs with O(1) posted above.

ReplyDeleteA Pythonista could just do this:

import mpmath

print( fib( n ) )

Had a good laugh :D

ReplyDeleteHaving worked at 5 *very* different companies in 5 years, I can testify that there is a lot of truth to this!

(Except perhaps the one with the cat)

Ah the varied species! Found some more in the comments! :D

ReplyDeleteAnd code written by a student, that paid attention during algoritms, knows how to google and did remember to trust only reliable sources of information...

ReplyDeletehttp://introcs.cs.princeton.edu/java/23recursion/Fibonacci.java.html

is missing the kernel guy code:

ReplyDeleteint fib(int n) {

if (n < 0) {

#ifdef HAVE_ERRNO

errno = EDOM;

#endif

return -1;

}

return n == 0

? 0

: (n == 1

? 1

: (n == 2

? 2

: fib(n - 2) * fib(n-1)

)

);

}

Lol so true, code written at large company does look like that, (why? :()

ReplyDeleteThis comment has been removed by the author.

ReplyDeletePhew! Then who'd write a O(lg(n)) algorithm using matrix exponentiation ? Only me? :P

ReplyDelete[{1 1},{1 0}]^n = [{F_(n+1) F_n},{F_n F_(n-1)}]

Also, x^n = x^(n/2)*x^(n/2)

which has O(lg(n)) ;)

Just to be pedantic for my CS/math bros:

ReplyDeleteThe CS101 code doesn't need recursion or memoization, and that would occur to most students, since that's how people do it by hand: they take the last two numbers, add them together, and get a new number. Then they can forget the oldest number. A simple for loop takes care of that. Admittedly, this is explicit memoization.

But worse, the code by a "math phd" isn't any faster than that, and is inexact if there is rounding error, unless it uses an overcomplicated math framework that handles sqrts symbolically.

Still, if you change the (math phd?) exponentiation function to do successive squaring, you get the best running time so far, O(log n). A CS101 student could even work out how to do it without a heavyweight math library, since all of the intermediate computations are on numbers of the form (a+b*sqrt(5))/2^n where a,b, and n are integers. So you only need integer arithmetic.

There other O(log n) algorithms, such as ones exploiting the recurrences

F_(2n-1) = (F_n)^2 + (F_(n-2))^2

and

F_(2n) = (2F_(n-1) + F_n)F_n

Sincerely,

a math phd candidate

cat style looks like perl code

ReplyDeleteThe Math PhD would use haskell and produce an infinite list of fibonacci results.

ReplyDeleteI think math phd should write that in Lisp.

ReplyDeleteA simple version would be, but you may expand to add other parameter forms.

(defun fib (x) (if (< x 2) x (fib (- x 1) (- x 2))))

My most beloved school of coding is so called 'Weimar school'. It used by Germans for writing embedded code, mainly safety critical code. It goes something like this:

ReplyDelete#define ONE 0U

#define TWO 1U

#define E_OK 0U

#define THRE 16U

#define HUNDRED 100U

uint8_t UDS_tx_buff_au8[HUNDRED + ONE]

uint8_t panic(uint16_t kondition_u16)

{

uint8_t temp_u8;

/* I am evaluating kondition */

if(kondition_u16 > THRE)

{

UDS_tx_buff_au8[ONE] = ONE;

UDS_tx_buff_au8[TWO] = TWO;

temp_u8 = HUNDRED;

}

else

{

UDS_tx_buff_au8[ONE] = ONE;

UDS_tx_buff_au8[TWO] = ONE;

temp_u8 = HUNDRED;

}

return temp_u8;

}

F$ck ya common sense, logical expresions folding and ROM saving.

MISRA and QAC said so. German engineering knows that;D

Hmmm ... a functional programmer writing in C may write:

ReplyDeletereturn ((x == 1) || (x == 2)) ? 1 : (fibonacci (x - 1) + fibonacci (x - 2));

arguing that: (a) tail recursion would take care of recursion costs, and (b) why bother with control flow if we only need the values.

Reminds me of Perlis' quip: C programmers know the cost of everything and value of nothing, while Lisp programmers know the value of everything but the cost of nothing. :-)

Thanks for a fun post.

Has anybody noticed that the smartest code with best practices is actually written by the cat?? Dude your cat is awesome..

ReplyDeleteThat loser CS 101 student did not even handle the infinite loop problem (x<1)..

Soft Kitty, Warm Kitty, little ball of fur, Happy Kitty, Sleepy Kitty, purr purr, purr #respect

A hackathon coder would use this:

ReplyDeleteint getFibonacciNumber(int n) {

int table[] = {-1, 1,1,2,3,5,6,13};

if ((unsigned int)n > 13)

return -1;

return table[n];

}

ReplyDeleteF_n = F_{n-1} + F_{n-2},\!\

F_n = F_{n-1} + F_{n-2},\!\

F_{n-2} = F_n - F_{n-1}

F_{-n} = (-1)^{n+1} F_n

F_{n}=\sum_{k=0}^{\lfloor\frac{n-1}{2}\rfloor} \tbinom {n-k-1} k

Code written by CS 101 student has too much indentation and looks too clean. In reality, the code would be flush against the left margin, no indents, no whitespace between operators/operands, and would probably have redundant comments on every other line (to please the prof), e.g. "//This is for the case x = 1 //This is for the case x == 2"

ReplyDeleteCode as written by a hacker:

ReplyDeletepublic int fib(int n) { return (n > 2) ? fib(n-1)+fib(n-2):0; }

Code as written as a seasoned: developer

import org.apache.commons.math;

public int fib(int n) {

return Math.fibonacci(n);

}

So true, Going through this I had a flashback of all companies i have worked with in the last 15 years.

ReplyDeleteMore you know, the more constrained you are

This comment has been removed by the author.

ReplyDeleteComman, at least there will be unit tests in the code produced at a large company, lol

ReplyDeleteecho "bye";

ReplyDeleteI like PHP.

I am going to write cat code in my company tomorrow :) :P

ReplyDeleteCode written by a type theorist. (It calculates Fibonacci numbers in the Haskell type system.)

ReplyDelete{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies, FlexibleInstances, UndecidableInstances #-}

data Zero

data Succ n

class Add a b c | a b -> c

instance Add Zero b b

instance Add a b c => Add (Succ a) b (Succ c)

class Fibb a b | a -> b

instance Fibb Zero Zero

instance Fibb (Succ Zero) (Succ Zero)

instance (Fibb a r1, Fibb (Succ a) r2, Add r1 r2 b) => Fibb (Succ (Succ a)) b

To calculate, you need to create placeholder values with appropriate types, and ask the interpreter what type the combination of the two would have.

*Main> let fibb = undefined :: (Fibb a b) => a -> b

*Main> let six = undefined :: Succ (Succ (Succ (Succ (Succ (Succ Zero)))))

*Main> :t fibb six

fibb six

:: Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))

thinking ... should get CAT.

ReplyDeleteSorry, couldn't resist... Bad Indian code http://pastie.org/8475451

ReplyDeleteJust a thought: one can compute Fib(n) in O(1). There is a nice closed from for Fib(n) to derived it consider that it satisfies:

ReplyDeleteFib(n+2) - Fib(n+1) - Fib(n) = 0

nice, linear and homogeneous.

The punchline is that

Fib(n) = c0 * b0^n + c1*b1^n

where b0 and b1 solve for

x^2 - x - 1 =0 [Golden ratio!]

and c0 and c1 are so that

co + c1 = Fib(0) = 1

c0*b0 + b1*b1 = Fib(1) = 1

Though, accuracy might be an issue.

And then there's the smart way to do it:

ReplyDeletehttps://gist.github.com/ElectricJack/7441844

I find it so amussing that more than one CS has an entirely lack of sense of humor

ReplyDelete... it's actually depressing.

And this is how it is done in ruby :)

ReplyDeletedef fibonaci(n)

a=[0]

(o..n).map {|x| x<=1? a[x]=x :(a[x] = a[x-1]+a[x-2])}

puts a.inspect

end

end

:D

ReplyDeleteWho gonna write the DP code? :)

return int(0.5+(pow(1.618033988749895, n) / 2.23606797749979));

ReplyDeleteExcellent code by your Cat..

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteThe real Math Ph.D. wouldn't use `one()` or `add(one(), one(), one(), one(), one())` when there is already a `zero()` defined. Rather he would write it using induction, like

ReplyDelete`succ(zero())`, or `succ(succ(succ(succ(succ(zero())))))`. Hope that helps ;)

Hahahahahahaha

ReplyDeleteisn't if funnier that many people are just diving into improving the code!!! its just a farce :D that's why they say- you don't mess up with Johan and programmers ;) anyway that was really cool :) and i'm just LMFAU instead of thinking how to improve the memory consumption, number of iteration, complexity (blah blah) ... :D

ReplyDelete