Postponed Prime Sequence in Kotlin

Question

Following my previous unbounded prime generator and a followup by Martin R, I've tested the waters in Kotlin by making an unbounded sieve.

To quote Martin R's wonderful explanation of the base algorithm,

The interesting thing about that algorithm is that the prime generator needs a list of "base primes" which are created using another instance of itself. This works because

• the base prime generator is created "delayed", after producing some fixed primes, and
• in order to generate primes up to \$ N \$, base primes are needed only up to \$ \sqrt N \$

so that the creation of nested prime generators terminates eventually.

The sieving is done using a dictionary which holds the "next composite numbers" which are divisible by any prime less than the current base prime. As explained [on SO], the required memory to produce \$ n \$ primes is \$ O(\sqrt n). \$

class PostponedPrimeSequence() : AbstractIterator<Int>(), Sequence<Int> {
    override fun iterator() = this

    private var basePrimes: PostponedPrimeSequence? = null
    private var basePrime = 0

    private var sieve = mutableMapOf<Int, Int>()
    private var initialPrimes = mutableListOf(2, 3, 5, 7)
    private var candidate = 9

    override fun computeNext() {
        if (!initialPrimes.isEmpty()) {
            setNext(initialPrimes.removeAt(0))
        } else {
            if (candidate == 9) {
                basePrimes = PostponedPrimeSequence()
                basePrimes!!.next()
                basePrime = basePrimes!!.next()
                assert(candidate == basePrime * basePrime)
            }

            while (candidate > 0) {
                val factor = sieve.remove(candidate) ?:
                        if (candidate == basePrime * basePrime) {
                            val temp = basePrime
                            basePrime = basePrimes!!.next()
                            temp
                        } else {
                            assert(candidate < basePrime * basePrime)
                            setNext(candidate)
                            break
                        }
                var j = candidate + 2 * factor
                while (sieve.containsKey(j)) {
                    j += 2 * factor
                }
                sieve[j] = factor
                candidate += 2
            }
            candidate += 2
        }
    }
}

Usage:

PostponedPrimeSequence().take(20).forEach(::println)

All feedback welcome, though reviews are encouraged to look at:

• Naming: As I'm new to Kotlin, I don't know the naming conventions yet
• Performance: If there are simple, provable improvements without drastically changing the algorithm (such as adding a large wheel)
• Iteration organization: As Kotlin lacks a true yielding generator and I wanted a true Iterator/Sequence, rather than a callback based "poor man's yield", the iteration isn't exactly the prettiest matter. The candidate += 2 } candidate += 2 bit especially feels like there should be a better way to do this, and the break (which is related) breaks ^_ha simple control flow, which is not ideal.
• !!: Even on the line immediately following assignment to basePrimes, I have to use !! to potentially fail on accessing the next method (Smart cast to 'PostponedPrimeSequence' is impossible, because 'basePrimes' is a mutable property that could have been changed by this time). I know that, due to reflection, any variable on the JVM could change at any time, but this seems like a smelly smell that smells smelly. basePrimes has to be mutable and start out null, though, because otherwise the class would recursively take infinite space. In this case, though, I want to initialize it once, late, and from then on it should act as an immutable (non-nullable) val reference. If this is possible in Kotlin, I don't know how to do so yet.

Answer 1

1. You can make basePrimes a lateinit non-null var to avoid !!.
2. sieve and initialPrimes are only assigned once so they can be marked with val instead of var
3. sequenceOf(2, 3, 4, 7).iterator() can be used along with Iterator.hasNext and Iterator.next instead of mutableListOf(2, 3, 5, 7) with somewhat difficult to read !initialPrimes.isEmpty() and initialPrimes.removeAt(0) (although if you really prefer to use a collection instead of an iterator then you can use isNotEmpty instead of !collection.isEmpty).
4. Instead of explicitly declaring a temp variable you can use apply to take the current value of a variable, use/change it, and return the initial value.
5. As an alternative to sieve.containsKey(j) you can use j in sieve.
6. As an alternative to candidate += 2 } candidate += 2 you can move the latter += 2 to relatively the beginning of computeNext (requires a few other changes, see below). The name candidate would no longer really fit though, but I think a generic property name like value is sufficient enough (we know what "value" we care about so we know what we're computing as we go, etc.).
7. You probably shouldn't implement Iterator<Int> and Sequence<Int> in the same object. e.g. When invoking with(PostponedPrimeSequence()) { repeat(2) { take(20).forEach(::println) } } I would expect it as a Sequence<Int> to print the first 20 primes twice (or throw "IllegalStateException: This sequence can be consumed only once.") but as an Iterator<Int> I would expect it to print the first 40 primes. These are conflicting expectations. I recommend only implementing one. A Sequence is understood to possibly be constrained to be iterated only once so I would implement the base Iterator and then wrap it as a Sequence in a top-level function for convenience.

e.g.

fun generatePrimeSequence() = PostponedPrimeIterator().asSequence()

class PostponedPrimeIterator() : AbstractIterator<Int>() {
    private lateinit var basePrimes: PostponedPrimeIterator
    private var basePrime = 0

    private val sieve = mutableMapOf<Int, Int>()
    private val initialPrimes = sequenceOf(2, 3, 5, 7).iterator()
    private var value = 0

    override fun computeNext() {
        if (initialPrimes.hasNext()) {
            value = initialPrimes.next()
            setNext(value)
        } else {
            value += 2

            if (value == 9) {
                basePrimes = PostponedPrimeIterator()
                basePrimes.next()
                basePrime = basePrimes.next()
                assert(value == basePrime * basePrime)
            }

            while (value > 0) {
                val factor = sieve.remove(value) ?:
                        if (value == basePrime * basePrime) {
                            basePrime.apply {
                                basePrime = basePrimes.next()
                            }
                        } else {
                            assert(value < basePrime * basePrime)
                            setNext(value)
                            break
                        }
                var j = value + 2 * factor
                while (j in sieve) {
                    j += 2 * factor
                }
                sieve[j] = factor
                value += 2
            }
        }
    }
}

Usage:

generatePrimeSequence().take(20).forEach(::println)

Answer 2

I just compared two solution suggested above in term of performance:

    println("PostponedPrimeSequence: ${measureTimeMillis { PostponedPrimeSequence().take(10000).sum().let(::println) }}")
    println("generatePrimeSequence: ${measureTimeMillis { generatePrimeSequence().take(10000).sum().let(::println) }}")

I've been surprised that performance diffs about 2 times:

496165411
PostponedPrimeSequence: 23
496165411
generatePrimeSequence: 48