add balanced_sum to Sage

[mwhansen]

Component: basic arithmetic

Author: Jason Grout, Mike Hansen

Reviewer: Robert Bradshaw

Merged: Sage 4.1.1.alpha1

Issue created by migration from https://trac.sagemath.org/ticket/2737

[mwhansen]

Attachment: 2737.patch.gz

[mwhansen]

comment:1

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

[robertwb]

comment:2

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.

[mwhansen]

comment:3

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.

[jasongrout]

comment:5

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.

[jasongrout]

Reviewer: Jason Grout

[jasongrout]

comment:6

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

[jasongrout]

comment:7

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.

[jasongrout]

comment:8

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

[jasongrout]

apply instead of previous patch

[robertwb]

comment:9

Attachment: trac-2737-balancedsum-rebased-bug-fixed.patch.gz

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.

[robertwb]

Changed reviewer from Jason Grout to Robert Bradshaw

[robertwb]

Author: Jason Grout, Mike Hansen

[7c09a680-e216-4024-bb8e-9bfd4aa7f313]

comment:11

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

[7c09a680-e216-4024-bb8e-9bfd4aa7f313]

Merged: Sage 4.1.1.alpha1

[7c09a680-e216-4024-bb8e-9bfd4aa7f313]

comment:12

Replying to @jasongrout:

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.

[jasongrout]

comment:13

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.