DEV Community: David Berry

Generating a Concordance

David Berry — Sun, 28 Jan 2024 20:39:00 +0000

Merriam-Webster defines a concordance as an alphabetical index of the principal words in a book or the works of an author with their immediate contexts. It is useful for building an index of words in a given text. In this article we will build a concordance generator using Java. The concordance should list the word, the number of times it appears in the text, and the sentences in which the word appears. The text that we will work with is the Gettysburg Address

Creating the project

Let's start by creating the project. We will use the maven quickstart archetype to generate and empty project:

mvn archetype:generate -DarchetypeGroupId=org.apache.maven.archetypes -DarchetypeArtifactId=maven-archetype-quickstart -DarchetypeVersion=1.4

You will be asked to fill in the following questions, and can use groupIds and packages that make sense for you:

Define value for property 'groupId': org.exaxis.concordance
Define value for property 'artifactId': concordance
Define value for property 'version' 1.0-SNAPSHOT: : 
Define value for property 'package' org.exaxis.concordance: : 
Confirm properties configuration:
groupId: org.exaxis.concordance
artifactId: concordance
version: 1.0-SNAPSHOT
package: org.exaxis.concordance
 Y: : Y

When you are done, you should have a project that looks like this:

Setting Up Main

The first thing we are going to do is setup main. By default, quickstart sets up main to be a "Hello World" program.

/**
 * Hello world!
 *
 */
public class App 
{
    public static void main( String[] args )
    {
        System.out.println( "Hello World!" );
    }
}

We want to keep all the logic out of main so we will need a Concordance class to encapsulate the logic. Main will instantiate a Concordance from a file name and print out the concordance. We will also need to get the filename from the args passed into main. The following code should suffice:

/**
 * Generate a Concordance from the file passed in
 */
public class App 
{
    public static void main( String[] args )
    {
        // make sure we have enough arguments
        if (args.length==0)
            usage();

        // grab the filename from the last argument
        String filename = args[args.length-1];

        try {
            //load the concordance from the file
            Concordance concordance = Concordance.fromFile(filename);

            // print the concordance
            concordance.print(System.out);
        } catch (Exception e) {
            errorMessageAndExit("Error processing file: "+filename+e.getLocalizedMessage());
        }
    }

    private static void usage(){
        errorMessageAndExit("Usage: java -jar target/concordance-1.0-SNAPSHOT.jar inputFile");
    }

    private static void errorMessageAndExit(String message){
        System.err.println(message);
        System.exit(1);
    }
}

In short, this code:

makes sure there is at least one argument.
assumes the last argument is the filename.
Creates a concordance using the Concordance.fromFile() factory method.
Prints the concordance to System.out using the Concordance.print() method.
If the concordance throws an exception, the error will be printed and the return code will be 1.

The Concordance class

In order for App.main to compile, we will need a Concordance Class with a static fromFile method, and a print method. Here is the basic class

public class Concordance {
  public void print(PrintStream printStream) {
    printStream.println("Not Implemented");
  }

  public static Concordance fromFile(String filename) throws IOException {
    return fromReader(new FileReader(filename));
  }

  public static Concordance fromString(String s) throws IOException {
    return fromReader(new StringReader(s));
  }

  public static Concordance fromReader(Reader reader) throws IOException {
    try (BufferedReader bufferedReader = new BufferedReader(reader)) {
      return fromBufferedReader(bufferedReader);
    } catch (Exception e) {
      throw e;
    }
  }

  public static Concordance fromBufferedReader(BufferedReader bufferedReader) throws IOException {
    // Process the text
    process(bufferedReader);

    // return the Concordance
    return new Concordance();
  }

  private static void process(BufferedReader bufferedReader) throws IOException {
  }

}

There are several factory methods (fromFile, fromString, fromReader, and fromBufferedReader) to allow us to turn a file or a string into a BufferedReader. A file will be used from the command line and strings can be used for testing. It is fromBufferedReader where the text is processed and a Concordance is generated and returned.

But what is a concordance? As stated above, the concordance is an alphabetical list of words and there context, being the number of occurrences and the sentences that the word appears in.

What structure(s) would be best for storing this info. Let's start with the word usage info. We would need the word, the occurrences, and the list of sentences that it appears in. The sentences can be represented by the sentence number in the text. The following class would work:

public class WordUsage {
  private final String word;
  private final ArrayList<Integer> sentences = new ArrayList<>();

  public WordUsage(String word, int sentence){
    this.word = word;
    addSentence(sentence);
  }

  public WordUsage(String word, int[] locations){
    this.word = word;
    Arrays.sort(locations);
    for (int sentence : locations)
      this.sentences.add(sentence);
  }

  public String getWord() {
    return word;
  }

  public int getOccurrences() {
    return sentences.size();
  }

  public List<Integer> getSentences() {
    return sentences;
  }

  public void addSentence(int sentence){
    sentences.add(sentence);
  }
}

WordUsage stores the word, and the sentences that it appears in. The occurrences is the number of sentences it appears in. There is a constructor for creating the WordUsage for the first sentence, or multiple sentences at once. addSentence allows you to add additional sentences to the WordUsage as they are found.

Now we need a structure to store the words alphabetically with their usage data. A TreeMap seems to good fit as it is a sorted map that can hold the usage data for the word. We can add a TreeMap<String, WordUsage> to the Concordance class to hold the concordance data. Using the TreeMap means that we can retrieve the sorted WordUsages without any additional sorting. We can now define a constructor which takes the TreeMap to instantiate the Concordance class. This also gives us the return value for the process method, and we can complete the fromBufferedReader factory method. The updated code is:

public class Concordance {
  private final TreeMap<String, WordUsage>  wordMap;

  private Concordance(TreeMap<String, WordUsage>  wordMap){
    this.wordMap = wordMap;
  }

  public static Concordance fromBufferedReader(BufferedReader bufferedReader) throws IOException {
    // Process the text
    // return the Concordance
    return new Concordance(process(bufferedReader));
  }

  private static TreeMap<String, WordUsage> process(BufferedReader bufferedReader) throws IOException {
    assert(bufferedReader != null);
    TreeMap<String, WordUsage> wordUsageMap = new TreeMap<>();
    // process the bufferedReader
    return wordUsageMap;
  }
}

The only thing left to do is generate the TreeMap<String, WordUsage>. In order to make sure it is as efficient as possible we will implement a simple single-pass lexer which will break the text into words to be added to the concordance. Whitespace, punctuation, and end of sentence characters will be used to identify word boundries. End of sentence characters will also be used to increment the current sentence number. Here is the code for the processor:

private static TreeMap<String, WordUsage> process(BufferedReader bufferedReader) throws IOException {
    assert(bufferedReader != null);
    TreeMap<String, WordUsage> wordUsageMap = new TreeMap<>();
    // process the bufferedReader
    int currentSentence = 1;
    StringBuilder stringBuilder = new StringBuilder();

    // Use a simple single-pass lexer to return the words of the corpus
    int ch = bufferedReader.read();
    while (ch != -1){
      char curr = (char)ch;

      // Are we at the end of the word
      if (Character.isWhitespace(curr)||isEndOfSentence(curr)||isPunctuation(curr)) {
        if (!stringBuilder.isEmpty()){
          // add the word to the TreeMap
          addWord(wordUsageMap, stringBuilder.toString().toLowerCase(), currentSentence);
          stringBuilder = new StringBuilder();
        }
        if (isEndOfSentence(curr)) {
          ++currentSentence;
        }
      } else {
        stringBuilder.append(curr);
      }

      ch = bufferedReader.read();
    }
    return wordUsageMap;
  }

  private static void addWord(TreeMap<String, WordUsage> wordStatsMap, String word, int sentence){
    WordUsage wordUsage = wordStatsMap.get(word);
    if (wordUsage == null) {
      wordStatsMap.put(word, new WordUsage(word, sentence));
    } else {
      wordUsage.addSentence(sentence);
    }
  }

  private static boolean isEndOfSentence(char ch){
    return ch=='.'||ch=='?'||ch=='!';
  }

  private static boolean isPunctuation(char ch){
    return ch == ',' || ch == ':' || ch == ';' || ch == '"' || ch == '\'' || ch == '(' || ch == ')' || ch == '-';
  }

The only thing left is to fill in the Concordance.print method so we can print out the results of the concordance. Since the printing will require printing the WordUsages, we will add a toString method to the WordUsage class. Here are the print and toString methods:

Concordance.java

  public void print(PrintStream printStream) {
    for (WordUsage wordUsage : wordMap.values()){
      printStream.println(wordUsage.toString());
    }
  }

WordUsage.java

  private String printLocations(){
    StringBuilder sb = new StringBuilder();
    for(int sentence: sentences){
      sb.append(sentence);
      sb.append(',');
    }
    sb.deleteCharAt(sb.length()-1);
    return sb.toString();
  }

  @Override
  public String toString() {
    return String.format("%15s: {%d:%s}", getWord(), getOccurrences(), printLocations());
  }

Finally, Running the concordance on the Gettysburg Address is done as follows:

java -jar target/concordance-1.0-SNAPSHOT.jar src/test/resources/GettysburgAddress.txt

and produces the following output:

              a: {7:1,2,3,4,4,6,10}
          above: {1:7}
            add: {1:7}
       advanced: {1:9}
            ago: {1:1}
            all: {1:1}
     altogether: {1:5}
            and: {6:1,1,2,5,7,10}
            any: {1:2}
            are: {3:1,2,3}
             as: {1:4}
    battlefield: {1:3}
             be: {2:9,10}
         before: {1:10}
          birth: {1:10}
          brave: {1:7}
        brought: {1:1}
            but: {2:6,8}
             by: {1:10}
            can: {5:2,6,6,6,8}
          cause: {1:10}
          civil: {1:2}
           come: {1:4}
      conceived: {2:1,2}
     consecrate: {1:6}
    consecrated: {1:7}
      continent: {1:1}
        created: {1:1}
           dead: {3:7,10,10}
       dedicate: {2:4,6}
      dedicated: {4:1,2,9,10}
        detract: {1:7}
       devotion: {2:10,10}
            did: {1:8}
           died: {1:10}
             do: {1:5}
          earth: {1:10}
         endure: {1:2}
        engaged: {1:2}
          equal: {1:1}
            far: {2:7,9}
        fathers: {1:1}
          field: {1:4}
          final: {1:4}
        fitting: {1:5}
            for: {5:4,9,10,10,10}
         forget: {1:8}
          forth: {1:1}
         fought: {1:9}
           four: {1:1}
        freedom: {1:10}
           from: {2:10,10}
           full: {1:10}
           gave: {2:4,10}
            god: {1:10}
     government: {1:10}
          great: {3:2,3,10}
         ground: {1:6}
         hallow: {1:6}
           have: {5:4,7,9,10,10}
           here: {8:4,7,8,8,9,9,10,10}
         highly: {1:10}
        honored: {1:10}
             in: {4:1,2,6,10}
      increased: {1:10}
             is: {3:5,9,10}
             it: {5:5,7,8,9,10}
         larger: {1:6}
           last: {1:10}
        liberty: {1:1}
         little: {1:8}
           live: {1:4}
          lives: {1:4}
         living: {2:7,9}
           long: {2:2,8}
        measure: {1:10}
            men: {2:1,7}
            met: {1:3}
          might: {1:4}
         nation: {5:1,2,2,4,10}
          never: {1:8}
            new: {2:1,10}
          nobly: {1:9}
            nor: {1:8}
            not: {5:6,6,6,10,10}
           note: {1:8}
            now: {1:2}
             of: {5:3,4,10,10,10}
             on: {2:1,3}
             or: {2:2,7}
            our: {2:1,7}
         people: {3:10,10,10}
         perish: {1:10}
          place: {1:4}
           poor: {1:7}
        portion: {1:4}
          power: {1:7}
         proper: {1:5}
    proposition: {1:1}
         rather: {2:9,10}
      remaining: {1:10}
       remember: {1:8}
        resolve: {1:10}
        resting: {1:4}
            say: {1:8}
          score: {1:1}
          sense: {1:6}
          seven: {1:1}
          shall: {3:10,10,10}
         should: {1:5}
             so: {3:2,2,9}
      struggled: {1:7}
           take: {1:10}
           task: {1:10}
        testing: {1:2}
           that: {13:1,2,3,4,4,4,5,10,10,10,10,10,10}
            the: {11:1,7,8,9,9,10,10,10,10,10,10}
          their: {1:4}
          these: {2:10,10}
           they: {3:8,9,10}
           this: {4:1,5,6,10}
          those: {1:4}
           thus: {1:9}
             to: {8:1,4,7,9,9,10,10,10}
          under: {1:10}
     unfinished: {1:9}
             us: {3:9,10,10}
           vain: {1:10}
            war: {2:2,3}
             we: {10:2,3,4,5,6,6,6,8,10,10}
           what: {2:8,8}
        whether: {1:2}
          which: {2:9,10}
            who: {3:4,7,9}
           will: {1:8}
           work: {1:9}
          world: {1:8}
          years: {1:1}

Conclusion

A concordance generator is a useful tool to build an index of words from a body of text. The body of text can be processed in a single pass, and the sorted list of word usage information is simply the values of the TreeMap

The code for this project can be found on GitHub.

Generating Lottery Numbers

David Berry — Mon, 30 Oct 2023 17:04:13 +0000

I started buying lottery tickets when Powerball was nearing a payout of $2B. I bought five quick picks (machine generated numbers) and noticed that there were many duplicated numbers across the five picks. I even had two picks that started with the same two numbers. After the drawing, I found that I had zero matching numbers and decided that there must be a better way to generate the numbers and at least get more matching numbers.

OBVIOUS DISCLAIMERS:

There is nothing here that changes the odds of winning.
- Powerball is 1 in 292,201,338
- MegaMillions is 1 in 302,575,350.
All random number generators are not really random.
This algorithm just generates picks with non-repeating numbers.
This algorithm does make me feel better because I can circle more matching numbers

TERMINOLOGY
The Mega Millions description of how to play defines each pick as a "board", and each "board" consists of two pools of number. Pool 1 consists of 5 non-repeating numbers from 1 to 70. Pool 2 is 1 number from 1 to 25.

REQUIREMENTS

The program should support multiple lotteries
The arguments should be pool definitions in the form of "selections:max_num".
- Powerball = "5:69 1:26"
- Mega Millions = "5:70 1:25"
The program should figure out the minimum number of boards required to include all the numbers.

CLASSES
Lotto is responsible for parsing the command-line arguments, creating the pools, and printing out each board. The main loop is as follows:

      if (args.Length < 2)
        throw new ArgumentException("Wrong Number of Arguments");

      var pools = ParsePools(args);
      var minBoards = GetMinBoards(pools);
      var board = new List<ushort>();
      for (int i = 0; i < minBoards; i++)
      {
        foreach (var pool in pools)
        {
          pool.MoveNext();
          board.AddRange(pool.Current);
        }
        PrintBoard(i+1, board);
        board.Clear();
      }

ParsePools(args) parses the command-line arguments and returns a List<Pool>. GetMinBoards(pools) gets the minimum number of boards for each pool and returns the greatest. Next it iterates minBoards times and gets the next pick for each pool and adds it to the board. You may have noticed that Pool is an IEnumerator. Pool implements the IEnumerator<List<ushort>> interface.

public class Pool : IEnumerator<List<ushort>>
{
  private static Random _random = new Random();
  private List<ushort> _available;
  public ushort Selections { get; }
  public ushort MaxNumber { get; }


  public Pool(ushort selections, ushort maxNumber)
  {
    Selections = selections;
    MaxNumber = maxNumber;
    _available = LoadAvailable(maxNumber);
    Current = new List<ushort>();
  }
}

The Pool constructor takes as arguments, the number of selections that must be made for the pool and the maximum number that can be chosen. LoadAvailable adds integers 1..MaxNumber into a list for use in the board. Keeping the numbers in an available list allows the program not to have to remember the selections that were already made. A random number is generated as an index into the list and that item is used and removed. When the available list is empty, we call LoadAvailable again and immediately remove any numbers that are in the current unfinished board so that duplicates are avoided. When all the selections are made for the current pool, the selections are sorted.

  private void GetNextBoard()
  {
    Current.Clear();
    if (_available.Count < Selections)
    {
      Current.AddRange(_available);
      _available = LoadAvailable(MaxNumber, Current);
    }

    while (Current.Count < Selections)
    {
      int pick = _random.Next(0, _available.Count - 1);
      Current.Add(_available[pick]);
      _available.RemoveAt(pick);
      if (!_available.Any())
      {
        _available = LoadAvailable(MaxNumber, Current);
      }
    }

    Current.Sort();
  }

The last thing to remember is to call ceiling when calculating the minimum number of boards so that you don't miss some numbers because of a rounding error.

  public ushort MinBoards()
  {
    double boards = Math.Ceiling((double)MaxNumber / Selections);
    return (ushort)boards;
  }

Running the program for PowerBall is as follows:

lotto 5:69 1:26

which returns

 1:  02 16 35 42 53 25
 2:  24 36 39 41 51 11
 3:  06 32 46 56 65 17
 4:  33 34 47 61 66 15
 5:  04 17 22 25 57 01
 6:  11 38 50 59 62 09
 7:  05 07 09 37 49 06
 8:  12 13 28 44 45 18
 9:  03 08 14 26 40 03
10:  19 31 52 63 68 20
11:  01 15 21 29 67 08
12:  10 43 48 54 64 19
13:  20 23 27 30 58 24
14:  18 51 55 60 69 21
15:  04 14 39 56 62 22
16:  26 27 49 53 57 23
17:  12 21 22 36 38 13
18:  01 02 25 31 46 12
19:  09 13 19 44 63 16
20:  03 20 23 33 48 14
21:  08 35 37 47 66 07
22:  05 17 29 45 50 04
23:  06 11 40 42 54 02
24:  41 52 58 65 67 05
25:  07 10 16 28 64 10
26:  15 24 30 59 61 26

I hope you enjoyed this coding tangent I went on. If you happen to win the lottery using any numbers generated by lotto, I accept gratuities. The code is available here

LL(1) parsing in Scala

David Berry — Thu, 13 Jul 2023 15:52:08 +0000

From Wikipedia, an LL parser (Left-to-right, leftmost derivation) is a top-down parser for a restricted context-free language. An LL parser is called an LL(k) parser if it uses k tokens of lookahead when parsing a sentence. An LL(1) parser therefore has 1 token of lookahead. The lookahead allows you to make decisions on future tokens without removing the token from the input. Many modern day parsers are top down parsers which take a source file, turn it into a set of tokens, and parses those tokens into an abstract syntax tree or some other data structure.

Scala has a Source object that allows you to create an Iterator[Char] from files or strings. We will use this as the basis of the input for our parser. Unfortunately, iterators do not allow you to peek or look ahead. Once you call next() you have consumed the next Char. What we need is an iterator that allows you to peek and see the next item. Here is a PeekableIterator class that wraps an iterator and provides the peek() and poke() methods.

/**
 * Create a peekable iterator to allow the caller to peek() the next item without moving the current position.
 *
 * @param it an Iterator
 * @tparam T the type of value in the iterator
 */
class PeekableIterator[T](private val it:Iterator[T]) extends Peekable[T]:
  private var nextToken:Try[T] = Try(it.next)
  def peek:Try[T] = nextToken
  def poll:Try[T] =
    val currentToken = nextToken
    nextToken = Try(it.next)
    currentToken

PeekableIterator() takes an iterator parameter and immediately calls next to load the next token. nextToken is a Try[T] so that it captures either the successful token or the failure. peek() returns the nextToken, put does not call next on the iterator. poll(), on the other hand, will return the nextToken and will call next() on the iterator and move to the next token.

Now that we can look ahead, let's define the goal of the parser. The parser should parse english text and return a list of sentences where each sentence is a list of words. The return type is Vector[Vector[String]] as Vector has better append performance than List. So how do we go from a Peekable[Char] to the Vector[Vector[String]]?

Most parsers start with a lexical analysis(tokenizing) step and then a parsing step. Our parsing goal is simple and does not require an LL(1) parser, but we use LL(1) parsing techniques to give readers an example they can use for more complicated parsing. Therefore we will process the source file using both the tokenizing step and a parsing step. The tokenizing step is just another parser but is usually referred to as a lexer. A first implementation could be step 1 as a lexer of Char to Vector[String] and step 2 is a Parser of Vector[String] to Vector[Vector[String]].

The shortcoming of this design is that the entire file is turned into tokens before any tokens are consumed by the parser. If you try to parse an extremely large file, you could run out of memory building the Vector[String] and never parse one token. It would be more efficient, in both time and space, to be able to transform the source file into tokens in a stream-like way where tokens are created lazily and consume the source input as needed.

3 ways to solve this problem were considered: LazyList, Akka Streams, and chained iterators. The addition of Akka Streams seemed like overkill for a simple parser, but it may be the subject of a future article. LazyList's immutability and memoization made it complicated to just create and consume one token at a time. Hence, I was left with chaining iterators together.

The goal of iterator chaining is to allow one iterator to use another iterator to lazily create its next item. To demonstrate this I will chain Iterator[Char] to Iterator[String]. The chaining is done as an apply on the PeekableIterator object:

/**
 * Companion object for creating PeekableIterators from an iterator or by chaining iteratars.
 */
object PeekableIterator:
  def apply[T](it:Iterator[T]):PeekableIterator[T] = new PeekableIterator[T](it)

  def apply[TInput, TOutput](it1:Iterator[TInput], getNext: PeekableIterator[TInput]=>TOutput ): PeekableIterator[TOutput] =
    val input = PeekableIterator[TInput](it1)
    PeekableIterator[TOutput](new Iterator[TOutput] {
      override def hasNext: Boolean = input.peek.isSuccess
      override def next(): TOutput = getNext(input)
    })

The second apply method takes an Iterator and a getNext function which will be used to dynamically create an iterator that will chain or wrap the first iterator. Its use is shown in the creation of the lexer for the parser.

    val lexer = PeekableIterator[Char,String](source, lazyLexer)

lazyLexer is the method that is used as the getNext() for the dynamically created iterator. It takes a Peekable[Char] as its parameter and returns a String

  // method used to do the actual tokenizing. It builds one token and returns
  private def lazyLexer(tokenizer: Peekable[Char]): String =
    // ignore the whitespace and look for an end of sentence
    while tokenizer.peek.isSuccess && (tokenizer.peek.get.isWhitespace || tokenizer.peek.get.isOtherPunctuation) do
      tokenizer.poll

    // Represent the End of Sentence as an empty String
    if tokenizer.peek.isSuccess && tokenizer.peek.get.isEndOfSentence then
      tokenizer.poll
      return ""

    // if we are at the end of input pass the failure on
    if tokenizer.peek.isFailure then
      throw tokenizer.peek.failed.get

    // build a word
    val sb = new StringBuilder()
    while tokenizer.peek.isSuccess && !(tokenizer.peek.get.isWhitespace || tokenizer.peek.get.isPunctuation) do
      sb.append(tokenizer.poll.get)

    // return the word
    sb.toString()
  end lazyLexer

Finally, the parser takes the words from the lexer and builds a Vector[Vector[String]] to represent a list of sentences. It is written to ignore empty sentences.

  def parse(source:Source):Vector[Vector[String]] =
    // create the lexer by chaining the source to the lazylexer
    var sentences:Vector[Vector[String]] = Vector.empty
    var sentence:Vector[String] = Vector.empty
    val lexer = PeekableIterator[Char,String](source, lazyLexer)

    while lexer.peek.isSuccess do
      if lexer.peek.get.isEmpty then
        // ignore empty sentences
        if sentence.nonEmpty then
          sentences = sentences :+ sentence
          sentence = Vector.empty
        end if
        lexer.poll
      else
        sentence = sentence :+ lexer.poll.get
      end if
    end while

    if sentence.nonEmpty then
      sentences = sentences :+ sentence
    end if

    sentences
  end parse

The code from this article can be found here: ll1-parser

Improving the Prime Iterator in Rust

David Berry — Mon, 26 Jun 2023 02:07:39 +0000

I wanted to improve the performance of the prime iterator I created back in 2021. The final code from part 1 was:

pub fn is_prime(n: u64) -> bool {
  if n < 4 {
    n > 1
  } else if n % 2 == 0 || n % 3 == 0 {
    false
  } else {
    let max_p = (n as f64).sqrt().ceil() as u64;
    match (5..=max_p).step_by(6).find(|p| n % p == 0 || n % (p+2) == 0) {
      Some(_) => false,
      None => true
    }
  }
}

pub struct Prime {
  curr: u64,
  next: u64,
  trial1: u64,
  trial2: u64
}

impl Prime {
  pub fn new() -> Prime {
    Prime {
      curr: 2,
      next: 3,
      trial1: 5,
      trial2: 7
    }
  }
}

impl Iterator for Prime {
  type Item = u64;

  fn next(&mut self) -> Option<Self::Item> {
    let prime = self.curr;
    self.curr = self.next;
    loop {
      self.next = self.trial1;
      self.trial1 = self.trial2;
      self.trial2 = self.next+6;
      if is_prime(self.next) {
        break;
      }
    }
    Some(prime)
  }
}

This algorithm operates in constant memory and uses the 6k ± 1 rule to generate the set of prime candidates. The area I would like to focus on is the is_prime function. is_prime needs to regenerate the list of primes each time to find out if the next prime candidate is prime or not. It will do this for each prime candidate tested. It would be faster if we memoize the generated primes so that we do not generate them over and over again. This will use more memory, but will perform faster.

Let's look at a version of the Iterator with memoization.

pub struct PrimeM {
  curr: u64,
  next: u64,
  trial1: u64,
  trial2: u64,
  primes: LinkedList<u64>
}

impl PrimeM {
  pub fn new() -> PrimeM {
    let mut prime_list = LinkedList::new();
    prime_list.push_back(2);
    prime_list.push_back(3);
    PrimeM {
      curr: 2,
      next: 3,
      trial1: 5,
      trial2: 7,
      primes: prime_list
    }
  }

  fn check_prime(&self, candidate:u64 ) -> bool {
    for p in &self.primes {
      let prime = *p;
      if prime*prime > candidate {
        return true;
      }
      if candidate%prime == 0 {
        return false;
      }
    }
    return true;
  }
}

impl Iterator for PrimeM {
  type Item = u64;

  fn next(&mut self) -> Option<Self::Item> {
    let prime = self.curr;
    self.curr = self.next;
    loop {
      self.next = self.trial1;
      self.trial1 = self.trial2;
      self.trial2 = self.next+6;
      if self.check_prime(self.next) {
        self.primes.push_back(self.next);
        break;
      }
    }
    Some(prime)
  }
}

There is now a linked list to store the generated primes. It is initialized with the first two primes 2 and 3. Each time the next prime is found it is stored in the linked list. A check_prime function has been added that loops through all the generated primes up to the square root of the candidate to see if the candidate is evenly divisible by the already generated primes. If it is not divisible then it is a prime number.

Here are the results of the two iterators generating 100000 primes:

The memoized version improved the performance of the iterator and runs in 29.47% of the time of the non-memoized version.

Full code can be found on GitHub

A Prime Iterator in rust

David Berry — Sun, 07 Nov 2021 19:46:38 +0000

Inspired by Alessio Saltarin's Primality Test in Scala, I thought that it would be interesting to implement the same primality test in rust and then use this test as a means to build an Iterator that lazily generates prime numbers.

The primality test is based on the fact that all primes greater than 3 are of the form 6k ± 1, where k is any integer greater than 0. The rust version of this algorithm is:

pub fn is_prime(n: u64) -> bool {
  if n < 4 {
    n > 1
  } else if n % 2 == 0 || n % 3 == 0 {
    false
  } else {
    let max_p = (n as f64).sqrt().ceil() as u64;
    match (5..=max_p).step_by(6).find(|p| n % p == 0 || n % (p+2) == 0) {
      Some(_) => false,
      None => true
    }
  }
}

is_prime first tests for n<4 and returns n>1. n=2 or n=3 will return true all other n<4 return false. The next test checks if n is an even multiple of 2 or 3. If it is, return false as n is not prime.

The final test checks to see if n is evenly divisible by any 6k ± 1 up to the square root of n. This is done by starting at 5 and checking if n is an even multiple of 5 or 5+2, 6-1 or 6+1 respectively. If it is an even multiple we will return false, if not we add 6 and test again. If no even multiple is found, n is prime and return true.

Many will point out that using sqrt() and ceil() are expensive, but I only use it once up front to get the upper bound for the comparison. This removes the need to square the 6k ± 1 in the test loop to determine when to break. It also allowed me to use the range (5..=max_p).step_by(6).find with the predicate |p| n % p == 0 || n % (p+2) == 0 to identify non-primes. I add that to a match statement to return false if a non-prime is identified and true if n is prime.

Now that we have a primality test we can construct the lazy prime Iterator in rust. The code for the Iterator is:

pub struct Prime {
  curr: u64,
  next: u64,
}

impl Prime {
  pub fn new() -> Prime {
    Prime {
      curr: 2,
      next: 3,
    }
  }
}

impl Iterator for Prime {
  type Item = u64;

  fn next(&mut self) -> Option<Self::Item> {
    let prime = self.curr;
    self.curr = self.next;
    loop {
      self.next += match self.next%6 {
        1 => 4,
        _ => 2,
      };
      if is_prime(self.next) {
        break;
      }
    }
    Some(prime)
  }
}

A new Prime starts off with curr=2 and next=3. This allowed me to ignore the special case of two primes being only one digit apart. The next function saves the prime in curr which it will return. It then moves next into curr and calculates a new next. It makes use of the fact that all primes greater than 3 are of the form 6k ± 1. So if the latest test prime is 6k-1 we add 2 to get the next possible prime. If the latest test prime is 6K+1 we add 4 to get the next possible prime. We accomplish this with p modulo 6, where p is the latest test prime. If p modulo 6 is 1 then we have a 6k+1 number and need to add 4 to get to the next test prime of 6k-1. If p modulo 6 is 5 or 3, then we add 2 to get to the next 6k+1 number. _ => 2 is the catch all that let's us catch the initial state of n=3 and any state where n=6k-1.

This iterator operates with constant memory and only generates one prime at a time, but it performs a modulo and match operation inside the loop. After some consideration, both the modulo and match can be removed from inside the loop. If we initialize the struct Prime with the first two primes and the first 6k ± 1 we only need to add 6 to get the next trial prime. The final Iterator is:

pub struct Prime {
  curr: u64,
  next: u64,
  trial1: u64,
  trial2: u64
}

impl Prime {
  pub fn new() -> Prime {
    Prime {
      curr: 2,
      next: 3,
      trial1: 5,
      trial2: 7
    }
  }
}

impl Iterator for Prime {
  type Item = u64;

  fn next(&mut self) -> Option<Self::Item> {
    let prime = self.curr;
    self.curr = self.next;
    loop {
      self.next = self.trial1;
      self.trial1 = self.trial2;
      self.trial2 = self.next+6;
      if is_prime(self.next) {
        break;
      }
    }
    Some(prime)
  }
}

Full code can be found on GitHub