This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author tim.peters
Recipients benrg, mark.dickinson, rhettinger, tim.peters
Date 2022-02-28.19:47:30
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1646077650.96.0.738076407872.issue46868@roundup.psfhosted.org>
In-reply-to
Content
Too abstract for me to find compelling. I suspect the title of this report referenced "math.prod with bignums" because it's the only actual concrete use case you had ;-)

Here's another: math.lcm. That can benefit for the same reason as math.prod - provoking Karatsuba multiplication. However, applying lcm to a largish collection of ints is so rare I can't recall ever seeing it done.

Here's a related anti-example: math.gcd. Tree reduction hurts that. It typically falls to 1 quickly, and tree reduction just delays that.

So I'm at best -0 on this, and I'll stop now.

For reference, here's a Python implementation that strives to match functools.reduce's signature and endcase behaviors. It accepts any iterable, and requires temp space at most about log2(number of elements the iterable delivers in all).

That memory frugality adds a log2 factor to the runtime. The O() speed penalty could be eliminated by using temp memory that grows to about half the number of elements in the iterable.

    def treereduce(function, iterable, initializer=None):
        levels = []
        if initializer is not None:
            levels.append(initializer)
        NULL = object()
        for y in iterable:
            for i, x in enumerate(levels):
                if x is NULL:
                    levels[i] = y
                    break
                y = function(x, y)
                levels[i] = NULL
            else:
                levels.append(y)
        y = NULL
        for x in levels:
            if x is not NULL:
                y = x if y is NULL else function(x, y)
        if y is NULL:
            raise TypeError("treereduce() of empty iterable with no initial value")
        return y

Then, for example,

>>> treereduce(lambda x, y: f"({x}+{y})", "abcdefghijk")
'((((a+b)+(c+d))+((e+f)+(g+h)))+((i+j)+k))'
History
Date User Action Args
2022-02-28 19:47:31tim.peterssetrecipients: + tim.peters, rhettinger, mark.dickinson, benrg
2022-02-28 19:47:30tim.peterssetmessageid: <1646077650.96.0.738076407872.issue46868@roundup.psfhosted.org>
2022-02-28 19:47:30tim.peterslinkissue46868 messages
2022-02-28 19:47:30tim.peterscreate