dtonhofer

dtonhofer

Functional Programming in Java, Second Edition: p.135 code for "primes" using a self-modifying filter

This is no particular interest but here is some code that uses the “execute around” pattern to build a timer to time the “primes generator”, as well as a second primes generator that uses a self-modifying stream filter, a closure that accumulates all the primes found so far so as to perform divisibility testing, which is evidently faster than the “try to divide by every x between 2 and sqrt(n)”.

import org.junit.jupiter.api.Test;

import java.util.*;
import java.util.function.Predicate;
import java.util.function.Supplier;
import java.util.stream.IntStream;
import java.util.stream.Stream;

import static java.util.stream.Collectors.toList;
import static org.junit.jupiter.api.Assertions.assertEquals;

class SimpleTimer {

    public final long duration_ms;
    public final List<Integer> result;

    private SimpleTimer(List<Integer> result, long duration_ms) {
        this.result = Collections.unmodifiableList(result);
        this.duration_ms = duration_ms;
    }

    public static SimpleTimer timeIt(Supplier<List<Integer>> supplier) {
        long start = System.currentTimeMillis();
        List<Integer> result = supplier.get();
        long stop = System.currentTimeMillis();
        return new SimpleTimer(result, stop - start);
    }

}

class Primes {

    public static boolean isPrime(final int number) {
        return number > 1 &&
                IntStream.rangeClosed(2, (int) Math.sqrt(number))
                        .noneMatch(divisor -> number % divisor == 0);
    }

    private static int primeAfter(final int number) {
        if (isPrime(number + 1)) {
            return number + 1;
        }
        return primeAfter(number + 1);
    }

    public static List<Integer> primes(final int fromNumber, final int count) {
        return Stream.iterate(primeAfter(fromNumber - 1), Primes::primeAfter)
                .limit(count)
                .collect(toList());
    }

}

class PrimesSieveNoDoubles {

    private enum What {found_divisor, surpassed_sqrt, possibly_prime}

    // This is actually a little bit *slower* than a version that computes sqrt(x)
    // to determine whether to stop instead of using integer division to check whether
    // the dividend has become smaller than the divisor.

    public static List<Integer> primes(int limit) {
        final var store = new LinkedList<Integer>();
        Predicate<Integer> p = x -> {
            What what = What.possibly_prime;
            Iterator<Integer> iter = store.iterator();
            while (what == What.possibly_prime && iter.hasNext()) {
                int somePrime = iter.next();
                // it is faster to compute remainder and divisor next to one another always
                // than compute the divisor inside the "else", apparently due to compiler optimizations
                int remainder = x % somePrime;
                int dividend = x / somePrime;
                if (remainder == 0) {
                    // System.out.println(x + " = " + somePrime + "*n, not a prime");
                    what = What.found_divisor;
                } else {
                    // int divisor = x / somePrime;
                    if (dividend < somePrime) {
                        what = What.surpassed_sqrt;
                    }
                }
            }
            if (what == What.surpassed_sqrt || what == What.possibly_prime) {
                // System.out.println(x + " is prime");
                store.addLast(x);
                return true;
            } else {
                return false;
            }
        };
        List<Integer> result = Stream.iterate(2, x -> x + 1).
                filter(p).
                limit(limit).
                collect(toList());
        // add the end of the collect, the result and the store have the same content
        // this comparison takes a few ms
        assertEquals(store,result);
        return result;
    }

}

public class Primality {

    private final static int limit = 1_000_000;

    @Test
    void runBookPrimes() {
        List<Integer> l1 = Primes.primes(1, 10);
        List<Integer> l2 = Primes.primes(100, 5);
        assertEquals(List.of(2, 3, 5, 7, 11, 13, 17, 19, 23, 29),l1);
        assertEquals(List.of(101, 103, 107, 109, 113),l2);
        System.out.println("10 primes from 1: " + l1);
        System.out.println("5 primes from 100: " + l2);
    }

    @Test
    void runBookPrimesWithTimer() {
        // not an actual test, just printout
        final SimpleTimer timeIt = SimpleTimer.timeIt(() -> Primes.primes(2, limit));
        final List<Integer> result = timeIt.result;
        final String range = (result.isEmpty()) ? "" : "in range [" + result.get(0) + "," + result.get(result.size() - 1) + "] ";
        System.out.println("Using book code: finding " + result.size() + " primes " + range + "took " + timeIt.duration_ms + " ms");
    }

    @Test
    void runPrimesSieveWithTimer() {
        // not an actual test, just printout
        final SimpleTimer timeIt = SimpleTimer.timeIt(() -> PrimesSieveNoDoubles.primes(limit));
        final List<Integer> result = timeIt.result;
        final String range = (result.isEmpty()) ? "" : "in range [" + result.get(0) + "," + result.get(result.size() - 1) + "] ";
        System.out.println("Using primes sieve w/o doubles: finding " + result.size() + " primes " + range + "took " + timeIt.duration_ms + " ms");
    }
}

Where Next?

Popular Pragmatic Bookshelf topics Top

jeffmcompsci
Title: Design and Build Great Web APIs - typo “https://company-atk.herokuapp.com/2258ie4t68jv” (page 19, third bullet in URL list) Typo:...
New
ianwillie
Hello Brian, I have some problems with running the code in your book. I like the style of the book very much and I have learnt a lot as...
New
lirux
Hi Jamis, I think there’s an issue with a test on chapter 6. I own the ebook, version P1.0 Feb. 2019. This test doesn’t pass for me: ...
New
AleksandrKudashkin
On the page xv there is an instruction to run bin/setup from the main folder. I downloaded the source code today (12/03/21) and can’t see...
New
Chrichton
Dear Sophie. I tried to do the “Authorization” exercise and have two questions: When trying to plug in an email-service, I found the ...
New
brian-m-ops
#book-python-testing-with-pytest-second-edition Hi. Thanks for writing the book. I am just learning so this might just of been an issue ...
New
fynn
This is as much a suggestion as a question, as a note for others. Locally the SGP30 wasn’t available, so I ordered a SGP40. On page 53, ...
New
akraut
The markup used to display the uploaded image results in a Phoenix.LiveView.HTMLTokenizer.ParseError error. lib/pento_web/live/product_l...
New
jwandekoken
Book: Programming Phoenix LiveView, page 142 (157/378), file lib/pento_web/live/product_live/form_component.ex, in the function below: d...
New
tkhobbes
After some hassle, I was able to finally run bin/setup, now I have started the rails server but I get this error message right when I vis...
New

Other popular topics Top

siddhant3030
I’m thinking of buying a monitor that I can rotate to use as a vertical monitor? Also, I want to know if someone is using it for program...
New
dasdom
No chair. I have a standing desk. This post was split into a dedicated thread from our thread about chairs :slight_smile:
New
AstonJ
We have a thread about the keyboards we have, but what about nice keyboards we come across that we want? If you have seen any that look n...
New
AstonJ
This looks like a stunning keycap set :orange_heart: A LEGENDARY KEYBOARD LIVES ON When you bought an Apple Macintosh computer in the e...
New
PragmaticBookshelf
Build highly interactive applications without ever leaving Elixir, the way the experts do. Let LiveView take care of performance, scalabi...
New
mafinar
Crystal recently reached version 1. I had been following it for awhile but never got to really learn it. Most languages I picked up out o...
New
rustkas
Intensively researching Erlang books and additional resources on it, I have found that the topic of using Regular Expressions is either c...
New
Maartz
Hi folks, I don’t know if I saw this here but, here’s a new programming language, called Roc Reminds me a bit of Elm and thus Haskell. ...
New
New
AstonJ
Curious what kind of results others are getting, I think actually prefer the 7B model to the 32B model, not only is it faster but the qua...
New

Latest in Functional Programming in Java, Second Edition

Functional Programming in Java, Second Edition Portal

Sub Categories: