Details

Type: Bug

Status: Closed

Priority: Major

Resolution: Fixed

Affects Version/s: Scala 2.8.0, Scala 2.8.1, Scala 2.9.0, Scala 2.9.1

Fix Version/s: Scala 2.10.0

Component/s: Misc Library

Labels:

Environment:
Scala version 2.10.0.r25021b20110525020223 (OpenJDK 64Bit Server VM, Java 1.6.0_22)
Description
Range doesn't provide a sensible implementation, but uses this one from TraversableOnce:
def sum[B >: A](implicit num: Numeric[B]): B = foldLeft(num.zero)(num.plus)
This is probably the worst case algorithm.
It is possible to provide an algorithm taking constant time for at least step size 1 and probably every other step size, too.
I just written a quickanddirty implementation covering step size 1:
final def sum: Int = { var _end = if (isInclusive) end else end1 if (step == 1) if(start >= 0) gauss(start1) + gauss(_end) else gauss(start) + gauss(_end) else sum() } @inline private def gauss(end: Int) = (end+1)*end/2
NumericRange has the same problem. The same algorithm applies, but with Numeric[T] instead of Int as a type.
Issue Links
 relates to

SI4958 Parallel sum produces different result from sequential sum
 Closed
Just Benchmarked it:
*One* run takes ~ 35 seconds.