Project Euler Problem 5

Questions / Help
1

Hi guys, im resolving problem 5, and reach this solutions :

@numeros Enum.to_list(2..20)

  def valor do
    Stream.iterate(21,&(&1 + 1))
    |> Stream.filter(&valores(&1, @numeros) == true)
    |> Enum.take(1)
  end

  def valores(_num,[]) do
     true
  end

  def valores(num, [cabeza | cola]) do
    case rem(num, cabeza) do
      0 -> valores(num,cola)
      _ -> false
    end
  end

And it take like 38 seconds to conclude.

Then i looked for other solutions and find this:

@numbers Enum.to_list 20..2

  def solve do
    _solve(21, @numbers)
  end

  defp _solve(n, []), do: n

  defp _solve(n, [h | t]) do
    case rem(n, h) do
      0 -> _solve(n, t)          
      _ -> _solve(n+1, @numbers) 
    end
end

And reach the result in 5 seconds. Im wonder why in one take so much time and the other is more faster?

1 Like
2

The second solution uses a kind of Tail Call Optimization. In general, if you can make the last expression in a recursive function a call to that function, the compiler can optimize that kind of recursion.

The second solution is faster because both branches of the case are TCO. While not strictly TCO, the compiler is smart enough to do the right thing in this case.

While in many languages TCO is absolutely required for large recursions to work at all the situation in Elixir and Erlang is quite different. This blog post is an interesting read.

In the case of the Euler problems, (at least the early ones), the size and type of the recursions is so large that TCO solutions will almost always be faster. But those problems are somewhat of a special edge case. The important lesson to take away is that benchmarking on typical inputs is the only way to know for sure whether changing your code is faster.

3 Likes