How can this code be better structured in Elixir?

Question

I'm learning Elixir as my first functional-style language. As a first simple project to familiarize myself with the environment and syntax, I chose to build a simple program that computes the prime factors for a number provided on the command line. This is my first solution:

defmodule Prime do
  defp is_factor?(number, divisor) do
    cond do
      rem(number, divisor) == 0 -> divisor
      true                      -> nil
    end
  end

  defp not_nil?(thing) do
    !is_nil(thing)
  end

  def factors(number) when number == 1 do
    []
  end

  def factors(number) do
    1..div(number, 2)
      |> Enum.map(&(is_factor?(number, &1)))
      |> Enum.filter(&not_nil?/1)
  end

  def is_prime?(number) when number == 1 do
    true
  end

  def is_prime?(number) do
    factors(number) == [1]
  end

  def prime_factors(number) do
    factors(number)
      |> Enum.filter(&is_prime?/1)
  end
end

input = hd(System.argv)
number = String.strip(input) |> String.to_integer
IO.puts "Prime factors of #{number} are #{inspect Prime.prime_factors(number)}"

It works, but runs rather slowly. On my laptop, run times are around 11 seconds to compute the prime factors of 50,000,000.

As I read more, it seems like this original solution is not very Elixir-like. So I restructured the code to this:

defmodule PrimeFactors do
  def of(n) do
    _factors(n, div(n, 2))
  end

  defp _factors(_n, 1) do
    [1]
  end
  defp _factors(n, divisor) when rem(n, divisor) == 0 do
    cond do
      is_prime?(divisor) -> _factors(n, divisor - 1) ++ [divisor]
      true               -> _factors(n, divisor - 1)
    end
  end
  defp _factors(n, divisor) do
    _factors(n, divisor - 1)
  end

  defp is_prime?(1) do
    true
  end
  defp is_prime?(n) do
    of(n) == [1]
  end
end

input = hd(System.argv)
number = String.strip(input) |> String.to_integer
IO.puts "Prime factors of #{number} are #{inspect PrimeFactors.of(number)}"

Typical run time of this code to compute the prime factors of 50,000,000 is substantially worse: over 17 seconds.

I built equivalent programs in Swift and Ruby. Optimized Swift runs in just over 0.5 seconds, and Ruby (2.2, and never known for its speed) runs in a bit over 6 seconds.

My primary question is: How should the Elixir code be structured to be more idiomatic and to avoid the performance problems I'm seeing?

I'm also left with some concerns that given such a simple problem, it's possible to write Elixir code that varies wildly in efficiency. Perhaps this is mostly my inexperience in functional styles showing?

Answer 1

Let me start with a quick rant then we will move to the answer. I believe we are worrying about the wrong thing here. Once you posted the Ruby code, my first thought was: why does the Elixir code does not look as clean as the Ruby one?

Let's solve this problem first:

defmodule PrimeFactors do
  def of(n) do
    factors(n, div(n, 2)) |> Enum.filter(&is_prime?/1)
  end

  def factors(1, _), do: [1]
  def factors(_, 1), do: [1]
  def factors(n, i) do
    if rem(n, i) == 0 do
      [i|factors(n, i-1)]
    else
      factors(n, i-1)
    end
  end

  def is_prime?(n) do
    factors(n, div(n, 2)) == [1]
  end
end

IO.inspect PrimeFactors.of(50_000_000)

Much better. Let's run this cleaner version? 3.5 seconds on my machine (compared to 24 seconds of the earlier one).

Now with a cleaner code, it is easier to compare what is wrong in your implementation. Your _factors function is actually _factors_and_prime because you are already checking if the number is prime in there. So when you check for is_prime?, you are actually computing "factors and prime" which is much more expensive to calculate than the actual "factors" since it ends up calling is_prime? again and recursively.

As someone, somewhere, said:

1. Make it work
2. Make it beautiful
3. Make it fast (if necessary)

:)

Answer 2

Optimized works in under a second:

defmodule PF do

  @doc "Calculates the unique prime factors of a number"
  def of(num) do
    prime_factors(num)
    |> Enum.uniq
  end

  @doc """
  Calculates all prime factors of a number by finding a low factor
  and then recursively calculating the factors of the high factor.
  Skips all evens except 2.
  Could be further optimized by only using known primes to find factors.
  """
  def prime_factors(num , next \\ 2)
  def prime_factors(num, 2) do
    cond do
      rem(num, 2) == 0 -> [2 | prime_factors(div(num, 2))]
      4 > num          -> [num]
      true             -> prime_factors(num, 3)
    end
  end
  def prime_factors(num, next) do
    cond do
      rem(num, next) == 0 -> [next | prime_factors(div(num, next))]
      next + next > num   -> [num]
      true                -> prime_factors(num, next + 2)
    end
  end

end

Bonus, tests:

ExUnit.start

defmodule PFTest do
  use ExUnit.Case

  test "prime factors are correct" do
    numbers = [4, 15, 22, 100, 1000, 2398, 293487,
               32409850, 95810934857, 50_000_000]
    Enum.map(numbers, fn (num) ->
      assert num == Enum.reduce(PF.prime_factors(num), &*/2)
    end)
  end
end

We end up writing much more literate/idiomatic elixir by reducing the problem domain. Further optimization could be achieved but perhaps at a loss of readability without significant performance gain. Also, as docs and tests are built into the platform, including them is painless and makes the code much more readable. :)