Calculus via Lambdas in Java 8

A quick glimpse at a Java 8 implementation for taking derivatives of functions using functional interfaces and lambda expressions.

Read More

Stream-Based Linear Congruential Generator in Java 8

A while ago, I wrote a post on a Stream-Based Linear Congruential Generator in Scala. This post is a similar implementation using the Java 8 Stream API.

Here is a Java 8 stream-based implementation of a pseudo-random number generator using a linear congruential generator (LCG):

package com.michaelcotterell.util;


public class Random {

    private final long a;    // multiplier
    private final long c;    // increment
    private final long m;    // modulus
    private final long seed; // start value
    private final LongStream stream;
    public Random(long a, long c, long m, long seed) {
        this.a      = a;
        this.c      = c;
        this.m      = m;
        this.seed   = seed % m; = LongStream.iterate(this.seed, x -> (a * x + c) % m);
    } // Random
    public Random(long a, long c, long m) {
        this(a, c, m, System.currentTimeMillis());
    } // Random
    public LongStream longs() {
        return -> e);
    } // longs
    public IntStream ints() {
        return stream.mapToInt(e -> (int) (e % (Integer.MAX_VALUE + 1L)));
    } // ints
    public DoubleStream doubles() {
        final double ONE_OVER_M = 1.0 / m;
        return stream.mapToDouble(e -> e * ONE_OVER_M);
    } // doubles
} // Random

To use this class, you might do something like the following:

Random lcg = new Random(48271, 0, (2L << 31) - 1, System.currentTimeMillis());
Iterator<Double> rand = lcg.doubles().iterator();

for (int i = 0; i < 10; ++i) System.out.println(; 

To test different LCGs, you might do the following:

long iters = 100_000;
long seed  = System.currentTimeMillis();

Random[] lcgs = new Random[] {
    new Random(48271, 0, (2L << 31) - 1, seed), // MINSTD (updated)
    new Random(16807, 0, (2L << 31) - 1, seed), // MINSTD (old)
    new Random(65539, 0, (2L << 31),     seed)  // RANDU

for (Random lcg : lcgs) {
} // for

Purely Tail Recursive k-th Smallest Element

Finding the k-th smallest (or largest) element of an unordered array is a problem that's been approached by many programmers and computer scientists. There are many methods for solving this problem. To me, one of the more interesting implementations is a purely tail recursive implementation that uses the partition algorithm.

A purely tail recursive function or method is one in which there are no deferred operations. A deferred operation in this case, is one that must wait until a recursive call returns before it can complete. This article goes into this a little detail about the differences between "ordinary" and "pure" tail recursive methods.

Given a function that can swap two elements of an array and the partition function, it is possible to find the k-th smallest element of an array of distinct integers using the following purely tail recursive implementation (the accumulator parameters act in a fashion that is similar to a binary search):

private static int kthMin(int[] a, int left, int right, int k) {
  int newPivot = partition(a, left, right, k - 1);
  if (newPivot == k - 1) return a[k - 1];
  if (newPivot < k - 1) left = newPivot + 1;
  if (newPivot > k - 1) right = newPivot - 1;
  return kthMin(a, left, right, k);
} // kthMin

If you have any questions, then please post them in the comments.