Why is this code not working?

New to Julia
1

The function below is to calculate the fibonacci sequence using get! but i don’t understand why it is not working.

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

You are not checking whether your Fibonacci number is in the cache, I think.

3

First, when you post something like that, it is good to use
```julia
code here
```
to make the code more readable. It becomes this way:

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

It is also good to say how the code is not working, with which values did you test? The code finishes in error, with an wrong answer, or does it just never returns?

Second, your problem is that fib(n‑1) + fib(n‑2) is not lazy, so it will be computed anyway, even if there is a value in the cache. And as you do not consider negative values, it ends in a “infinite” recursive call with negative values as parameters.

The code below solves this problems:

fib_cache = Dict{BigInt, BigInt}(0 => 0, 1 => 1)
function fib(n::Integer)
  n < zero(n) && @error "negative parameter n ($n) for fib"
  global fib_cache
  get!(fib_cache, BigInt(n)) do
    fib(n - 1) + fib(n - 2)
  end 
end

@show fib(0)
@show fib(1)
@show fib(2)
@show fib(3)
@show fib(4)
#@show fib(-1)
4 Likes
5

Perhaps this package could be relevant? GitHub - marius311/Memoization.jl: Easily and efficiently memoize any function, closure, or callable object in Julia.

It does what you appear to be doing

6

I tried his code and it doesn’t work also for positive number ! , I mean the problem is not related to Negative numbers … the code doesn’t work in General

7

Hi @A.U.M, If you read this:

this is @Henrique_Becker saying that the problem is not negative input numbers but the fact that you are calling fib(n-1) + fib(n-2) whether or not n is in your cache, so it just cascades down to n=-Inf

3 Likes
8

I never said their code worked for zero or positive numbers. I said the code does not work because it is an infinite recursion, and if they did add an exception throw for negative input, they would have perceived the infinite recursion, as it goes from the number that is passed as parameter (that can be a positive one) to negative infinite.

This can be easily checked by adding this assertion:

@assert n >= zero(n)

as the first line of their original code, and now any call to the method will throw the exception even if the parameter is positive.

2 Likes
9

You beat me to it, XD.

10

Thank you I didn’t notice this

1 Like
11

Thank you :)) I got it

1 Like
12

Here’s something you can do to have the error demonstrated:

julia> function fib(n::Integer)
           global fib_cache
           @show n
           if n < -4 
               error("this is broken")
           end
           get!(fib_cache, BigInt(n), fib(n-1) + fib(n-2))
       end
fib (generic function with 1 method)

julia> fib(4)
n = 4
n = 3
n = 2
n = 1
n = 0
n = -1
n = -2
n = -3
n = -4
n = -5
ERROR: this is broken
Stacktrace:
 [1] error(::String) at ./error.jl:33
 [2] fib(::Int64) at ./REPL[116]:5
 [3] fib(::Int64) at ./REPL[116]:7 (repeats 9 times)
 [4] top-level scope at REPL[117]:1
 [5] eval(::Module, ::Any) at ./boot.jl:331
 [6] eval_user_input(::Any, ::REPL.REPLBackend) at /home/mason/julia/usr/share/julia/stdlib/v1.4/REPL/src/REPL.jl:86
 [7] run_backend(::REPL.REPLBackend) at /home/mason/.julia/packages/Revise/Pcs5V/src/Revise.jl:1073
 [8] top-level scope at none:0

The thing is that get! is a function, so to compute get!(x, y, z), julia needs to first know what x ,y and z are, but in this case, z = fib(n-1) + fib(n-2), so to give that value to the third argument of get! it then recurses into fib(n-1) and fib(n-2) respectively. This causes it to neverendingly flow towards -Inf

3 Likes