Opened 15 years ago

Closed 13 years ago

# [with patch, positive review] add balanced_sum to Sage

Reported by: Owned by: Mike Hansen somebody minor sage-4.1.1 basic arithmetic Sage 4.1.1.alpha1 Jason Grout, Mike Hansen Robert Bradshaw N/A

### comment:1 Changed 15 years ago by Mike Hansen

I've added my initial patch. There is major code duplication through.

### comment:2 Changed 15 years ago by Robert Bradshaw

Can you post some timings? For most types summation won't be helped by balancing it (compared to say multiplication) because the basic algorithm is already linear. Unless there are non-trivial improvements, I don't think it's worth the code duplication.

### comment:3 Changed 15 years ago by Mike Hansen

I don't know of any good benchmarks (since I don't have any personal interest in this). However, this is from Joel:

```About a month ago, I mailed sage-devel with a related issue:

sage: N=1000
sage: R.<x,y>=QQ[]
sage: L2=[x^i for i in range(N)]
sage: sum(L2)
...

The above sum behaves quadratically since it appears that singular goes
through it's whole list of monomials when it adds a single monomial.  This
was much improved by a divide and conquer sum approach.  I didn't bother to
write the generic function though.

I'm just noting that if you've written the generic code, I think it should be
included because there are some types for which the small additions are
expensive.  Whether or not this should replace 'sum' in the sage global
namespace, I'm not so certain.
```

### comment:4 Changed 13 years ago by Minh Van Nguyen

Summary: add balanced_sum to Sage → [with patch, needs review] add balanced_sum to Sage

### comment:5 Changed 13 years ago by Jason Grout

Summary: [with patch, needs review] add balanced_sum to Sage → [with patch, positive review] add balanced_sum to Sage

I fixed a bug, added some documentation, and rebased the patch to 4.1. I think my changes are minor enough that I can still review the patch. Positive review.

Mike is right, though. There is some major code duplication that eventually should be factored out.

### comment:6 follow-up:  12 Changed 13 years ago by Jason Grout

Reviewers: → Jason Grout

Some timing info for the tour, comparing balanced sum with the builtin sum.

```sage: a=range(10e6)
sage: %timeit sum(a)
10 loops, best of 3: 2.58 s per loop
sage: %timeit balanced_sum(a)
10 loops, best of 3: 891 ms per loop
sage: balanced_sum(a)==sum(a)
True
```

### comment:7 Changed 13 years ago by Jason Grout

Summary: [with patch, positive review] add balanced_sum to Sage → [with patch, needs review] add balanced_sum to Sage

A more drastic example:

```sage: a=[[i] for i in range(10e4)]
sage: %time b=sum(a,[])
CPU times: user 209.95 s, sys: 0.57 s, total: 210.51 s
Wall time: 245.69 s
sage: a==[[i] for i in range(10e4)]
True
sage: b==range(10e4)
True
sage: %time c=balanced_sum(a, [])
CPU times: user 0.11 s, sys: 0.00 s, total: 0.11 s
Wall time: 0.12 s
sage: a==[[i] for i in range(10e4)]
True
sage: c==range(10e4)
True
```

However, I also uncovered a bug because the function does not copy its arguments (it modified the lists it was using, giving an incorrect sum). I'm posting a revised patch. This revised patch should be reviewed.

### comment:8 Changed 13 years ago by Jason Grout

Apply just the trac-2737-balancedsum-rebased-bug-fixed.patch patch.

### comment:9 Changed 13 years ago by Robert Bradshaw

Summary: [with patch, needs review] add balanced_sum to Sage → [with patch, positive review] add balanced_sum to Sage

Positive review to the second patch. I don't see an easy way to get rid of code duplication, so I think this is worth it.

### comment:10 Changed 13 years ago by Robert Bradshaw

Authors: → Jason Grout, Mike Hansen Jason Grout → Robert Bradshaw

### comment:11 Changed 13 years ago by Minh Van Nguyen

Merged in: → Sage 4.1.1.alpha1 → fixed new → closed

Merged `trac-2737-balancedsum-rebased-bug-fixed.patch`.

### comment:12 in reply to:  6 Changed 13 years ago by Minh Van Nguyen

Some timing info for the tour, comparing balanced sum with the builtin sum.

```sage: a=range(10e6)
sage: %timeit sum(a)
10 loops, best of 3: 2.58 s per loop
sage: %timeit balanced_sum(a)
10 loops, best of 3: 891 ms per loop
sage: balanced_sum(a)==sum(a)
True
```

This is what I get on sage.math:

```sage: L = range(10e6)
sage: %time sum(L);
CPU times: user 0.51 s, sys: 0.00 s, total: 0.51 s
Wall time: 0.51 s
sage: %time balanced_sum(L);
CPU times: user 0.78 s, sys: 0.00 s, total: 0.78 s
Wall time: 0.79 s
sage: %timeit sum(L);
10 loops, best of 3: 504 ms per loop
sage: %timeit balanced_sum(L);
10 loops, best of 3: 753 ms per loop
```

Looks like `balanced_sum()` is worse off than the built-in `sum()` for this particular example.

### comment:13 Changed 13 years ago by Jason Grout

So I guess my computer is slow. The builtin sum is *fast*. However, when it costs a fixed high cost to add two elements together (like the lists above), I think the balanced sum is a clear, clear winner. The list example above should show great improvement, even on sage.math.

Note: See TracTickets for help on using tickets.