# Fibonacci, Factorial, Triangle Numbers

Nth Fibonacci Number (inefficient*):

Factorial (doesn't support negative numbers):

Nth Triangle Number (doesn't support negative numbers):

*fib(100) would have to calculate fib(99) and fib(98), then fib(98), fib(97), fib(97), and fib(96); this requires calculating many fibonacci numbers multiple times.

Your factorial function isn't quite right; 0! = 1, not 0. (To see this, start with, say, 3!, and do
2! = 3! / 3
1! = 2! / 2
0! = 1! / 1
)

The name for that last thing is "triangle number."

You say that your Fibonacci Number generator is inefficient, because it has to calculate all previous Fibonacci Numbers, just like a person would. There is actually a formula, called Binet's Formula, that gives you the nth Fibonacci Number without calculating the previous ones. The even cooler thing about that formula is that you can plug in non-integers and get very interesting results (What's the 1.5th Fibonacci number?).

No, it's worse than that; it takes exponential time,because it does a lot of redundant computation. With memoization you can get it down to linear time. Still not as good as constant time, if that's what your formula takes. :~)

If you were to put axis on that graph, you would see that the line crosses the x-axis, where the imaginary part is 0, at what we call 'Fibonacci Numbers'.
For example, Snap! Build Your Own Blocks

i saw that project before

Yeah. I was eventually going to get around to using memoizing, but I haven't had time.