[Python-ideas] Fast sum() for non-numbers

[Oscar Benjamin]

On 11 July 2013 11:47, Ron Adam <ron3200 at gmail.com> wrote:
> On 07/10/2013 08:03 PM, Steven D'Aprano wrote:
>> On 11/07/13 07:00, Ron Adam wrote:
>>>
>>> Just curious, how does your sum compare with fsum() in the math module?
>>
>> math.fsum is a high-precision floating point sum, keeping extra precision
>> that the built-in loses. Compare these:
[snip]
>
> I was thinking more on the lines of how it worked internally compared to
> sum.  And how it handles different inputs.  Of course it is quite a bit
> slower too.

math.fsum converts all inputs to float and then adds them using (I
assume) Kahan summation [1]. A demonstration:

>>> class A:
...     pass
...
>>> a = A()
>>> math.fsum([a])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: A instance has no attribute '__float__'
>>> class A:
...     def __float__(self):
...         return -1
...
>>> a = A()
>>> math.fsum([a])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: nb_float should return float object
>>> class A:
...     def __float__(self):
...         return -1.0
...
>>> a = A()
>>> math.fsum([a])
-1.0

>
>>>> timeit("fsum(r)", "from __main__ import fsum\nr=list(range(100))")
> 15.151492834091187
>
>>>> timeit("sum(r)", "r=list(range(100))")
> 2.282749891281128

The above is not a fair comparison since fsum converts them to floats
as you say. fsum is useless for integers since the additional
computation is all about floating point precision. You should use a
list of floats for a fair test:

>>> timeit("fsum(r)", "from __main__ import fsum\nr=list(map(float, range(100)))")
3.432480121620099
>>> timeit("sum(r)", "from __main__ import fsum\nr=list(map(float, range(100)))")
1.6432468412557402


[1] http://en.wikipedia.org/wiki/Kahan_summation_algorithm


Oscar