Binary exponentation with modulo

Question

I have implemented binary exponentiation. Is this good?

def quad_pow(base, exponent, modul): 
 alpha = (bin(exponent).replace('0b', ''))[::-1]
 a = 1
 b = base
 for i in range(0, len(alpha)):
 if int(alpha[i]) == 1:
 a = (a * b) % modul
 b = (b*b) % modul
 return a

• AJNeufeld: Are you trying to "reinvent-the-wheel"? If not, the most efficient way is pow(base, exponent, modul) (Python 3.x)
• MrFish: No, I am not. I am aware that there are those functions, but programming doesn't mean that you use those default finished things. I was interested in how to programm this mathematical algorithm.
• AJNeufeld: "Reinventing the wheel" is a perfectly sound practice; especially when trying to learn programming, or understanding algorithms. We even have a tag for that.

Answer 1

One set of parenthesis are unneeded in this expression:

alpha = (bin(exponent).replace('0b', ''))[::-1]

You could write this as:

alpha = bin(exponent).replace('0b', '')[::-1]

---

Using [::-1] to reverse the string is nice, but using replace('0b', '') to remove the "0b" from the start first is unnecessary. Using the end field of [start:end:step] would work ... you want to end just before the first character:

alpha = bin(exponent)[:1:-1]

---

Conversion from a string ("0" and "1") to an integer (0 and 1) is unnecessary when you are just comparing the result to the integer 1. So instead of:

 if int(alpha[i]) == 1:

you could write:

 if alpha[i] == "1":

---

When you loop over a string, character by character (or any ordered container element by element), using:

for i in range(0, len(alpha)):
 if alpha[i] == "1":
 ...
 ...

is an anti-pattern in Python. You should loop directly over the container:

for character in alpha:
 if character == "1":
 ...
 ...

If you need the element and the index, you should use enumerate:

for i, character in enumerate(alpha):
 ...

but that is not necessary here.

---

Updated code, with type hints and an example """docstring""":

def quad_pow(base: int, exponent: int, modul: int) -> int:
 """
 Efficiently compute (base ^ exponent) % modul
 Parameters:
 base: The value to raise to the exponent
 exponent: The exponent to raise the base to
 modul: The modulus to compute the resulting value in
 Returns:
 The base raised to the exponent, modulo the given modulus
 """
 alpha = bin(exponent)[:1:-1]
 a = 1
 b = base
 for character in alpha:
 if character == "1":
 a = (a * b) % modul
 b = (b * b) % modul
 return a

---

PEP-8 Note:

Binary operators should have a space on either side, so (b*b) should be written (b * b).

---

See also harold's answer for avoiding the conversion of the exponent to a string.

Answer 2

The string manipulation is avoidable, by working with bits of the exponent directly:

def quad_pow(base, exponent, modul): 
 a = 1
 b = base
 while exponent:
 if exponent & 1:
 a = (a * b) % modul
 b = (b * b) % modul
 exponent >>= 1
 return a