diff options
Diffstat (limited to 'src/library')
4 files changed, 77 insertions, 46 deletions
diff --git a/src/library/scala/collection/immutable/NumericRange.scala b/src/library/scala/collection/immutable/NumericRange.scala index 28e56a6d87..11603a118b 100644 --- a/src/library/scala/collection/immutable/NumericRange.scala +++ b/src/library/scala/collection/immutable/NumericRange.scala @@ -175,34 +175,68 @@ extends AbstractSeq[T] with IndexedSeq[T] with Serializable { catch { case _: ClassCastException => false } final override def sum[B >: T](implicit num: Numeric[B]): B = { - // arithmetic series formula can be used for regular addition - if ((num eq scala.math.Numeric.IntIsIntegral)|| - (num eq scala.math.Numeric.BigIntIsIntegral)|| - (num eq scala.math.Numeric.ShortIsIntegral)|| - (num eq scala.math.Numeric.ByteIsIntegral)|| - (num eq scala.math.Numeric.CharIsIntegral)|| - (num eq scala.math.Numeric.LongIsIntegral)|| - (num eq scala.math.Numeric.FloatAsIfIntegral)|| - (num eq scala.math.Numeric.BigDecimalIsFractional)|| - (num eq scala.math.Numeric.DoubleAsIfIntegral)) { - val numAsIntegral = num.asInstanceOf[Integral[B]] - import numAsIntegral._ - if (isEmpty) num fromInt 0 - else if (numRangeElements == 1) head - else ((num fromInt numRangeElements) * (head + last) / (num fromInt 2)) - } else { - // user provided custom Numeric, we cannot rely on arithmetic series formula - if (isEmpty) num.zero + if (isEmpty) num.zero + else if (numRangeElements == 1) head + else { + // If there is no overflow, use arithmetic series formula + // a + ... (n terms total) ... + b = n*(a+b)/2 + if ((num eq scala.math.Numeric.IntIsIntegral)|| + (num eq scala.math.Numeric.ShortIsIntegral)|| + (num eq scala.math.Numeric.ByteIsIntegral)|| + (num eq scala.math.Numeric.CharIsIntegral)) { + // We can do math with no overflow in a Long--easy + val exact = (numRangeElements * ((num toLong head) + (num toInt last))) / 2 + num fromInt exact.toInt + } + else if (num eq scala.math.Numeric.LongIsIntegral) { + // Uh-oh, might be overflow, so we have to divide before we overflow. + // Either numRangeElements or (head + last) must be even, so divide the even one before multiplying + val a = head.toLong + val b = last.toLong + val ans = + if ((numRangeElements & 1) == 0) (numRangeElements / 2) * (a + b) + else numRangeElements * { + // Sum is even, but we might overflow it, so divide in pieces and add back remainder + val ha = a/2 + val hb = b/2 + ha + hb + ((a - 2*ha) + (b - 2*hb)) / 2 + } + ans.asInstanceOf[B] + } + else if ((num eq scala.math.Numeric.FloatAsIfIntegral) || + (num eq scala.math.Numeric.DoubleAsIfIntegral)) { + // Try to compute sum with reasonable accuracy, avoiding over/underflow + val numAsIntegral = num.asInstanceOf[Integral[B]] + import numAsIntegral._ + val a = math.abs(head.toDouble) + val b = math.abs(last.toDouble) + val two = num fromInt 2 + val nre = num fromInt numRangeElements + if (a > 1e38 || b > 1e38) nre * ((head / two) + (last / two)) // Compute in parts to avoid Infinity if possible + else (nre / two) * (head + last) // Don't need to worry about infinity; this will be more accurate and avoid underflow + } + else if ((num eq scala.math.Numeric.BigIntIsIntegral) || + (num eq scala.math.Numeric.BigDecimalIsFractional)) { + // No overflow, so we can use arithmetic series formula directly + // (not going to worry about running out of memory) + val numAsIntegral = num.asInstanceOf[Integral[B]] + import numAsIntegral._ + ((num fromInt numRangeElements) * (head + last)) / (num fromInt 2) + } else { - var acc = num.zero - var i = head - var idx = 0 - while(idx < length) { - acc = num.plus(acc, i) - i = i + step - idx = idx + 1 + // User provided custom Numeric, so we cannot rely on arithmetic series formula (e.g. won't work on something like Z_6) + if (isEmpty) num.zero + else { + var acc = num.zero + var i = head + var idx = 0 + while(idx < length) { + acc = num.plus(acc, i) + i = i + step + idx = idx + 1 + } + acc } - acc } } } diff --git a/src/library/scala/collection/immutable/PagedSeq.scala b/src/library/scala/collection/immutable/PagedSeq.scala index 8910ee16b9..c8d0b00327 100644 --- a/src/library/scala/collection/immutable/PagedSeq.scala +++ b/src/library/scala/collection/immutable/PagedSeq.scala @@ -190,8 +190,8 @@ extends scala.collection.AbstractSeq[T] val e = if (_end == UndeterminedEnd) _end else start + _end var f = first1 while (f.end <= s && !f.isLast) { - if (f.next eq null) f.addMore(more) - f = f.next + if (f.next eq null) f = f.addMore(more) + else f = f.next } // Warning -- not refining `more` means that slices can freely request and obtain // data outside of their slice. This is part of the design of PagedSeq diff --git a/src/library/scala/collection/immutable/Range.scala b/src/library/scala/collection/immutable/Range.scala index 984ea7ba50..fb7dd4cfbf 100644 --- a/src/library/scala/collection/immutable/Range.scala +++ b/src/library/scala/collection/immutable/Range.scala @@ -153,19 +153,15 @@ extends scala.collection.AbstractSeq[Int] } @inline final override def foreach[@specialized(Unit) U](f: Int => U) { - validateMaxLength() - val isCommonCase = (start != Int.MinValue || end != Int.MinValue) - var i = start - var count = 0 - val terminal = terminalElement - val step = this.step - while( - if(isCommonCase) { i != terminal } - else { count < numRangeElements } - ) { - f(i) - count += 1 - i += step + // Implementation chosen on the basis of favorable microbenchmarks + // Note--initialization catches step == 0 so we don't need to here + if (!isEmpty) { + var i = start + while (true) { + f(i) + if (i == lastElement) return + i += step + } } } @@ -364,18 +360,19 @@ extends scala.collection.AbstractSeq[Int] // this is normal integer range with usual addition. arithmetic series formula can be used if (isEmpty) 0 else if (numRangeElements == 1) head - else (numRangeElements.toLong * (head + last) / 2).toInt + else ((numRangeElements * (head.toLong + last)) / 2).toInt } else { // user provided custom Numeric, we cannot rely on arithmetic series formula if (isEmpty) num.toInt(num.zero) else { var acc = num.zero var i = head - while(i != terminalElement) { + while (true) { acc = num.plus(acc, i) + if (i == lastElement) return num.toInt(acc) i = i + step } - num.toInt(acc) + 0 // Never hit this--just to satisfy compiler since it doesn't know while(true) has type Nothing } } } diff --git a/src/library/scala/util/Properties.scala b/src/library/scala/util/Properties.scala index 367488f116..d4a5e2f0e8 100644 --- a/src/library/scala/util/Properties.scala +++ b/src/library/scala/util/Properties.scala @@ -1,6 +1,6 @@ /* __ *\ ** ________ ___ / / ___ Scala API ** -** / __/ __// _ | / / / _ | (c) 2006-2013, LAMP/EPFL ** +** / __/ __// _ | / / / _ | (c) 2006-2015, LAMP/EPFL ** ** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** ** /____/\___/_/ |_/____/_/ | | ** ** |/ ** @@ -105,7 +105,7 @@ private[scala] trait PropertiesTrait { * or "version (unknown)" if it cannot be determined. */ val versionString = "version " + scalaPropOrElse("version.number", "(unknown)") - val copyrightString = scalaPropOrElse("copyright.string", "Copyright 2002-2013, LAMP/EPFL") + val copyrightString = scalaPropOrElse("copyright.string", "Copyright 2002-2015, LAMP/EPFL") /** This is the encoding to use reading in source files, overridden with -encoding. * Note that it uses "prop" i.e. looks in the scala jar, not the system properties. |