CODEWITHSUNDEEP
scalafibonacci
Cory Klein
Cory Klein

Reputation: 55690

Make this fibonacci stream stop before it overflows

The Scala docs present this Fibonacci definition using Streams

def fibFrom(a: Int, b: Int): Stream[Int] = a #:: fibFrom(b, a + b)

Unfortunately, this overflows Int around the 47th number

scala> fibFrom(1,1).take(47).toList
res5: List[Int] = List(1, 1, 2, 3, /* snip */, 1836311903, -1323752223)

How would I change fibsFrom to end when a.toLong + b.toLong > Int.MaxValue such that:

scala> fibsFrom(1,1).take(9999999).toList
res6: List[Int] = List(1, 1, 2, 3, /* snip */, 1836311903)

I tried the following, but it behaves identically to the original fibFrom

def fibFromSafe(a: Int, b: Int): Stream[Int] = {
  if(a.toLong + b.toLong > Int.MaxValue) Stream.cons(a, Stream.cons(b, Stream.empty))
  else Stream.cons(a, fibFromSafe(b, a + b))
}

Upvotes: 1

Views: 117

Answers (2)

LRLucena
LRLucena

Reputation: 1705

I just changed the original definition of fibFrom. If b is negative the function stops searching for more numbers and returns an empty stream.

  def fibFromSafe(a: Int = 1, b: Int = 1): Stream[Int] = {
    a #:: (if (b > 0) fibFromSafe(b, a + b) else Stream.empty)
  }

  fibFromSafe().take(100).toList

Edit:

If you don't want to check for overflows you can stop when a > 3/5 of Int.MaxInt. 

def fibFromSafe(a: Int = 1, b: Int = 1): Stream[Int] = {
  a #:: (if (a < Int.MaxValue/5*3) fibFromSafe(b, a + b) else Stream.empty)
}

Upvotes: 1

wingedsubmariner
wingedsubmariner

Reputation: 13667

You have a typo, fibFromSafe calls your original fibFrom.

Upvotes: 2

Related Questions