Alex Rivera | Logout

Reducing a large stream without stack overflowing

Asked 2012-04-19T14:40:47.867
9

1I'm trying to make a limit-less factorial function (just out of curiosity.) This works for large n (tried up to 100000 and it seems to work, although I can't check the output value for correctness because, well, it's LARGE!)

(BigInt(1) to n).reduceRight(_*_)

But I'm afraid that the whole BigInt(1) to n range might be in memory, while I just need it element by element for reduceRight. Taking a look at Scala's standard library code it looks like BigInt(1) to n actually outputs the whole Range and not a lazy Stream but I found Stream.range which I can use like this (notice the n+1, stream range is exclusive)

Stream.range[BigInt](BigInt(1), BigInt(n+1)).reduceRight(_*_)

It works for n=10000 (for some reason it takes a little bit longer! which makes me think that maybe the normal range is actually a Stream too?) but for n=100000 I get this stack overflow

java.lang.StackOverflowError
    at java.math.BigInteger.add(Unknown Source)
    at scala.math.BigInt.$plus(BigInt.scala:161)
    at scala.math.Numeric$BigIntIsIntegral$class.plus(Numeric.scala:28)
    at scala.math.Numeric$BigIntIsIntegral$.plus(Numeric.scala:40)
    at scala.math.Numeric$BigIntIsIntegral$.plus(Numeric.scala:40)
    at scala.math.Numeric$Ops.$plus(Numeric.scala:208)
    at scala.collection.immutable.Stream$$anonfun$range$1.apply(Stream.scala:695)
    at scala.collection.immutable.Stream$$anonfun$range$1.apply(Stream.scala:695)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:634)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:626)
    at scala.collection.LinearSeqOptimized$class.reduceRight(LinearSeqOptimized.scala:130)
    at scala.collection.immutable.Stream.reduceRight(Stream.scala:47)
    at scala.collection.LinearSeqOptimized$class.reduceRi
Edit
Report

1 Answer

4

Try using reduceLeft instead. reduceRight starts from the end of the stream and thus forces every element to be evaluated — exactly what you wanted to avoid.

answered 2012-04-19T14:53:18.830

Your Answer