Function Problem

General Usage
1

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
> if haskey(fib_cache, n)
> 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
2

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:

https://stackoverflow.com/questions/60997656/how-does-this-recursive-function-in-julia-work/60998070#60998070

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
3

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

2 Likes
4

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
5

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 !

6

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
7

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