1
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ Are you trying to "reinvent-the-wheel"? If not, the most efficient way is pow(base, exponent, modul) (Python 3.x) \$\endgroup\$
    – AJNeufeld
    Commented Apr 9, 2020 at 14:36
  • \$\begingroup\$ 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. \$\endgroup\$
    – MrFish
    Commented Apr 9, 2020 at 14:58
  • 1
    \$\begingroup\$ "Reinventing the wheel" is a perfectly sound practice; especially when trying to learn programming, or understanding algorithms. We even have a tag for that. \$\endgroup\$
    – AJNeufeld
    Commented Apr 9, 2020 at 15:01

2 Answers 2

3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.