8000 Makes Range#sum an O(1) operation instead of an O(n) one. by soc · Pull Request #83 · scala/legacy-svn-scala · GitHub
[go: up one dir, main page]
Skip to content
This repository was archived by the owner on Feb 23, 2018. It is now read-only.

Makes Range#sum an O(1) operation instead of an O(n) one. #83

Closed
wants to merge 1 commit into from
Closed

Makes Range#sum an O(1) operation instead of an O(n) one. #83

wants to merge 1 commit into from

Conversation

soc
Copy link
@soc soc commented Sep 3, 2011

Makes Range#sum an O(1) operation instead of an O(n) one. Partially fixes SI-4658. NumericRange stays slow, thanks to the one who had the brilliant idea that Numeric doesn't need a division operation.

@soc
Copy link
Author
soc commented Sep 3, 2011

def sum[B](implicit num: Numeric[B]): Int

is wrong and doesn't compile, it should be:

def sum[B >: Int](implicit num: Numeric[B]): Int

I'll redo the patch tomorrow.

@jsuereth
Copy link
jsuereth commented Sep 3, 2011

Can you add scalacheck test with this that checks against start/end/step?
On Sep 3, 2011 3:51 PM, "soc" <
reply@reply.github.com>
wrote:

Makes Range#sum an O(1) operation instead of an O(n) one. Partially fixes
SI-4658. NumericRange stays slow, thanks to the one who had the brilliant
idea that Numeric doesn't need a division operation.

Reply to this email directly or view it on GitHub:
scala/scala#83

@soc
Makes Range#sum an O(1) operation instead of an O one.
2bfaecc 
Partially fixes SI-4658. NumericRange stays slow, thanks to the brilliant idea that Numeric doesn't need a division operation. </rant>
Added some simple test.
@soc
Copy link
Author
soc commented Sep 4, 2011

Yes, did that. it compiles, all tests run. Is the unit test enough?

@notnoop
Copy link
notnoop commented Nov 30, 2011

The patch may contain a tiny bug where it invokes an arithmetic overflow in (len.toLong * (head + last) / 2).toInt. Consider the following case:

val a = Int.MaxValue - 2
assert(Range(a, a+1).sum == a) // <-- Currently passes, with unmodified Range
assert((1.toLong * (a + a) / 2).toInt == a) // <- Fails

I would change the method to the following:

final override def sum[B >: Int](implicit num: Numeric[B]): Int = {
  length match {
      case 0 => 0
      case 1 => head
      case len => (len.toLong * (head + last) / 2).toInt
  }
}

If len > 1 and (head + last) overflows, then the sum should overflow as well.

@soc
Copy link
Author
soc commented Nov 30, 2011

Great, thanks!

Although I wonder if I wouldn't prefer (len.toLong * (head.toLong + last) / 2).toInt ...

@soc soc closed this Dec 2, 2011
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Reviewers
No reviews
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
3 participants
@soc @jsuereth @notnoop
0