# Function Problem

Sorry I am new in Julia , This is my Fibonacci numbers function :

``````> global fib_cache = Dict{BigInt, BigInt}(0 => 0, 1 => 1)
> function fib(n::Integer)
> global fib_cache
> fib_cache[n]
> else
> fib_cache[n] = fib(n-1) + fib(n-2)
> end
> end
``````

The following function is a shorter alternative to fib because of its use of
get!. However, it does not work. I don’t know why can someone explain why it dosen’t work ?.

``````global fib_cache = Dict{BigInt, BigInt}(0 => 0, 1 => 1)
function fib(n::Integer)
global fib_cache
get!(fib_cache, BigInt(n), fib(n-1) + fib(n-2))
end
``````

Not sure if this is an exercise or you just want it to work. If the latter, you may want to look at the Memoize package, which I described and demonstrated the usage of in a recent StackOverflow answer:

Regarding your specific problem, you could write it like this:

``````const FIB_CACHE = Dict{BigInt,BigInt}(0 => 0, 1 => 1)

fib(n::Integer) = get!(FIB_CACHE, n) do
fib(n-1) + fib(n-2)
end
``````
``````julia> [fib(k) for k = 1:10]
10-element Array{BigInt,1}:
1
1
2
3
5
8
13
21
34
55

julia> fib(1234)
347746739180370201052517440604335969788684934927843710657352239304121649686845967975636459392453053377493026875020744760145842401792378749321113719919618588095724485583919541019961884523908359133457357334538791778480910430756107407761555218113998374287548487
``````

This works, but note that using a dict for `FIB_CACHE` is kind of inefficient: the keys are always going to be value `1:N` where `N` is the largest value you’ve called `fib` on. This is going to fail if `N` is too large to hold in an `Int`, so we can do something else instead which is a bit more complicated but more efficient in term of both memory and compute:

``````const FIB_CACHE = BigInt[1, 1]

function fib(n::Integer)
n < 1 && return big(0)
n <= length(FIB_CACHE) && return FIB_CACHE[n]
sizehint!(FIB_CACHE, n)
r = fib(n-1) + fib(n-2)
push!(FIB_CACHE, r)
return r
end
``````

This is a bit tricky and relies on a few subtle things:

• we ensure that `FIB_CACHE` is grown to the right size before doing any work by calling `sizehint!` first, which reallocates the array memory if necessary
• then we recursively compute `r` which fills in all the cache entries < `n`
• these calls never have to reallocate the cache because of the `sizehint!` call
• calling `push!(FIB_CACHE, r)` always puts the value at the right place beacuse the recursive calls have already filled in all the values up to `n-1` by that time
4 Likes

This is exactly the same code in Why is this code not working?. Homework problem?

2 Likes

Just for fun, here’s an iterative version instead which is clearer and more efficient:

``````function fib(n::Integer)
n < 1 && return big(0)
m = length(FIB_CACHE)
if m < n
resize!(FIB_CACHE, n)
for i = m+1:n
FIB_CACHE[i] = FIB_CACHE[i-1] + FIB_CACHE[i-2]
end
end
return FIB_CACHE[n]
end
``````
1 Like

Thank you for your explanation, Yes this is a part of an Exercise. but actually the problem is when I running this code in Julia

``````global fib_cache = Dict{BigInt, BigInt}(0 => 0, 1 => 1)
function fib(n::Integer)
global fib_cache
get!(fib_cache, BigInt(n), fib(n-1) + fib(n-2))
end
``````

i got LoadError: StackOverflowError and it seems that this code in this way dosn’t check whether the Fibonacci number is in the cache and it repeated many time so we got this error but i am not sure this is the only error or not !

Did you look at your classmate’s post? The problem is explained clearly by Henrique.

Edit: I see now that you responded to Henrique in that thread. Let’s take it there.

1 Like

Yes , and you can also check my reply to him . the problem is not related to Negative numbers as he explained. the code doesn’t work in general even if for a positive number