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)
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?
I don't think it really has anything to do with your particular implementation. The fiboncci sequence grows very fast, so naturally at some point values won't fit an int in Nim (which is fixed in size to be equal to the size of a pointer, so likely 64-bit for you) has anymore. When
So what are the solutions?