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

belgoros
Following the steps described in Chapter 6 of the book, I’m stuck with running the migration as described on page 84: bundle exec sequel...
New
sdmoralesma
Title: Web Development with Clojure, Third Edition - migrations/create not working: p159 When I execute the command: user=&gt; (create-...
New
simonpeter
When I try the command to create a pair of migration files I get an error. user=&gt; (create-migration "guestbook") Execution error (Ill...
New
Mmm
Hi, build fails on: bracket-lib = “~0.8.1” when running on Mac Mini M1 Rust version 1.5.0: Compiling winit v0.22.2 error[E0308]: mi...
New
jskubick
I think I might have found a problem involving SwitchCompat, thumbTint, and trackTint. As entered, the SwitchCompat changes color to hol...
New
hgkjshegfskef
The test is as follows: Scenario: Intersecting a scaled sphere with a ray Given r ← ray(point(0, 0, -5), vector(0, 0, 1)) And s ← sphere...
New
jskubick
I found an issue in Chapter 7 regarding android:backgroundTint vs app:backgroundTint. How to replicate: load chapter-7 from zipfile i...
New
jonmac
The allprojects block listed on page 245 produces the following error when syncing gradle: “org.gradle.api.GradleScriptException: A prob...
New
a.zampa
@mfazio23 I’m following the indications of the book and arriver ad chapter 10, but the app cannot be compiled due to an error in the Bas...
New
dachristenson
I’ve got to the end of Ch. 11, and the app runs, with all tabs displaying what they should – at first. After switching around between St...
New

Other popular topics Top

DevotionGeo
I know that these benchmarks might not be the exact picture of real-world scenario, but still I expect a Rust web framework performing a ...
New
Exadra37
Please tell us what is your preferred monitor setup for programming(not gaming) and why you have chosen it. Does your monitor have eye p...
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
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
PragmaticBookshelf
Rust is an exciting new programming language combining the power of C with memory safety, fearless concurrency, and productivity boosters...
New
PragmaticBookshelf
Author Spotlight: VM Brasseur @vmbrasseur We have a treat for you today! We turn the spotlight onto Open Source as we sit down with V...
New
PragmaticBookshelf
Programming Ruby is the most complete book on Ruby, covering both the language itself and the standard library as well as commonly used t...
New
PragmaticBookshelf
Build modern server-driven web applications using htmx. Whatever programming language you use, you’ll write less (and cleaner) code. ...
New
sir.laksmana_wenk
I’m able to do the “artistic” part of game-development; character designing/modeling, music, environment modeling, etc. However, I don’t...
New
PragmaticBookshelf
Fight complexity and reclaim the original spirit of agility by learning to simplify how you develop software. The result: a more humane a...
New

Latest in Functional Programming in Java, Second Edition

Functional Programming in Java, Second Edition Portal

Sub Categories: