[Python-ideas] Yet another sum function (fractions.sum)

[Oscar Benjamin]

On 21 August 2013 01:16, David Mertz <mertz at gnosis.cx> wrote:
> On Tue, Aug 20, 2013 at 3:26 PM, Oscar Benjamin <oscar.j.benjamin at gmail.com>
> wrote:
>>
>> So with all our powers combined I created binsortmergesum (bsms) and
>> it looks like this:
>>
>> def bsms(iterable):
>>     bins = defaultdict(int)
>>     for num in iterable:
>>         bins[num.denominator] += num.numerator
>>     return mergesum([F(n, d) for d, n in sorted(bins.items())])
>
>
> Wow.  I noticed that you didn't do a sort in your binsum(), but I didn't
> think it would make much difference.

And now I see that Stefan already proposed exactly this function as
binsum2. Sorry Stefan, I missed that from your initial post!

> Actually, I thought the cost of the
> sort wouldn't be worth it at all.  It's actually a little unclear to me
> exactly why it makes such a big difference as it does in the 'e' case.

It's because of the natural ordering in the series. Summing in a
random order means that you mix up giant denominators with tiny ones
for pretty much every addition step. This means massive gcd
computations for every addition. Mergesum sums the small denominators
with small ones avoiding the extra large denominators. This is
particularly important for this series since the denominators are
growing super-exponentially.


Oscar