Spiked Math Games  // Math Fail Blog  // Gauss Facts  // Spiked Math Comics



Fibonacci's 8th Term - August 25, 2009
Rating: 4.1/5 (164 votes cast)
  • Currently 4.1/5
  • 1
  • 2
  • 3
  • 4
  • 5
Spiked Math Comic - Fibonacci Served His Time


home     info     archive     contact     rss

Google+ Page   //   Facebook Page   //   Twitter Page


I once wrote out the Fibonacci sequence to the 98th number.
I was bored...

He need a pair of rabbits to pass the time.

//yeh on that same topic.../
import java.io.*;
class Fibonacci {
public static void main(String[] args) throws IOException {
PrintWriter wF = new PrintWriter(new BufferedWriter(new FileWriter("Fibonacci.txt")));
long[] Fibonacci = new long [94];
int c=0;
wF.println("The Fibonacci Sequence on its first 100 places:");
System.out.println("Fibonacci[0] = 0");
wF.println("Fibonacci[0] = 0");
System.out.println("Fibonacci[1] = 1");
wF.println("Fibonacci[1] = 1");
for(c=2;c Fibonacci[c]=Fibonacci[c-1]+Fibonacci[c-2];
System.out.println("Fibonacci["+c+"] = "+Fibonacci[c]+" which is: "+Fibonacci[c-1]+" + "+Fibonacci[c-2]);
wF.println("Fibonacci["+c+"] = "+Fibonacci[c]+" which is: "+Fibonacci[c-1]+" + "+Fibonacci[c-2]);
}//am i a nerd?/

# reply to the above statement ^ lol no

reply = raw_input("You could do better, ever heard of tail recursion ? reply with yes/no")
If reply.capitalize() == YES : print "yes"
elif reply.capitalize() == NO : print "no"
else : print "can you read?"

recursion for Fibonacci number generation is a very bad idea. using recursion, the time complexity is exponential - o(2^n)
Using iteration, the time complexity is o(n).

Naive recursion fails badly, but naive recursion is not the only recursion. For example:
fib n = fibs !! (n-1) --the nth fibonacci number is the nth entry in the list.
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
is an O(n) recursive implementation of the Fibonacci sequence in Haskell. This particular implementation requires laziness.

Recursion can be used to get a Fibonacci number in O(logn).

By using a recursive function to calculate [1 1;1 0]^n in logarithmic time and multiply it with [1 0] one would obtain [F(n+1);F(n)].

[1 1;1 0]^(n-1)*[1;0]=[F(n);F(n-1)]

I used the matrix representation of matlab.

Use memoization when recursing. Note that without operator overloading, it's gonna look ugly.
It made my recursive Ackermann quite fast. That is, until i had to learn how to play with infinite-size integers :)

Anyways, here's an efficient recursion one:
#include <cstdio>
#include <cstdlib>
#include <map>
using namespace std;

map<unsigned int, unsigned long> memo;
unsigned long fib(unsigned int a) {
if (memo.find(a) != memo.end())
return memo[a];
if (a < 3) {
memo[a] = 1;
return memo[a];
memo[a] = fib(a-1) + fib(a-2);
return memo[a];
int main(int argc, char **argv) {
memo = map<unsigned int, unsigned long>();
printf("%lu", fib(atoi(argv[1])));
return 0;

I don't get the joke :/

Who can explain this joke to me ...

This coding has gotten out of hand...

It's Fibonacci's eighth prison term (his eighth prison sentence)...I don't think that this is a funny joke.

or you guys could just use: ((phi)^(n))/(root5) if n is even, you round down to the largest number if n is odd, round up to next smalled whole number

Leave a comment

Profile pictures are tied to your email address and can be set up at Gravatar. Click here for recent comments.
(Note: You must have javascript enabled to leave comments, otherwise you will get a comment submission error.)
If you make a mistake or the comment doesn't show up properly, email me and I'll gladly fix it :-).


home     info     archive     contact     rss

Google+ Page   //   Facebook Page   //   Twitter Page

Welcome to Spiked Math!

Hello my fellow math geeks. My name is Mike and I am the creator of Spiked Math Comics, a math comic dedicated to humor, educate and entertain the geek in you. Beware though, there might be some math involved :D

New to Spiked Math?
View the top comics.

New Feature: Browse the archives in quick view! Choose from a black, white or grey background.