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

iPaul
page 37 ANTLRInputStream input = new ANTLRInputStream(is); as of ANTLR 4 .8 should be: CharStream stream = CharStreams.fromStream(i...
New
telemachus
Python Testing With Pytest - Chapter 2, warnings for “unregistered custom marks” While running the smoke tests in Chapter 2, I get these...
New
JohnS
I can’t setup the Rails source code. This happens in a working directory containing multiple (postgres) Rails apps. With: ruby-3.0.0 s...
New
leonW
I ran this command after installing the sample application: $ cards add do something --owner Brian And got a file not found error: Fil...
New
jskubick
I’m running Android Studio “Arctic Fox” 2020.3.1 Patch 2, and I’m embarrassed to admit that I only made it to page 8 before running into ...
New
jskubick
I’m under the impression that when the reader gets to page 136 (“View Data with the Database Inspector”), the code SHOULD be able to buil...
New
taguniversalmachine
Hi, I am getting an error I cannot figure out on my test. I have what I think is the exact code from the book, other than I changed “us...
New
Henrai
Hi, I’m working on the Chapter 8 of the book. After I add add the point_offset, I’m still able to see acne: In the image above, I re...
New
SlowburnAZ
Getting an error when installing the dependencies at the start of this chapter: could not compile dependency :exla, "mix compile" failed...
New
dachristenson
@mfazio23 Android Studio will not accept anything I do when trying to use the Transformations class, as described on pp. 140-141. Googl...
New

Other popular topics Top

ohm
Which, if any, games do you play? On what platform? I just bought (and completed) Minecraft Dungeons for my Nintendo Switch. Other than ...
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
PragmaticBookshelf
Design and develop sophisticated 2D games that are as much fun to make as they are to play. From particle effects and pathfinding to soci...
New
AstonJ
You might be thinking we should just ask who’s not using VSCode :joy: however there are some new additions in the space that might give V...
New
DevotionGeo
The V Programming Language Simple language for building maintainable programs V is already mentioned couple of times in the forum, but I...
New
AstonJ
If you get Can't find emacs in your PATH when trying to install Doom Emacs on your Mac you… just… need to install Emacs first! :lol: bre...
New
PragmaticBookshelf
Author Spotlight Jamis Buck @jamis This month, we have the pleasure of spotlighting author Jamis Buck, who has written Mazes for Prog...
New
New
DevotionGeo
I have always used antique keyboards like Cherry MX 1800 or Cherry MX 8100 and almost always have modified the switches in some way, like...
New
mindriot
Ok, well here are some thoughts and opinions on some of the ergonomic keyboards I have, I guess like mini review of each that I use enoug...
New

Latest in Functional Programming in Java, Second Edition

Functional Programming in Java, Second Edition Portal

Sub Categories: