Why sum_kbn can't sum generators?


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)?


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)


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.


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.



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