Testing whether an ordered infinite stream contains a value

Question

I have an infinite Stream of primes primeStream (starting at 2 and increasing). I also have another stream of Ints s which increase in magnitude and I want to test whether each of these is prime.

What is an efficient way to do this? I could define

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

but this seems inefficient since it needs to iterate over the whole stream each time.

Implementation of primeStream (shamelessly copied from elsewhere):

  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 the question is about implementing isPrime, then you should do as suggested by rossum, even with division costing more than equality test, and with primes being more dense for lower values of n, it would be asymptotically much faster. Moreover, it is very fast when testing non primes which have a small divisor (most numbers have)

It may be different if you want to test primality of elements of another increasing Stream. You may consider something akin to a merge sort. You did not state how you want to get your result, here as a stream of Boolean, but it should not be too hard 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 may do belong(yourStream, primeStream)

Yet it is not obvious that this solution will be better than a separate testing of primality for each number in turn, stopping at square root. Especially if yourStream is fast increasing compared to primes, so you have to compute many primes in vain, just to keep up. And even less so if there is no reason to suspect that elements in yourStream tend to be primes or have only large divisors.

Answer 2

1. You only need to read your prime stream as far as sqrt(s).
2. As you retrieve each p from the prime stream check if p evenly divides s.

This will give you a trial division method of prime checking.

Answer 3

To solve the general question of determining whether an ordered finite list consisted entirely of element of an ordered but infinite stream:

The simplest way is

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

but if the candidate is large, that requires a lot of space and it is O(n log n) instead O(n) like it could be. The O(n) way is

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
}

(Incidentally, if some helpful soul could propose a more Scalicious way to write the foregoing, I'd appreciate it.)

EDIT:

In the comments, the inestimable Luigi Plinge pointed out that I could just write:

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