Deprecate (cum)sum_kbn #24869

ararslan · 2017-11-30T21:45:30Z

This removes sum_kbn and cumsum_kbn in favor of sum and cumsum, respectively, with a note about the potential loss in precision. Those can be moved to a package if someone wants them, as was done with rref.

Fixes #24804

Sacha0 · 2017-12-01T01:26:13Z

test/offsetarray.jl

-cv2 = OffsetArray([1,-1e100,-1e100,2], (5,))*1000
-@test isequal(cumsum_kbn(v), cv)
-@test isequal(cumsum_kbn(v2), cv2)
-@test isequal(sum_kbn(v), sum_kbn(parent(v)))


Perhaps modify rather than eradicate these tests? I conjecture that testing OffsetArray is these tests' purpose rather than testing [cum]sum_kbn specifically :).

Interestingly, even if I convert these to BigFloats, using cumsum rather than cumsum_kbn seems to give a different answer:

julia> v = OffsetArray(BigFloat[1,1e100,1,-1e100], (-3,))*1000 OffsetArray{BigFloat,1,Array{BigFloat,1}} with indices -2:1: 1.0e+03 1.000000000000000015902891109759918046836080856394528138978132755774783877217038e+103 1.0e+03 -1.000000000000000015902891109759918046836080856394528138978132755774783877217038e+103 julia> cumsum(v) OffsetArray{BigFloat,1,Array{BigFloat,1}} with indices -2:1: 1.0e+03 1.000000000000000015902891109759918046836080856394528138978132755774783877217038e+103 1.000000000000000015902891109759918046836080856394528138978132755774783877217038e+103 1.0e+03 julia> cumsum_kbn(v) OffsetArray{BigFloat,1,Array{BigFloat,1}} with indices -2:1: 1.0e+03 1.000000000000000015902891109759918046836080856394528138978132755774783877217038e+103 1.000000000000000015902891109759918046836080856394528138978132755774783877217038e+103 2.0e+03

Perhaps need higher precision, and/or cumsum doesn't preserve precision in the accumulation?

I'd just use isapprox here. The fact that the result was exact before must have been due to the way the KBN algorithm worked in that particular case, but we don't really care here since the goal is just to test that it works on OffsetArray.

The problem with isapprox in this case is that 1000 and 2000 aren't approximately equal. 😛

OK, I misread. That's just because BigFloat doesn't have enough precision by default. It works with a higher precision:

julia> setprecision(BigFloat, 500) 500 julia> cumsum(BigFloat[1,1e100,1,-1e100]*1000) 4-element Array{BigFloat,1}: 1.0e+03 1.0000000000000000159028911097599180468360808563945281389781327557747838772170381060813469985856815105e+103 1.0000000000000000159028911097599180468360808563945281389781327557747838772170381060813469985856815106e+103 2.0e+03 julia> cumsum_kbn(BigFloat[1,1e100,1,-1e100]*1000) 4-element Array{BigFloat,1}: 1.0e+03 1.0000000000000000159028911097599180468360808563945281389781327557747838772170381060813469985856815105e+103 1.0000000000000000159028911097599180468360808563945281389781327557747838772170381060813469985856815106e+103 2.0e+03

But it's really weird to mix testing OffsetArray with testing precision with very high values. Maybe split them into two separate tests, with a comment saying what is being tested?

Sacha0 · 2017-12-01T01:28:44Z

test/reduce.jl

- cs = cumsum(z)
- @test (es - cs[end]) < es * 1e-13
- @test (es2 - cs[10^5]) < es2 * 1e-13
-end


I wonder whether these tests' purpose is testing [cum]sum accuracy rather than testing sub_kbn per se? And if so, perhaps retaining these tests with some other mechanism to calculate an accurate sum would be worthwhile?

Like using BigFloat?

musm · 2017-12-01T15:34:11Z

Instead of deprecating this, how about following the OPs suggestion of adding a named optional argument for the algorithm:

...A more general and Julian approach would be to use something like sum(x, alg=KahanBabuskaNeumaier) or sum(KahanBabuskaNeumaier, x) (or just KBN).

KristofferC · 2017-12-01T15:40:16Z

I think that is an excessive generalization. This seems very much in package territory to me.

ararslan · 2017-12-02T00:01:31Z

https://github.com/JuliaMath/KahanSummation.jl

ViralBShah · 2017-12-02T16:44:38Z

Wow all green!

ararslan · 2017-12-05T21:23:33Z

CircleCI failure:

ERROR: LoadError: LoadError: cannot obtain socket name: operation not permitted (EPERM)
uv_error at ./libuv.jl:68 [inlined]
_sockname(::TCPSocket, ::Bool) at ./socket.jl:1001
bind_client_port at ./distributed/managers.jl:492 [inlined]
socket_reuse_port() at ./distributed/managers.jl:471
connect_to_worker(::SubString{String}, ::UInt16) at ./distributed/managers.jl:498
connect(::TopoTestManager, ::Int64, ::WorkerConfig) at ./distributed/managers.jl:437
create_worker(::TopoTestManager, ::WorkerConfig) at ./distributed/cluster.jl:513
setup_launched_worker(::TopoTestManager, ::WorkerConfig, ::Array{Int64,1}) at ./distributed/cluster.jl:459
(::getfield(Base.Distributed, Symbol("##41#44")){TopoTestManager,WorkerConfig})() at ./task.jl:348

...and 7 more exception(s).

Surely unrelated. FreeBSD CI was down when CI last ran for this PR. Everything else is green though.

This removes `sum_kbn` and `cumsum_kbn` in favor of `sum` and `cumsum`, respectively, with the `*_kbn` functions moving to a package. Fixes #24804

ararslan · 2017-12-07T22:55:56Z

I've rebased this, so unless there are any further comments, I plan to merge this pretty soon.

yurivish · 2017-12-07T23:05:00Z

@JeffreySarnoff posted this very minimal sum_kbn use case in Slack today that I found quite interesting as someone who hasn't thought deeply about summation algorithms. Not sure it says anything either way about this PR, but I thought I'd post it here to preserve it once the Slack history is lost to the sands of time:

a, b, c = 1.0, 1.0e16, -1.0e16;
fwd = [a, b, a, c];
rev = [c, a, b, a];

sum(fwd), sum(rev), sum_kbn(fwd), sum_kbn(rev)
0.0, 1.0, 2.0, 2.0

ararslan · 2017-12-08T18:27:22Z

CI failures are unrelated. AppVeyor i686 is a failure to download Cygwin and Circle x86-64 is something about deserializing a remote libgit2 exception.

JeffreySarnoff · 2017-12-08T19:56:39Z

I put sum_kbn and cumsum_kbn here.

diegozea · 2017-12-08T20:02:20Z

This is missing in NEWS.md

ararslan · 2017-12-08T20:28:14Z

@JeffreySarnoff I already made and registered https://github.com/JuliaMath/KahanSummation.jl.

@diegozea Good catch, I'll rectify that. Thanks.

JeffreySarnoff · 2017-12-08T20:59:37Z

@ararslan good!

This removes `sum_kbn` and `cumsum_kbn` in favor of `sum` and `cumsum`, respectively, with the `*_kbn` functions moving to a package. Fixes JuliaLang#24804

ararslan added domain:arrays [a, r, r, a, y, s] kind:deprecation This change introduces or involves a deprecation domain:maths Mathematical functions labels Nov 30, 2017

ararslan requested a review from andreasnoack November 30, 2017 21:45

ararslan force-pushed the aa/dep-kbn branch from b0aeb49 to 7b3ad39 Compare November 30, 2017 22:12

Sacha0 reviewed Dec 1, 2017

View reviewed changes

ararslan force-pushed the aa/dep-kbn branch from 7b3ad39 to 965becf Compare December 2, 2017 00:30

ararslan force-pushed the aa/dep-kbn branch 3 times, most recently from 8992771 to be6141a Compare December 5, 2017 03:13

Deprecate (cum)sum_kbn

1a4ebd4

This removes `sum_kbn` and `cumsum_kbn` in favor of `sum` and `cumsum`, respectively, with the `*_kbn` functions moving to a package. Fixes #24804

ararslan force-pushed the aa/dep-kbn branch from be6141a to 1a4ebd4 Compare December 7, 2017 22:54

ararslan merged commit 5f929a4 into master Dec 8, 2017

ararslan deleted the aa/dep-kbn branch December 8, 2017 18:27

evetion pushed a commit to evetion/julia that referenced this pull request Dec 12, 2017

Deprecate (cum)sum_kbn (JuliaLang#24869)

f15c987

This removes `sum_kbn` and `cumsum_kbn` in favor of `sum` and `cumsum`, respectively, with the `*_kbn` functions moving to a package. Fixes JuliaLang#24804

cormullion mentioned this pull request Mar 18, 2018

NEWS.md is getting a bit untidy #26508

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Deprecate (cum)sum_kbn #24869

Deprecate (cum)sum_kbn #24869

ararslan commented Nov 30, 2017

Sacha0 Dec 1, 2017

ararslan Dec 2, 2017

Sacha0 Dec 2, 2017

nalimilan Dec 2, 2017

ararslan Dec 3, 2017

nalimilan Dec 4, 2017 •

edited

Loading

Sacha0 Dec 1, 2017

nalimilan Dec 1, 2017

musm commented Dec 1, 2017

KristofferC commented Dec 1, 2017

ararslan commented Dec 2, 2017

ViralBShah commented Dec 2, 2017

ararslan commented Dec 5, 2017

ararslan commented Dec 7, 2017

yurivish commented Dec 7, 2017

ararslan commented Dec 8, 2017

JeffreySarnoff commented Dec 8, 2017

diegozea commented Dec 8, 2017

ararslan commented Dec 8, 2017

JeffreySarnoff commented Dec 8, 2017

Deprecate (cum)sum_kbn #24869

Deprecate (cum)sum_kbn #24869

Conversation

ararslan commented Nov 30, 2017

Sacha0 Dec 1, 2017

Choose a reason for hiding this comment

ararslan Dec 2, 2017

Choose a reason for hiding this comment

Sacha0 Dec 2, 2017

Choose a reason for hiding this comment

nalimilan Dec 2, 2017

Choose a reason for hiding this comment

ararslan Dec 3, 2017

Choose a reason for hiding this comment

nalimilan Dec 4, 2017 • edited Loading

Choose a reason for hiding this comment

Sacha0 Dec 1, 2017

Choose a reason for hiding this comment

nalimilan Dec 1, 2017

Choose a reason for hiding this comment

musm commented Dec 1, 2017

KristofferC commented Dec 1, 2017

ararslan commented Dec 2, 2017

ViralBShah commented Dec 2, 2017

ararslan commented Dec 5, 2017

ararslan commented Dec 7, 2017

yurivish commented Dec 7, 2017

ararslan commented Dec 8, 2017

JeffreySarnoff commented Dec 8, 2017

diegozea commented Dec 8, 2017

ararslan commented Dec 8, 2017

JeffreySarnoff commented Dec 8, 2017

nalimilan Dec 4, 2017 •

edited

Loading