stevensonmt

stevensonmt OP

I tried to modify an example from RosettaCode.org for a prime sieve algorithm. I’m not entirely sure I understood the original code. I tried to make sense of it with more explicit variable names but I was hoping someone could correct my understanding if I missed something. Also wondering why you have to prepopulate the odd primes with 3 and 5.

  def primes_to(limit) do
    # prepopulate with 2 so we only have to check odd numbers
    [2]
    |> Stream.concat(oddprimes())
    |> Enum.take_while(&(&1 < limit))
  end

  defp oddprimes() do
    # prepopulating with 3 and 5 is necessary but not sure why
    [3, 5]
    |> Stream.concat(
      Stream.iterate(
        {5, 25, 7, nil, %{9 => 6}},
        &check_next(&1)
      )
      |> Stream.map(fn {_, _, p, _, _} -> p end)
    )
  end

  # map ==> %{next_next_odd => increment}
  defp check_next({last_prime, last_prm_sq, next_odd, cached_primes?, map}) do
    cached_primes =
      if cached_primes? === nil do
        oddprimes() |> Stream.drop(1)
      else
        cached_primes?
      end

    next_next_odd = next_odd + 2

    # if the next number to check would be greater than the square of the last prime
    # advance the next known prime and its square as the new minimum step
    if next_next_odd >= last_prm_sq do
      inc = last_prime + last_prime
      next_cached_primes = cached_primes |> Stream.drop(1)
      [next_last_prime] = next_cached_primes |> Enum.take(1)

      check_next(
        {next_last_prime, next_last_prime * next_last_prime, next_next_odd, next_cached_primes,
         map |> Map.put(next_next_odd + inc, inc)}
      )
    else
      # if the next number to check is under the minimum step to advance
      # check if the map includes that number and remove it
      # find the first multiple of the increment for that number that is not
      # in the map and put it in the rmap (produced by removing the next number)
      #  with the increment as the value and check the next odd with the current
      #  last prime limits and cache
      if Map.has_key?(map, next_next_odd) do
        {inc, rmap} = Map.pop(map, next_next_odd)

        [next_candidate] =
          Stream.iterate(next_next_odd + inc, &(&1 + inc))
          |> Stream.drop_while(&Map.has_key?(rmap, &1))
          |> Enum.take(1)

        check_next(
          {last_prime, last_prm_sq, next_next_odd, cached_primes,
           Map.put(rmap, next_candidate, inc)}
        )
      else
        # if the next number to check is under the minimum step to advance
        # and it is not a key in the current map check the next odd
        # against the current last prime limits, cache, and map of increments
        {last_prime, last_prm_sq, next_next_odd, cached_primes, map}
      end
    end
  end
end

First 5 of 5 Posts Switch mode

al2o3cr

al2o3cr

check_next uses oddprimes - which depends on check_next after the first two elements. The initial [3, 5] is similar to the “base case” in traditional recursive code; without it, the algorithm wouldn’t be able to get started.

the_wildgoose

the_wildgoose

Here’s my contribution to this… Priority queues turn out to be your next step up from the basic wheel for immutable languages. Perhaps it’s useful?

https://github.com/ewildgoose/elixir-primes

stevensonmt

stevensonmt OP

I guess I don’t understand the need to concat [3,5] but pass nil as the first round argument instead of just starting with [3,5] as the cached_primes? initial value.

stevensonmt

stevensonmt OP

Very nice work. Going to try a deeper dive into it to try and understand more fully. Thanks!

al2o3cr

al2o3cr

The initial value of cached_primes? is an infinite stream, the first two elements of which happen to be 3 and 5 - the rest of it is the result of iterating check_next.

— All posts loaded —

Where Next? Top

Trending in Questions Top

stjefim
Hello! Suppose you are building workflow (order / task / payment) processing system with the following requirements: Each workflow con...
New
jonnycharles
I’m in search of an Elixir library that offers PDF generation capabilities similar to Ruby’s Prawn. While there have been discussions abo...
New
spammy
I’m looking to build a personal workflow to quickly deploy web applications written in elixir/phoenix, for local consumption (ie not on t...
New
dli
Before I dive in myself, did anyone successfully sprinkle Hologram into their existing LiveView app? Looking for hints regarding: Addi...
New
bottlenecked
Hi all, I wanted to ask how the community is dealing with post-release steps. Today we have Ecto migrations, which make sure that the db...
New
roeland
Kia ora, We have been using elixir-google-api to connect to Google Drive. However, with the updates to Tesla due to CVEs this is now bro...
New
michallepicki
I am using Oban and occasionally, shortly after a deployment, a handful of jobs can fail because of dependency on other parts of the syst...
New

Other Trending Topics Top

JesseHerrick
Hey, I’m Jesse and I’m the main contributor behind Dexter, a full-featured, lightning-fast Elixir LSP optimized for large codebases. It s...
New
jimsynz
Beam Bots (or just BB for short) is a framework for building fault-tolerant robotics applications in Elixir using familiar OTP patterns. ...
New
Damirados
Hello everyone. After busy few months I am happy to announce v0.1.0 of Emerge &amp; Solve. They are GUI (Emerge) and State management (S...
New
netoum
Corex is an accessible, unstyled UI component library for Phoenix that integrates Zag.js state machines using Vanilla JavaScript and Live...
New
ausimian
Emily is an Elixir library that runs Nx computations on Apple’s MLX. Install it as the default Nx backend and Nx, defn, Axon, Nx.Serving,...
New
juhalehtonen
There has been a thread to discuss the Stack Overflow Developer Survey on this forum every year since 2018, so here’s yet another one for...
New

We're in Beta

About us Mission Statement