Add fibonacci example

[ghost]

Here http://cboard.cprogramming.com/c-programming/67989-highest-fibonacci-number-ever-calculated.html it says:

the first five digits of the 100000th Fibonacci number, which is 20899 digits long: 25974

So wc reports 20900 characters and it starts with 25974 so I guess its correct. It would be nice to have this example to demonstrate the capabilities of this library. Also I would like to know how or why it took less than 7s to compute.

[def-]

This fails with nim c fib && ./fib:

Traceback (most recent call last)
x.nim(3)                 x
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
(1874 calls omitted) ...
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(12)                fib
x.nim(9)                 fib
tables.nim(339)          hasKey
tables.nim(236)          hasKey
tableimpl.nim(43)        rawGet
hashes.nim               hash
Stack overflow

I guess it's not such a great idea to recurse that deeply.

[def-]

I would do it like this:

import bigints

proc fib(x: Natural): BigInt =
  var
    a = 0.initBigInt
    b = 1.initBigInt
  for i in 2 .. x:
    let tmp = a + b
    a = b
    b = tmp
  return b

echo fib(100000)

Note that this is still much slower than even Python's bigints:

def fib(x):
  a = 0
  b = 1
  for i in range(0, x):
    tmp = a + b
    a = b
    b = tmp
  return a

print(fib(100000))

If you want high performance bigints in Nim use GMP.