How did Python implement the built-in function pow()?

by

If a, b and c are integers, the implementation can be made more efficient by binary exponentiation and reducing modulo c in each step, including the first one (i.e. reducing a modulo c before you even start). This is what the implementation of long_pow() does indeed. The function has over two hundred lines of code, as it has to deal with reference counting, and it handles negative exponents and a whole bunch of special cases.

At its core, the idea of the algorithm is rather simple, though. Let’s say we want to compute a ** b for positive integers a and b, and b has the binary digits b_i. Then we can write b as

b = b_0 + b1 * 2 + b2 * 2**2 + ... + b_k ** 2**k

ans a ** b as

a ** b = a**b0 * (a**2)**b1 * (a**2**2)**b2 * ... * (a**2**k)**b_k

Each factor in this product is of the form (a**2**i)**b_i. If b_i is zero, we can simply omit the factor. If b_i is 1, the factor is equal to a**2**i, and these powers can be computed for all i by repeatedly squaring a. Overall, we need to square and multiply k times, where k is the number of binary digits of b.

As mentioned above, for pow(a, b, c) we can reduce modulo c in each step, both after squaring and after multiplying.

More Related Contents:

  1. Evenly distributing n points on a sphere
  2. What is the best way to get all the divisors of a number?
  3. Algorithm to find which number in a list sum up to a certain number
  4. How to find integer nth roots?
  5. Getting the subsets of a set in Python
  6. counting combinations and permutations efficiently
  7. Fastest way to list all primes below N
  8. Sieve of Eratosthenes – Finding Primes Python
  9. Check if a number is a perfect square
  10. Quicksort with Python
  11. Generate all permutations of a list without adjacent equal elements
  12. how to split an iterable in constant-size chunks
  13. How can you determine a point is between two other points on a line segment?
  14. How do I generate all permutations of a list?
  15. Modular multiplicative inverse function in Python
  16. Representing and solving a maze given an image
  17. How can I use numpy.correlate to do autocorrelation?
  18. Python program to check matching of simple parentheses
  19. Efficiently detect sign-changes in python
  20. Gauss-Legendre Algorithm in python
  21. How do I find the distance between two points? [closed]
  22. Subset sum Problem
  23. What algorithm does Python’s built-in sort() method use?
  24. Equivalent of `polyfit` for a 2D polynomial in Python
  25. Get all numbers that add up to a number
  26. Python: maximum recursion depth exceeded while calling a Python object
  27. Python pi calculation?
  28. Calculating the angle between two vectors in Python
  29. Sieve of Eratosthenes – Primes between X and N
  30. How do you get the next value in the floating-point sequence? [duplicate]

Leave a Comment