Testing whether an ordered infinite stream contains a value

Question

I have an infinite primeStream prime primeStream (starting at 2 and increasing). I also have another Ints s thread that is increasing in size and I want to check if each of them is simple.

What is an effective way to do this? I could identify

 def isPrime(n: Int) = n == primeStream.dropWhile(_ < n).head 

but this seems inefficient, as he needs to iterate over the entire stream each time.

primeStream implementation (shamelessly copied from other sources):

  val primeStream: Stream[Int] = 2 #:: primeStream.map{ i => Stream.from(i + 1) .find{ j => primeStream.takeWhile{ k => k * k <= j } .forall{ j % _ > 0 } }.get } 

Answer 1

If we are talking about implementing isPrime, then you should do as rossum suggested, even if the separation cost is more than the equality test, and with denser values ​​for lower values ​​of n it will be asymptotically much faster. Moreover, it is very fast when testing non-prime numbers that have a small divisor (most numbers have)

It could be different if you want to test the primitiveness of the elements of another ascending stream. You might consider something like merge sorting. You did not specify how you want to get your result, here as a stream of Booleans, but it is not too difficult to adapt to something else.

 /** * Returns a stream of boolean, whether element at the corresponding position * in xs belongs in ys. xs and ys must both be increasing streams. */ def belong[A: Ordering](xs: Stream[A], ys: Stream[A]): Stream[Boolean] = { if (xs.isEmpty) Stream.empty else if (ys.isEmpty) xs.map(_ => true) else Ordering[A].compare(xs.head, ys.head) match { case less if less < 0 => false #:: belong(xs.tail, ys) case equal if equal == 0 => true #:: belong(xs.tail, ys.tail) case greater if greater > 0 => belong(xs, ys.tail) } } 

So you can do belong(yourStream, primeStream)

However, it is not obvious that this solution will be better than a separate primitiveness test for each number, in turn, stopping at the square root. Especially if your thread is growing fast compared to primes, so you just need to compute a lot of primes just to keep up. And even to a lesser extent, if there is no reason to suspect that the elements in your stream are usually simple or have only large divisors.

Answer 2

• You only need to read your main thread before sqrt(s) .
• When you extract each p from a simple stream, check to see if p divides s evenly.

This will give you a trial division method for the initial verification.

Answer 3

To solve the general question of whether a finite leaf list consists entirely of an element of an ordered but infinite stream:

The easiest way -

 candidate.toSet subsetOf infiniteList.takeWhile( _ <= candidate.last).toSet 

but if the candidate is large, this requires a lot of space, and O (n log n) instead of O (n), as it could be. Method O (n) -

 def acontains(a : Int, b : Iterator[Int]) : Boolean = { while (b hasNext) { val c = b.next if (c == a) { return true } if (c > a) { return false } } return false } def scontains(candidate: List[Int], infiniteList: Stream[Int]) : Boolean = { val it = candidate.iterator val il = infiniteList.iterator while (it.hasNext) { if (!acontains(it.next, il)) { return false } } return true } 

(By the way, if some helpful soul could suggest a more Scalicious way to write the above, I would appreciate it.)

EDIT:

In the comments, the invaluable Luigi Pling indicated that I can simply write:

 def scontains(candidate: List[Int], infiniteStream: Stream[Int]) = { val it = infiniteStream.iterator candidate.forall(i => it.dropWhile(_ < i).next == i) }