daphne-project / daphne-project/daphne

Numerically stable summation

Open
#698 0 comments 0 reactions 0 assignees View on GitHub
good first issue
Dominant language
C++
Stars
81
Forks
83
PR merge metrics
No merged PRs in 30d

Description

It is known that adding up a large number of small floating-point values can lead to significant rounding errors unless a smart summation algorithm is applied. In fact, such a problem can easily be triggered in DAPHNE at the moment.

The following script generates a matrix of 100 M single-precision floating-point values uniformly distributed in [0, 1]. The sum should be roughly 0.5 * 100 M = 50 M = 5.0e+07. However, the output (on my system) is `1.67772e+07`.

```R
X = rand(10^4, 10^4, as.f32(0.0), as.f32(1.0), 1, -1);
print(sum(X));
```

**This task is to implement a numerically stable summation** in the `aggAll`-kernel (`src/runtime/local/kernels/AggAll.h`). The Kahan summation algorithm could be a candidate.

One could extend the task to check in how far other aggregates (e.g., column-wise (`AggCol.h`), row-wise (`AggRow.h`), and cumulative (`AggCum.h`)) or other aggregation functions (e.g., `mean`, `var`, `stddev`) or other values types (`f64`) are affected by similar problems.

Contributor guide

Open the contributing guide

Research direction

Start by reading src/runtime/local/kernels/AggAll.h and reproducing the provided R script that sums 100 million f32 values. Compare the current result with the expected value near 5.0e+07 and verify that the aggAll result is numerically stable; the optional aggregate extensions are separate scope.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
data
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.