Hey guys,
Below is a code snippet for the fibonacci sequence with 'memoization', a
technique that stores the results of previous calls to a function so that the
function can return the stored result instead of recalculating the result. This
makes executing the fibonacci sequence much more efficient.
template idx(): untyped =
if n == 0: 0 else: n-1
func fib(n: Natural; memo: var seq[int]): Natural =
if memo[idx] != -1: return memo[idx]
if n == 0 or n == 1: result = 1
else: result = fib(n - 1, memo) + fib(n - 2, memo)
memo[idx] = result
let startTime = epochTime()
var memo = newSeqWith(91, -1)
echo fib(91, memo)
let endTime = epochTime()
echo "elapsed time: " & $(endTime - startTime)
Run
If you run the code snippet it'll work but if you change the `91` to `92`
inside of the `newSeqWith` and `fib` procs, it'll raise an error: `Error:
unhandled exception: over- or underflow [OverflowDefect]`
Why would I get this error and what does this mean?
