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.

• mfulton26: StackExchange also supports lang-kotlin.
• CAD97: @mfulton26 Does it, though? If I read that right, it should be falling back to default when using lang-kotlin. It seems to do just as well, though, so I'll switch. (The biggest hint is fun is not highlighted as a keyword.)
• mfulton26: Ha. That's funny, I figured it wasn't fully implemented, buggy, etc. You're probably right but I've always used lang-kotlin just the same.
• Will Ness: a side note: if N is x repetedly squared k times, then N = x**(2**k) so that log(log N) = log( (2**k)*log x) = k*log 2 + log(log x) so the height of that "tower" of "nested primes generators" is k = O(log (log N)). IOW that recursion that "terminates eventually" actually does so in O(log log N) steps. An interesting tidbit.

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

• CAD97: As always, benchmarking the JVM is troublesome. Make sure that you aren't accidentally measuring startup time. It'd also be more fair to compare PostponedPrimeIterator() to my PostponedPrimeSequence() due to the requirement of the asSequence wrapper.
• CAD97: Answers should be able to stand on their own. As is, this answer is dependent on another to be of any use and could be voted Not An Answer because of that. I'd suggest fleshing out your answer to avoid that. A demonstration of performance deltas could potentially stand on its own if you successfully demonstrate that you are measuring what you purport to be measuring, and it isn't overshadowed by overhead.
• greybeard: (If and where you refer to another post or comment, please plant a link for disambiguation. You can find one for posts as share immediately underneath. For a comment, find it "below the date".)