Reducing a large stream without stack overflowing

Question

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.reduceRight(LinearSeqOptimized.scala:131)
    at scala.collection.immutable.Stream.reduceRight(Stream.scala:47)
    at scala.collection.LinearSeqOptimized$class.reduceRight(LinearSeqOptimized.scala:131)
    at scala.collection.immutable.Stream.reduceRight(Stream.scala:47)
    ...

It's obvious that reduceRight is calling itself like this

reduceRight(reduceRight(first, second, op), third, op)...

And thus the stack overflow. I assume it's not tail-call optimized because it first reduces and then operates prior to returning the value, so it can't be optimized. How could I approach this problem then? Should I ditch the functional approach and aim for custom imperative-style code for reducing?

What strikes me as a very odd thing is that the (BigInt(1) to n).reduceRight(_*_) does not overflow for large n while almost the same using a stream does... What's going on here?

score 8 · Answer 1 · edited May 23 '17 at 10:31

8

You are correct that your first solution will create a list in memory to store the reversed sequence. You could simply use reduceLeft (which doesn't have that problem on ranges), but that will pass through the range in the opposite direction. If for some reason you want to start at the large end but keep the laziness of reduceLeft, you can create a backwards Range:

def fact(n: Int) = (BigInt(n) to 1 by -1).reduceLeft(_ * _)

There may be other ways you can easily optimize this function.

edited May 23 '17 at 10:31

Community

1
1

answered Apr 19 '12 at 14:58

Travis Brown

138,631
12
375
680

Great ideas for optimization. Thanks! – kaoD Apr 19 '12 at 15:08
2

You have the order backwards. In-order is faster than reverse-order, and `foldLeft` does it in the order you ask for. – Rex Kerr Apr 19 '12 at 15:34
@Rex: actually, if the cost of `BigInt` multiplication is proportional to the product of the number of digits of the two numbers, then neither direction has an advantage, right? In any case I've edited the answer to make this a non-issue. – Travis Brown Apr 19 '12 at 16:07
@TravisBrown In my very limited testing, the direction you're proposing is about 30% slower than the reverse (increasing) direction. – Jean-Philippe Pellet Apr 19 '12 at 16:17
@Travis - You were right the first time about the performance; you were just wrong about the evaluation order. For example: 2*2*2*1000 has cost 1+1+4 in forward order and 4+4+4 in reverse order, using your metric. – Rex Kerr Apr 19 '12 at 16:59

Rex Kerr · Accepted Answer · 2012-04-19T15:03:24.753

7

reduceLeft is implemented to compute as it goes on streams (and it calls in order). You can verify as follows:

Stream.range(1,10).map(i => print(i)).reduceLeft((a,b) => println("r"))

Or you can use tail recursion:

final def fac(n: BigInt, prod: BigInt = BigInt(1)): BigInt = {
  if (n<2) prod else fac(n-1,prod*n)
}

(as Travis points out, it'd be faster to multiply the small numbers first, which would take an extra line).

edited Apr 19 '12 at 15:03

answered Apr 19 '12 at 14:53

Rex Kerr

166,841
26
322
407

See my comment in the other answer (applies here too.) Also: I'd like to avoid the common factorial implementation using TCR since this is meant as an exercise for using lazy ranges. – kaoD Apr 19 '12 at 14:58
@kaoD - It doesn't need the range and doesn't start from the last element. See example (paste into REPL). – Rex Kerr Apr 19 '12 at 15:03

score 4 · Answer 3 · answered Apr 19 '12 at 14:53

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 Apr 19 '12 at 14:53

Jean-Philippe Pellet

59,296
21
173
234

Thought of that too but, wouldn't it need the whole `Range` to begin with? IIRC, `reduceLeft` starts from the last element, but the whole `Range` has to be computed for the last element to exist (which is actually what I don't want to.) – kaoD Apr 19 '12 at 14:56
1

`reduceLeft` starts on the left part, so at the first element, like `foldLeft`. – Jean-Philippe Pellet Apr 19 '12 at 15:02
Yep, I was just looking at `TraversableOnce` and saw it. I mistakenly took `Right` as direction of evaluation, not beginning of it. Thanks! – kaoD Apr 19 '12 at 15:04
2

BTW, this works faster for me: `Stream.range(BigInt(1), BigInt(n)).par.reduce(_*_)`. – Jean-Philippe Pellet Apr 19 '12 at 15:08

score 1 · Answer 4 · answered Apr 19 '12 at 15:05

1

def fac (n: BigInt=1, m:BigInt=1): Stream[BigInt] = 
  Stream.cons (n, fac (n * m, m+1))

fac().take (10).toList
res27: List[BigInt] = List(1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880)

works well with take(10000).toList too.

answered Apr 19 '12 at 15:05

user unknown

35,537
11
75
121

1

Define this as a val and it'd take a lot less to compute (see http://stackoverflow.com/questions/8659127/how-to-fix-my-fibonacci-stream-in-scala) – kaoD Apr 20 '12 at 00:29

Reducing a large stream without stack overflowing

4 Answers4