How can I resolve timeout problem with my task called "Last digit of A large number"?

Question

Basically, I have written such a program which could acquire the last digit of large numbers. However, at a certain point it crashed due to timeout. Actually, it doesn't have an exact error popped up but still takes a whole lot more time to process the entire code.

Here is my program:

def last_digit(n1, n2):
    number = n1**n2
    number_list = str(number).split()
    return number_list[0][-1]

print(last_digit(3715290469715693021198967285016729344580685479654510946723, 68819615221552997273737174557165657483427362207517952651))

I was expecting to get the last digit of the equation. I wanna get rid of timeout and quickly solve that problem. I am open to all suggestions thanks in advance!

Answer 1

3715290469715693021198967285016729344580685479654510946723 ** 68819615221552997273737174557165657483427362207517952651 is too much to calculate. If you try, it'll never finish. You can try with much smaller numbers and gradually increase them to get a sense of the problem.

The task basically requires some very specific knowledge, not general programming skills. You want to use the pow function. Take a look at the docs: https://docs.python.org/3/library/functions.html#pow

You may also want to look up "python mod" to understand what % means, although the point is not to use %, but something equivalent.

Answer 2

Raising a large number to a large power is a very expensive operation. Since we only need to determine the last digit of the result, we can only raise this last digit to the required power. But, if the power value is very large, then this operation will also be very costly. For power values starting from 20, you can notice such a pattern, the last digit is repeated with a period of 4 power values, so it is enough to raise the last digit to a power modulo 4. To avoid a zero power value for numbers that are multiples of 4, you can add the number 4 to the modulo.

def last_digit(x, p):
    if p == 0: return 0            # any number to the power of 0 is 1
    if x > 9: x = x % 10           # if the number is greater than 9, take the last digit from it
    if x == 0 or x == 1: return x  # 0 and 1 are equal to themselves to any power
    if p > 19: p = p % 4 + 4       # if the degree is greater than or equal to 20, take it modulo 4
    y = x ** p                     # the power is here
    if y > 9: y = y % 10           # if the number of digits in the result is greater than 1, take the last digit
    return y

Answer 3

I did something like this:

def last_digit(n1, n2):
    if n2 == 0:
        return 1

    cycle = [n1 % 10]
    while True:
        nxt = (cycle[-1] * n1) % 10
        if nxt == cycle[0]:
            break
        cycle.append(nxt)
    return cycle[(n2 - 1) % len(cycle)]

it worked perfectly in the end.