astrofrog / astrofrog/fast-histogram

histogram1d returns incorrect bins due to rounding error

Open
#63 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
C
Stars
281
Forks
28
PR merge metrics
No merged PRs in 30d

Description

Hello,

the function `histogram1d` (and likely `histogram2d`) can increment the wrong bin when a floating-point rounding error happened. This happens at https://github.com/astrofrog/fast-histogram/blob/main/fast_histogram/_histogram_core.c#L173, when the value of `ix` is calculated just below a whole number due to rounding. The index lookup in the next line then truncates the value to a whole number resulting in an incorrectly incremented bin one below.

See here:
```
left, right = (0.9, 1.1)
bins = 10
norm = bins/(right-left)
value = 1.00
ix = (value-left)*norm;
print(ix, int(ix)) # 4.999999999999997 4
```

The incorrect behaviour of `histogram1d` can be reproduced with the following script:
```
#!/usr/bin/env python3

import numpy as np
from fast_histogram import histogram1d

data = np.array([0.999, 1.000, 1.001, 1.099, 1.100, 1.101])

bins, edges = np.histogram(data, bins=10, range=(0.9, 1.1))
fast_bins = histogram1d(data, bins=10, range=(0.9, 1.1))
print(data)
print(edges)
print("#### NumPy")
print(bins) # [0 0 0 0 1 2 0 0 0 2]
print("#### Fast-Histogram")
print(fast_bins) # [0. 0. 0. 0. 2. 1. 0. 0. 0. 1.]
```

Also this includes another error (miscounted right-most value), the incorrect result due to the rounding error is the in the middle of the bins ( (1,2) vs (2,1) ).

Contributor guide

No contributing guide indexed for this repository

Research direction

Start at fast_histogram/_histogram_core.c around line 173 and reproduce the issue with the Python script in the report. Check histogram1d and likely histogram2d against the NumPy results, including values on the right edge. Done means floating-point boundary cases increment the intended bins and the right-most value is counted correctly.

Written by the indexing model from the issue text.

Assessment

Tech stack
c, python
Domain
data
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Clearly specified
Newbie friendliness
55/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.