[ARROW-11758] [C++][Compute] Summation kernel round-off error

• Type: Bug
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 4.0.0
• Component/s: C++
• Labels: pull-request-available
• External issue URL: https://github.com/apache/arrow/issues/27612
• Assignee: yibocai#1
• Reporter: Yibo Cai
• Created: 24/Feb/21 06:30
• Updated: 11/Jan/23 08:21
• Resolved: 12/Mar/21 01:33

Description

From below test, summation kernel is of lower precision than numpy.sum.
Numpy implements pairwise summation [1] with O(logn) round-off error, better than O(n) error from naive summation.

sum.py

import numpy as np
import pyarrow.compute as pc

t = np.arange(321000, dtype='float64')
t2 = t - np.mean(t)
t2 *= t2

print('numpy sum:', np.sum(t2))
print('arrow sum:', pc.sum(t2))

test result

# Verified with wolfram alpha (arbitrary precision), Numpy's result is correct. 
$ ARROW_USER_SIMD_LEVEL=SSE4_2 python sum.py
numpy sum: 2756346749973250.0
arrow sum: 2756346749973248.0

$ ARROW_USER_SIMD_LEVEL=AVX2 python sum.py 
numpy sum: 2756346749973250.0
arrow sum: 2756346749973249.0

[1] https://en.wikipedia.org/wiki/Pairwise_summation

Issue Links

• relates to: ARROW-11567 [C++][Compute] Variance kernel has precision issue
• links to: GitHub Pull Request #9635