In Python 3.8, pow (n, -1, 1000000007) looks better than pow (n, 1000000007-2, 1000000007)

In Python 3.8, pow (n, -1, 1000000007) looks better than pow (n, 1000000007-2, 1000000007)

Python 3.8 pow can now take a negative value for the second argument, even if you specify the third argument, which is also noted in the Python 3.8 release notes.

What’s New In Python 3.8: Other Language Changes

For integers, the three-argument form of the pow() function now permits the exponent to be negative in the case where the base is relatively prime to the modulus.

And it seems that it is much faster to calculate the inverse element by specifying -1.

$ python3.8
Python 3.8.3 (default, May 23 2020, 15:50:53)
[GCC 9.3.0] on cygwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from timeit import timeit
>>> m = 1000000007
>>> pow(2, m - 2, m)
500000004
>>> pow(2, -1, m)
500000004
>>> timeit(lambda: [pow(i, m - 2, m) for i in range(1, 10000)], number=100)
3.5805746999103576
>>> timeit(lambda: [pow(i, -1, m) for i in range(1, 10000)], number=100)
1.2788116000592709

Recommended Posts

In Python 3.8, pow (n, -1, 1000000007) looks better than pow (n, 1000000007-2, 1000000007)
Golang vs. Python – Is Golang Better Than Python?
cout << "Hello, World! \ N" in python
[python] python's configparser may be better than managing settings in yaml
Quadtree in Python --2
Python in optimization
CURL in python
Metaprogramming in Python
Python 3.3 in Anaconda
Geocoding in python
SendKeys in Python
Meta-analysis in Python
Unittest in python
Epoch in Python
Discord in Python
Sudoku in Python
DCI in Python
quicksort in python
nCr in python
N-Gram in Python
Programming in python
Plink in Python
Constant in python
Lifegame in Python.
FizzBuzz in Python
Sqlite in python
StepAIC in Python
Y / n processing in bash, python and Go
N-gram in python
LINE-Bot [0] in Python
Csv in python
Disassemble in Python
Reflection in Python
Constant in python
nCr in Python.
format in python
Scons in Python3
Puyo Puyo in python
python in virtualenv
PPAP in Python
Quad-tree in Python
Reflection in Python
Chemistry in Python
Hashable in python
DirectLiNGAM in Python
LiNGAM in Python
Flatten in python
flatten in python
Display n digits after the decimal point in python
[Small story] In Python, i = i + 1 is slightly faster than i + = 1.
Shift the alphabet string by N characters in Python
Daily AtCoder # 36 in Python
Clustering text in Python
Implement Enigma in python
Daily AtCoder # 32 in Python
Daily AtCoder # 6 in Python
Daily AtCoder # 18 in Python
Edit fonts in Python
Singleton pattern in Python
File operations in Python
Read DXF in python