Why is pow(a, d, n) so much faster than a**d % n?

by

See the Wikipedia article on modular exponentiation. Basically, when you do a**d % n, you actually have to calculate a**d, which could be quite large. But there are ways of computing a**d % n without having to compute a**d itself, and that is what pow does. The ** operator can’t do this because it can’t “see into the future” to know that you are going to immediately take the modulus.

More Related Contents:

  1. Why shouldn’t I use PyPy over CPython if PyPy is 6.3 times faster?
  2. What is the fastest and pythonic way to generate a list [(0,0), (0,1), (0,2)…(0,100)]? [closed]
  3. Fastest way to check if a value exists in a list
  4. Get difference between two lists
  5. Why does concatenation of DataFrames get exponentially slower?
  6. Which Python memory profiler is recommended? [closed]
  7. Why does Python code run faster in a function?
  8. A faster strptime?
  9. Roll rows of a matrix independently
  10. Efficient calculation of Fibonacci series
  11. Python string ‘join’ is faster (?) than ‘+’, but what’s wrong here?
  12. Bin elements per row – Vectorized 2D Bincount for NumPy
  13. Why is looping over range() in Python faster than using a while loop?
  14. Vectorized searchsorted numpy
  15. Simple Python Challenge: Fastest Bitwise XOR on Data Buffers
  16. Why is numpy.array so slow?
  17. Efficient evaluation of a function at every cell of a NumPy array
  18. why isn’t numpy.mean multithreaded?
  19. Why is Collections.counter so slow?
  20. Python built-in sum function vs. for loop performance
  21. Any way to speed up Python and Pygame?
  22. Are NumPy’s math functions faster than Python’s?
  23. matplotlib savefig performance, saving multiple pngs within loop
  24. Is there a way to circumvent Python list.append() becoming progressively slower in a loop as the list grows?
  25. Speed up writing to files
  26. Efficiently replace elements in array based on dictionary – NumPy / Python
  27. What are the differences between bool() and operator.truth()?
  28. improving python code in Monte Carlo simulation
  29. What is the most efficient way of doing square root of sum of square of two numbers?
  30. Python if vs try-except

Leave a Comment