Debugging a simple program in Erlang

Question

I have just started to learn erlang(and functional programming) and I am stuck on a simple program. The object of the program is to find the largest prime factor of a number. This is my program:

lprime(N, L, D) when D == N->
    if N rem D == 0 -> D;
       true-> L
    end;
lprime(N,L,D) ->
    if N rem D == 0 ->
        lprime(N/D, D, D);
      true -> lprime(N, L, D+1)
    end.
lprime(N)->
    lprime(N,1,2).

Here's how it should run for some inputs:

lprime(3)->lprime(3,1,2)->lprime(3,1,3)->3
lprime(36)->lprime(36,1,2)->lprime(18,2,2)->lprime(9,2,2)->lprime(9,2,3)->lprime(3,3,3)->3
lprime(14)->lprime(14,1,2)->lprime(7,2,2)->lprime(7,2,3)->lprime(7,2,4)->lprime(7,2,5)->lprime(7,2,6)->lprime(7,1,7)->7

But the program always returns the first prime divisor instead. lprime(24)->2, lprime(9)->3

I wrote an equivalent(in my opinion) program in Python which I am more familiar with that performs exactly as expected:

def lprime(N, L=1, D=2):
    if D==N:
        if N%D == 0: return D
        return L
    if N%D == 0:
        return lprime(N/D, D, D)
    return lprime(N, L, D+1)

I also tried another version without a guard(it looks cleaner too) but this one seems to go into an infinite recursion, again the python equivalent(IMO) works as expected:

lprime2(1, L, D) ->
    L;
lprime2(N,L,D) ->
    if N rem D == 0 ->
        lprime2(N/D, D, D);
      true -> lprime2(N, L, D+1)
    end.
lprime2(N)->
    lprime2(N,1,2).

I was trying to debug the program using dbg, the documentation of which is very sparse and I don't understand the steps very well. The steps I used were:

1> dbg:start().
{ok,<0.35.0>}
2> dbg:tracer().
{ok,<0.35.0>}
3> dbg:tp(first,lprime, 1, []).
{ok,[{matched,nonode@nohost,1}]}
4> dbg:tp(first,lprime,3,[]).
{ok,[{matched,nonode@nohost,1}]}
5> dbg:p(all,c).
{ok,[{matched,nonode@nohost,26}]}
6> first:lprime(10).
(<0.33.0>) call first:lprime(10)
2
7> first:lprime(10,1,2).
(<0.33.0>) call first:lprime(10,1,2)

Edit: Emphasis added
I didn't find any useful information from this and I'd appreciate any pointers on how to debug effectively too but mainly I'd like to know what causes the program to fail.

Answer 1

The mistake in porting the code is that in Python, 5 / 2 == 2 while in Erlang, 5 / 2 == 2.5. You need to use the div operator: 5 div 2 == 2

1> 5 / 2.
2.5
2> 5 div 2.
2

So, in your code, replace:

lprime(N/D, D, D);

with:

lprime(N div D, D, D);

With this change, I get the expected outputs:

2> a:lprime(3).
3
3> a:lprime(36).
3
4> a:lprime(14).
7

On a side note about your logic, I'm pretty sure if N == D, N rem D will always equal 0, so you might want to simplify the code there.

Answer 2

You're using floating-point division instead of integer division, and that's causing exceptions in rem. But you're not seeing these exceptions because you're calling rem in a guard. You can see this by using case rather than if:

lprime2(1, L, D) ->
    L;
lprime2(N,L,D) ->
    case N rem D of
        0 -> lprime2(N/D, D, D);
        _ -> lprime2(N, L, D+1)
    end.
lprime2(N)->
    lprime2(N,1,2).

This will let you see the exceptions:

1> c(lp).
lp.erl:4: Warning: variable 'D' is unused
{ok,lp}
2> lp:lprime2(14).
** exception error: an error occurred when evaluating an arithmetic expression
     in function  lp:lprime2/3 (/tmp/lp.erl, line 7)

To fix it, use div rather than / in your second clause of lprime/3:

    lprime2(N,L,D) ->
        case N rem D of
            0 -> lprime2(N div D, D, D);
            _ -> lprime2(N, L, D+1)
        end.

In general, idiomatic Erlang code uses case more than if because the latter allows only guards in its clauses.

One other thing to note is that in your code with the guards on the function clauses (as well as in your Python code), when N == D, then N rem D will always be true, so you can simplify the code:

lprime(N,_,N) ->
    N;
lprime(N,_,D) when N rem D == 0 ->
    lprime(N div D, D, D);
lprime(N,L,D) ->
    lprime(N, L, D+1).

In the first clause, we use the same variable N for both the N and D arguments. This clause runs only when N and D are equal. There's no need for the rem test in this case.