Printing the last two digits of an exponential calculation

Question

I am trying to create a program where a user inputs two numbers - a base and an exponent, while exponent is a binary number. Then prints out the last two digits of the result. My code is working well, but according to the time execution it is not the fastest way to do it. I read a little about using Horner's method, is there a way to use it here? If so, how?

base = int(input())
exponent = int(input())

def binaryToDec(binary): 
    decimal, i = 0, 0
    while(binary != 0): 
        dec = binary % 10
        decimal = decimal + dec * pow(2, i) 
        binary = binary//10
        i += 1
    return decimal
exponent = binaryToDec(exponent)
result = base ** exponent
result = abs(result)%100
print(result)

For example, the output of 3 and 1010 should be 49.

Another example:

Input:

111111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111111

Output:

31

I expect the program to work faster in doing so, how can I do this?

Answer 1

• document your code. In the code.
  Python got it right with docstrings:
  The laziest copying of a function includes its docstring, ready for introspection.
• document what everything is there for wherever not blatantly obvious.
  This would include the problem description - if it was in the source code, one might notice that the statements use an abs() where the description never mentions it.
• let a tool help you to follow the Style Guide for Python Code.
• your naming is OK (with the exception of result - there should be digits of power or modulus of power)
• your binaryToDec() is too weird to mention - just try to describe what it does accomplish, and how.
• read the requirement specification carefully. If possible, fix in writing how to check requirements are met.
  You mention that your implementation is not the fastest way to do [modular exponentiation]: is there an upper limit on execution time? Rank among course-mates?
  The way the exponent is specified looks constructed to head you to use one particular way to implement exponentiation.
• know your python library. Mast commented the existence of a built-in - for conversion of strings to numbers using a non-default base, more likely than not.

How not to do more than hardly avoidable (/be "fast"):
For starters, only the last d digits of a number have any influence on the last d digits of its integral powers represented using the same base b.
Moreover, those last d digits become cyclic with b**d an integral multiple of cycle length - just watch out for things like 2**100.

Answer 2

You say the exponent is written in binary, but then you're reading it as decimal, call it binary (even though it's a number, not a string, so it's neither binary nor decimal), somehow convert it, and call the result decimal (again not true, as it's a number, not a string). Just read it as binary instead of all of that.

For efficiency, don't compute the whole power. That's highly inefficient, both time and space. Use pow appropriately, making it work modulo 100 during the exponentiation so it's super fast.

The whole efficient solution:

base = int(input())
exponent = int(input(), 2)
print(pow(base, exponent, 100))