Why sum_kbn can't sum generators?

proposal

#1
sum_kbn(i for i = 1:10)

raises a MethodError:

ERROR: MethodError: no method matching sum_kbn(::Base.Generator{UnitRange{Int64},##9#10})
Closest candidates are:
sum_kbn{T<:AbstractFloat}(::AbstractArray{T<:AbstractFloat,N}) at reduce.jl:237

Is this intentional? Something about the KBN summation prevents it from applying to an iterator (without instantiating it into an array)?


#2

The KBN sum is for floating point numbers and doesn’t provide any benefit for integers, so it looks like it’s not defined for them: for example, sum_kbn([1,2,3]) also doesn’t work. Try using a floating-point range in your generator:

sum_kbn(i for i = 1.0:1.0:10.0)

#3

I’ve just realised that this doesn’t actually work! I thought I’d tested it but I may have accidentally tested normal sum. So yes, you are right that the definition of sum_kbn doesn’t allow for iterators: if you do methods(sum_kbn) you will see that it’s only defined for floating-point arrays. Adding a more general method based on the existing one which accepts an iterable collection would be a nice pull request.


#4

Yes, it seems like there should really be sum_kbn(itr) and sum_kbn(f::Function, itr) methods.

This function has not gotten a huge amount of attention, probably because the sum function is nearly as accurate, and much faster: it uses pairwise summation, which has O(sqrt(log n)) rms error growth, which in most cases is almost indistinguishable from the O(1) error growth of sum_kbn.


#5

#6

@stevengj sum(itr) can’t do pairwise summation, because that requires length. So sum_kbn is actually even more useful for iterators.