3
\$\begingroup\$

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?

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Are you aware Python has an in-built function for this? \$\endgroup\$
    – Mast
    Commented Oct 26, 2019 at 16:14
  • 1
    \$\begingroup\$ What are the two least significant digits of 101**n and 9876543201**n? \$\endgroup\$
    – greybeard
    Commented Oct 26, 2019 at 17:40
  • \$\begingroup\$ @Mast for the method? \$\endgroup\$
    – Hemal
    Commented Oct 26, 2019 at 18:26
  • \$\begingroup\$ @greybeard how can i check this? \$\endgroup\$
    – Hemal
    Commented Oct 26, 2019 at 18:27
  • \$\begingroup\$ The current question title, which states your concerns about the code, applies to too many questions on this site to be useful. The site standard is for the title to simply state the task accomplished by the code. Please see How do I ask a good question? for examples, and revise the title accordingly. \$\endgroup\$
    – Martin R
    Commented Oct 26, 2019 at 18:56

2 Answers 2

1
\$\begingroup\$
  • 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.

\$\endgroup\$
1
  • \$\begingroup\$ Without change of base, only the last d digits of a number have any influence on the last d digits of its integral powers, products, sums, differences - propagation in direction of lower significance starts only with division. \$\endgroup\$
    – greybeard
    Commented Nov 5, 2019 at 9:14
1
\$\begingroup\$

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))
\$\endgroup\$
1
  • \$\begingroup\$ Hmm, just realized this question is old. Was one of the Top Questions on the front page, due to "modified 1 hour ago Community♦ 1". Not sure what that means. I don't see any modification... \$\endgroup\$ Commented Jul 30, 2020 at 12:02

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.