Check if the Nth number of Fibonacci is NthFib or not - arithmetic error fail

Question

Here is my predicate, which should check if the N^th number of Fibonacci is NthFib or not.

I am getting arithmetic is not function error.

K - current iteration
N - Nth number
Tmp - previous Fibonacci number
Ans - current Fibonacci number

Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21, etc. (sum of two previous = current)

fib(N, NthFib) :-
    fib(1, N, 1, 0, NthFib).

fib(K, N, Ans, Tmp, NthFib) :-
    % true if Ans is NthFib, false otherwise
    ( K > N -> Ans is NthFib
    ; K =< N -> fib( K + 1, N, Ans + Tmp, Ans, NthFib)
    ).

Answer 1

First, re-write your original code as

fib(N, NthFib) :- fib(1, N, 1, 0, NthFib).

fib(K, N, Ans, Tmp, NthFib) :- 
  K > N -> Ans = NthFib;       % use = instead of is here
  K =< N -> fib((K+1), N, (Ans+Tmp), Ans, NthFib).

Now,

?- fib(7,X).

X = 1+0+1+ (1+0)+ (1+0+1)+ (1+0+1+ (1+0))+ (1+0+1+ (1+0)+ (1+0+1))+ 
       (1+0+1+ (1+0)+ (1+0+1)+ (1+0+1+ (1+0))) 

Yes
?- fib(7,X), Z is X.

X = 1+0+1+ (1+0)+ (1+0+1)+ (1+0+1+ (1+0))+ (1+0+1+ (1+0)+ (1+0+1))+ 
       (1+0+1+ (1+0)+ (1+0+1)+ (1+0+1+ (1+0)))
Z = 21 

See, in Prolog data is symbolic, and using is forces the arithmetic expression into an arithmetic value (evaluates the expression under assumption that it is a meaningful arithmetic expression).

To check whether 20 is 7-th Fibonacci number, we can use arithmetic comparison operator which evaluates its arguments,

?- fib(7,X), X =:= 20.

No

Which means that your code just needs to be rewritten as

fib(N, NthFib) :- fib(1, N, 1, 0, NthFib).

fib(K, N, Ans, Tmp, NthFib) :- 
  K > N -> NthFib is Ans ;       % exchange the order of operands
  K =< N -> fib((K+1), N, (Ans+Tmp), Ans, NthFib).

Now it works as you intended:

?- fib(7,21).

Yes
?- fib(7,20).

No

But it doesn't work efficiently, carrying all those long expressions around as symbolic data. We only need the numbers really, so just as you were shown in other answers, is is used to achieve that. Every symbolic sub-expression that you have, take it out of its enclosing expression, and name it, using is instead of =.

BTW 21 really is an 8-th member of the sequence. Correct your code.

Answer 2

If K is unified with 1, K + 1 is unified with 1 + 1, not 2.

Answer 3

I have rewrote an algorithm, it is more simple and efficient now:

fib(0, 0).
fib(1, 1).
fib(N, F) :-
    N > 0,
    X is N - 2,
    Y is N - 1,
    fib(X, A),
    fib(Y, B),
    F is A + B.