A sequence described by LeonardoFibonacci, defined as f(1)=f(2)=1, f(n)=f(n-1)+f(n-2) for n>2. The first few terms are: 1 1 2 3 5 8 13 21 34 55 89 144 233 377 For more on the sequence's properties, see http://mathworld.wolfram.com/FibonacciNumber.html. The Fibonacci sequence is attributed originally to Indian mathematics. A number of credible sources support this assertion, including Wikipedia. See http://en.wikipedia.org/wiki/Fibonacci_sequence. ---- The Fibonacci numbers form a classic example for recursion: In Scheme: (define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2)))))) In C: int fib(int n) { if (n == 0) return 0; else if (n == 1) return 1; else return fib(n-1) + fib(n-2); } But while elegant, this code is extremely inefficient (exponential)! The following iterative version runs in linear time: In Scheme: (define (fib2 n) (let loop ((m 0) (k 1) (count n)) (if (= count 0) m (loop k (+ m k) (- count 1))))) In C: int fib2(int n) { int m = 1; int k = 0; int i; for (i = 1; i <= n; i++) { int tmp = m + k; m = k; k = tmp; } return m; } ForthLanguage: : fib 0 1 rot 0 ?do over + swap loop drop ; This can be improved further to an algorithm that runs in logarithmic time, that is, provided we're assuming that arithmetic operations take constant time. (Which is true only if your numbers are bounded or you want only limited precision.) Generating the ''n''th Fibonacci number requires you to generate on the order of n bits. There can't possibly be a way to do that in less than linear time. ''True. Scheme code for the logarithmic-in-n sense could look something like this:'' (define (fib3 n) (define (fib-iter a b u v count) (cond ((= count 0) b) ((even? count) (fib-iter a b (+ (square u) (square v)) (+ (square v) (* 2 u v)) (/ count 2))) (else (fib-iter (+ (* b v) (* a v) (* a u)) (+ (* b u) (* a v)) u v (- count 1))))) (fib-iter 1 0 0 1 n)) ''By defining a square-able operator on the coefficient space, this achieves logarithmic-in-n behaviour in exactly the same way that an exponentiation operator could.'' In Haskell the version is more elegant (YMMV): We define a lazy list corresponding to the FibonacciSequence. fibs = 0 : 1 : zipWith (+) fibs (tail fibs) fibs is a list composed of 0, 1 and the sum of items from two lists, fibs itself, and all but the first element of fibs, exactly as the original definition fib n = fibs !! n Here we say that the fibonacci number at n is the nth element of fibs. It's elegant and runs in linear time (modulo laziness issues, but they're implementation specific). -- DanielYokomiso ---- In wild contrast to the terse versions of Fibonacci that are possible in functional languages, I present an implementation in GuidoVanRobot, which does not have the luxury of variables. I assure you, this code actually works, as long as you leave plenty of beepers in the origin of the world: -- SteveHowell define face_north: while not_facing_north: turnleft define face_east: while not_facing_east: turnleft define face_west: while not_facing_west: turnleft define face_south: while not_facing_south: turnleft define move_north: face_north move define move_east: face_east move define move_west: face_west move define move_south: face_south move define go_home: face_south while front_is_clear: move face_west while front_is_clear: move define move_northeast: face_east move face_north move define move_southwest: face_south move face_west move define go_past_end_of_beeper_diagonal: go_home while next_to_a_beeper: move_northeast define go_to_end_of_beeper_diagonal: go_past_end_of_beeper_diagonal move_southwest define makebeeper: go_home pickbeeper go_to_end_of_beeper_diagonal define move_beepers_northeast: while next_to_a_beeper: pickbeeper move_northeast putbeeper move_southwest move_northeast define copy_beepers_northeast: go_to_end_of_beeper_diagonal move_beepers_northeast define double_beeper_at_home: pickbeeper go_home pickbeeper define drop_beeper_west_of_current: go_past_end_of_beeper_diagonal move_north putbeeper move_east define move_beepers_to_3: face_east move move putbeeper define move_beepers_to_4: face_east move move move putbeeper define copy_to_3: copy_beepers_northeast while next_to_a_beeper: double_beeper_at_home move_beepers_to_3 drop_beeper_west_of_current define copy_to_4: copy_beepers_northeast while next_to_a_beeper: double_beeper_at_home move_beepers_to_4 drop_beeper_west_of_current define pick_all_beepers: while next_to_a_beeper: pickbeeper define put_all_beepers: while any_beepers_in_beeper_bag: putbeeper define add_3_4: go_home face_east move move pick_all_beepers move pick_all_beepers define add: go_to_end_of_beeper_diagonal copy_to_3 copy_to_4 add_3_4 go_home go_past_end_of_beeper_diagonal do 2: move_northeast put_all_beepers do 2: move_west pick_all_beepers move_south put_all_beepers makebeeper makebeeper move_northeast putbeeper move_northeast putbeeper while next_to_a_beeper: add ---- Surprisingly enough, there is also a simple non-recursive formula for the nth Fibonacci number (the ^ operator is exponentiation): fib(n) = (Phi^n - (-phi)^n) / sqrt(5). where the GoldenRatio''''''s Phi and phi are defined as Phi = (1 + sqrt(5)) / 2. -phi = (1 - sqrt(5)) / 2. It is a simple proof by induction to show that this correctly gives the nth Fibonacci number. If calculating x^n runs in linear time for fixed x, this algorithm takes only linear time. ''Actually, it takes fewer than 2*lg n multiplications. See IntegerPowerAlgorithm. -- EricJablow'' Since the number called "-phi" above is less than 1 in absolute value, it's easy to prove that fib(n) is the nearest integer to Phi^n/sqrt(5). ---- MemoIzation can make the recursive algorithm work in linear time. To do it in logarithmic time, reduce this to a matrix exponentiation problem: /0 1\ /F_{n-1} F_n \ /F_n F_{n+1} | | | | = | | \1 1/ \F_n F_{n+1}/ \F_{n+1} F_{n+2}/ Here, F_{-1} = 1. Given that definition, n /0 1\ /F_{n-1} F_n | | = | | \1 1/ \F_n F_{n+1}/ and standard exponentiation techniques make this run in O(log n) arithmetic operations. Since F_n has O(n) binary digits, and you need to store only constantly many intermediate values, and since the bit-complexity of multiplication of n-bit numbers is n log n (the divide and conquer algorithms), you end up with O(log n) arithmetic operations, O(n) space, and O(n (log n)^2) bit-complexity. Incidentally, don't be so sure that you need to compute n bits of a number to get the nth bit; there's an infinite series for pi where the denominators are powers of 16 and the numerators are sufficiently bounded that you can find the nth bit of the binary expansion of pi in O(log n) time. The GeneratingFunction of the FibonacciNumbers is: \sum_{n=0}^{\infty} F_n x^n = \frac{x}{1 - x - x^2}. On the other hand, the GoldenRatio method is fairly useless for precise computational work, because errors propagate. Suppose the computed version of F_{100} is off by 1. Then the computed version of F_{200} will be off by about F_{100}. Sorry about the quasi-TeX notation. -- EricJablow ---- All these algorithms are of course fun to write create and think of but .... On the other hand, as very few uses of Fibonacci numbers require infinite precision arithmetic, it is often possible to remember all possible answers to all the possible questions and just use a look up table - constant time. ---- By sublime coincidence, the GoldenRatio is very close to the ratio of km to miles for n = 3 to 11, and not far out after that.... Fib(n)Miles = Fib(n+1)Kilometers Not quite as applicable as double-and-add-thirty for C->F though. * I may have missed something here. I always thought it was F = 9/5C + 32? Or is it that we're trying to say that F = 2C + 30 is a useful rough approximation? ** Well, let's try that ... | (x2+30) (9/5+32) | C F F Err | 0 30 32 -2 | 1 32 33.8 -1.8 | 2 34 35.6 -1.6 | 3 36 37.4 -1.4 | 5 40 41 -1 | 10 50 50 0 | 15 60 59 1 | 20 70 68 2 | 30 90 86 4 | 38 106 100.4 5.6 | 40 110 104 6 Hmmm. A little sloppy, but not unusable. Faster in the head. ---- Implementing a generator for the FibonacciSequence introduced as a TestDrivenDevelopment exercise by CharliePoole: http://groups.yahoo.com/group/testdrivendevelopment/message/295 ---- Here's an implementation of the FibonacciSequence I coded up in Python based on a new-ish algorithm I read in a journal article: http://pythonista.wordpress.com/2008/07/03/pure-python-fibonacci-numbers/ --PaulMiller ---- CategoryMath