On Saturday, 18 October 2014 at 12:16:24 UTC, John Colvin wrote:
> writeln(a.kahanSum);        // 111.157
> writeln(a.sum);             // -1272
> writeln(a.sort().kahanSum); // 0

Yes, but it is misleading, my test case was bad. Try to add a 1.0 element to the array.

a.append(1.0)
a = sorted(a)

print sum(a), kahan(a), accurate(a)

-1024.0 0.0 1.0

On Saturday, 18 October 2014 at 12:22:38 UTC, Ola Fosheim Grøstad wrote:
> On Saturday, 18 October 2014 at 12:16:24 UTC, John Colvin wrote:
>> writeln(a.kahanSum);        // 111.157
>> writeln(a.sum);             // -1272
>> writeln(a.sort().kahanSum); // 0
>
> Yes, but it is misleading, my test case was bad. Try to add a 1.0 element to the array.

Note: the sort should be over abs(x) to have an effect, but then we would need a different dataset since +N and -N will cancel out too easily.

On Saturday, 18 October 2014 at 10:44:59 UTC, Ola Fosheim Grøstad wrote:
> On Saturday, 18 October 2014 at 08:21:47 UTC, eles wrote:
>> On Saturday, 18 October 2014 at 05:54:01 UTC, Ola Fosheim Grøstad wrote:
>>> On Saturday, 18 October 2014 at 04:35:07 UTC, Walter Bright wrote:
>>
>>> Larger mantissa can help a little bit, but only a little bit.
>>
>> https://en.wikipedia.org/wiki/Kahan_summation_algorithm
>
> Kahan helps a little bit:
>
>
> a = [math.pi*(n**9) for n in range(0,101)]
>       +[-math.pi*(n**9) for n in range(100,0,-1)]

This might simply be a case biased in favor of pairwise summation, as numbers ar symmetric.

On Saturday, 18 October 2014 at 12:48:00 UTC, eles wrote:
> This might simply be a case biased in favor of pairwise summation, as numbers ar symmetric.

I haven't used pairwise summation though. The best solution is to partition based on exponent and use accurate integer arithmetics. The first function on the link I posted above is accurate in the partitions, but inaccurate of the summation of the partitions…  :-/

But yes, you can create a lot worse datasets. Kahan only recover a few of the lost bits due to rounding.

On 10/18/14, 4:43 AM, John Colvin wrote:
> auto kahanSum(R)(R input)
> {
>      double sum = 0.0;
>      double c = 0.0;
>      foreach(double el; input)
>      {
>          double y = el - c;
>          double t = sum + y;
>          c = (t - sum) - y;
>          sum = t;
>      }
>      return sum;
> }

No need to implement it. http://dlang.org/phobos/std_algorithm.html#.sum

Andrei

On Saturday, 18 October 2014 at 15:17:09 UTC, Andrei Alexandrescu wrote:
>
> No need to implement it. http://dlang.org/phobos/std_algorithm.html#.sum
>

It isn't accurate. Python's fsum is around 100 lines of c-code and AFAIK based on this algorithm:

http://www.cs.berkeley.edu/~jrs/papers/robustr.pdf

more:

https://hg.python.org/cpython/file/7c183c782401/Modules/mathmodule.c#l1063

http://www-pequan.lip6.fr/~graillat/papers/rr2005-03.pdf

But I think an integer version is faster on a large dataset.

Demmel and Hida use different algorithms based on then input size:

http://www.cs.berkeley.edu/~demmel/AccurateSummation.pdf

Another overview of summation algorithms:

http://www.sigsam.org/bulletin/articles/147/sumnums.pdf

On Friday, 17 October 2014 at 09:17:52 UTC, ZombineDev wrote:
> I saw [this][0] proposal for adding ranges to C++'s standard
> library. The [paper][1] looks at D style ranges, but concludes:
>
>> Since iterators can implement D ranges, but D ranges cannot be used to implement iterators, we conclude that iterators form a more powerful and foundational basis.
>
> What do you guys think?

"Since assembly code can be used to implement Java but java cannot be used to implement assembly code, we conclude that assembly code forms a more powerful and foundational basis."

I probably could have chosen that example better, but I hope it gets my point across.  It's always possible to reduce a library interface to something that's even more stripped-down, which is by definition more powerful and foundational.  But if the user never wants to work at that low level of abstraction then you're just imposing an unnecessary burden upon them.

A well-designed library provides power and flexibility in a form that encourages a good coding style and which inherently reduces the chance of mistakes.  Getting this right is really, really hard to do.  I think D gets it more right than C++ though, across the board.

Regarding iterators vs. ranges, there are still places where ranges struggle to meet the facility of iterators.  But I don't think this is a flaw in the concept so much that it's still fairly new and people are still working out the details.  Given the standardization process for C++, they're probably right to remain with iterators for now and wait for all the kinks to be worked out of range design.  Maybe get ranges into Boost (if they aren't there already) and see how it goes.  But dismissing ranges out of hand for not being sufficiently "powerful and foundational" is just silly.

On Saturday, 18 October 2014 at 15:39:36 UTC, Ola Fosheim Grøstad wrote:
> On Saturday, 18 October 2014 at 15:17:09 UTC, Andrei Alexandrescu wrote:
>>
>> No need to implement it. http://dlang.org/phobos/std_algorithm.html#.sum
>>
>
> It isn't accurate.

Did you look at the doc. It's specially designed to be accurate...

On Saturday, 18 October 2014 at 16:46:31 UTC, monarch_dodra wrote:
> Did you look at the doc. It's specially designed to be accurate...

Change the docs?