In Python, I am trying to figure out how to find the last three digits of a number that is the result of 2^(a^b) with a and b as the imput values. It handles input values up to 6, 6 without slowing down, but once it gets to 7, 7 it becomes very slow, and 8, 8 just doesnt work. I was wondering if there was some kind of mathematical shortcut or something to get the last three digits faster. Also, I am kind of new to stack overflow, so I don't know if I am asking this in the right place. Also, I am using replit if that changes anything. (This is for school and I would really appreciate help)
def last_three(a, b):
num = 2 ** (a ** b)
string = str(num)
length = len(string)
print (length)
new_string = ''
new_string = string[length - 3]
new_string = string[length - 2]
new_string = string[length - 1]
return int(new_string)
CodePudding user response:
I realized that it is not the equation that is slow, it was the fact that is was converting it to a string, finding the length, and indexing the last 3 digits. One of the comments told me to do 2^(a^b) % 1000 to get the solution, and it worked. Thank you all for the feedback.
CodePudding user response:
This is a common trick played by university professors. 2^64 is more than the known number of stars in the universe. This is definitely a Big-O time complexity issue :
https://www.geeksforgeeks.org/analysis-algorithms-big-o-analysis/