[New-bugs-announce] [issue19171] pow() improvement on longs

Armin Rigo report at bugs.python.org
Sat Oct 5 16:07:17 CEST 2013

New submission from Armin Rigo:

The attached patch (which can be applied on both trunk and 2.7) gives a huge speed improvement for the case 'pow(huge_number, smallish_number, smallish_number)'.  The improvement is unbounded: I get 20x with 'pow(x, y, z)' with the arguments 'x = 3 ** 10000, y = 10 ** 51 - 2, z = 10 ** 51' but increasing x just increases the factor.

This is inspired by https://github.com/pyca/ed25519: check out revision 9f3e838d90ded42a86ec74c5e9f5e37dec8122a0, run it with 'time python -u signfast.py < sign.input'.  This patch gives around 14% improvement.  So it's a case that occurs in practice.

components: Interpreter Core
files: pow_speedup.diff
keywords: patch
messages: 198987
nosy: arigo
priority: normal
severity: normal
status: open
title: pow() improvement on longs
versions: Python 2.7, Python 3.4
Added file: http://bugs.python.org/file31964/pow_speedup.diff

Python tracker <report at bugs.python.org>

More information about the New-bugs-announce mailing list