Fix OOB access in Quantile()
Fixes #22. (*TDigest).Quantile() causes an OOB panic when the digest has been provided with values that, due to floating point arithmetic errors, cause the sort.Search call to not find an i such that t.cumulative[i] >= index. (Minimal playground reproduction). This PR fixes this bug by clamping access to processed.Len().
Furthermore, the unit tests as written did not pass on my M2 MacBook Pro: due to differences in how the M2 performs floating point math compared to Intel or AMD CPUs, there are small deltas some 14 digits into the results, so got == tt.expected evaluates to false:
$ go test
--- FAIL: TestTdigest_Quantile (0.00s)
--- FAIL: TestTdigest_Quantile/uniform_50 (0.00s)
tdigest_test.go:217: unexpected quantile 0.500000, got 49.99250234584355 want 49.992502345843555
--- FAIL: TestTdigest_Quantile/uniform_99 (0.00s)
tdigest_test.go:217: unexpected quantile 0.990000, got 98.98503400959561 want 98.98503400959562
--- FAIL: TestTdigest_Quantile/uniform_99.9 (0.00s)
tdigest_test.go:217: unexpected quantile 0.999000, got 99.9010378104362 want 99.90103781043621
FAIL
exit status 1
FAIL github.com/influxdata/tdigest 1.404s
This PR fixes tests on this hardware by updating to a more recent version of gonum and using its scalar.EqualWithinRel function to compare floats.
Hey 👋🏻 We quickly hit this panic when running on ARM-based VMs, rendering the module unusable. Is there a reason this is not being merged?