[issue36027] Consider adding modular multiplicative inverse to the math module
Berry Schoenmakers
report at bugs.python.org
Tue Feb 19 12:24:32 EST 2019
Berry Schoenmakers <l.a.m.schoenmakers at tue.nl> added the comment:
> Is there a clear reason for your expectation that the xgcd-based algorithm should be faster?
Yeah, good question. Maybe I'm assuming too much, like assuming that it should be faster;) It may depend a lot on the constants indeed, but ultimately the xgcd style should prevail.
So the pow-based algorithm needs to do log(p) full-size muls, plus log(p) modular reductions. Karatsuba helps a bit to speed up the muls, but as far as I know it only kicks in for quite sizeable inputs. I forgot how Python is dealing with the modular reductions, but presumably that's done without divisions.
The xgcd-based algorithm needs to do a division per iteration, but the numbers are getting smaller over the course of the algorithm. And, the worst-case behavior occurs for things involving Fibonacci numbers only. In any case, the overall bit complexity is quadratic, even if division is quadratic. There may be a few expensive divisions along the way, but these also reduce the numbers a lot in size, which leads to good amortized complexity for each iteration.
----------
_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue36027>
_______________________________________
More information about the Python-bugs-list
mailing list