The Fibonacci sequence is a sequence    Fn    of natural numbers defined recursively:

      F0 = 0 
      F1 = 1 
      Fn = Fn-1 + Fn-2, if n>1 



Task

Write a function to generate the    nth    Fibonacci number.

Solutions can be iterative or recursive (though recursive solutions are generally considered too slow and are mostly used as an exercise in recursion).

The sequence is sometimes extended into negative numbers by using a straightforward inverse of the positive definition:

      Fn = Fn+2 - Fn+1, if n<0   

support for negative      n      in the solution is optional.



Related tasks

   Fibonacci n-step number sequences‎
   Leonardo numbers


References

   Wikipedia, Fibonacci number
   Wikipedia, Lucas number
   MathWorld, Fibonacci Number
   Some identities for r-Fibonacci numbers
   OEIS Fibonacci numbers
   OEIS Lucas numbers


10101000000000100000000000000000    0. -21 to c    acc = -n
01101000000001100000000000000000    1. c   to 22   temp = acc
00101000000001010000000000000000    2. Sub. 20     acc -= m
10101000000001100000000000000000    3. c   to 21   n = acc
10101000000000100000000000000000    4. -21 to c    acc = -n
10101000000001100000000000000000    5. c   to 21   n = acc
01101000000000100000000000000000    6. -22 to c    acc = -temp
00101000000001100000000000000000    7. c   to 20   m = acc
11101000000000100000000000000000    8. -23 to c    acc = -count
00011000000001010000000000000000    9. Sub. 24     acc -= -1
00000000000000110000000000000000   10. Test        skip next if acc<0
10011000000000000000000000000000   11. 25  to CI   goto (15 + 1)
11101000000001100000000000000000   12. c   to 23   count = acc
11101000000000100000000000000000   13. -23 to c    acc = -count
11101000000001100000000000000000   14. c   to 23   count = acc
00011000000000000000000000000000   15. 24  to CI   goto (-1 + 1)
10101000000000100000000000000000   16. -21 to c    acc = -n
10101000000001100000000000000000   17. c   to 21   n = acc
10101000000000100000000000000000   18. -21 to c    acc = -n
00000000000001110000000000000000   19. Stop
00000000000000000000000000000000   20. 0           var m = 0
10000000000000000000000000000000   21. 1           var n = 1
00000000000000000000000000000000   22. 0           var temp = 0
10010000000000000000000000000000   23. 9           var count = 9
11111111111111111111111111111111   24. -1          const -1
11110000000000000000000000000000   25. 15          const 15