10
\$\begingroup\$

Possible improvements I see are take lastdigit_num and implement arr_{lastdigit_num} since the math behind this is common for most (integers with cyclicity 4 or 2 common to them) integers and reduces repetitive if statements.

For example if num = 23423, then lastdigit_num = 3 and arr_{lastdigit_num} is directly linked to 3 rather than having a separate if statement for 3 or any other digit with common cyclicity.

But I am not able to implement this in the code.

num = int(input("Enter number: "))

lastdigit_num = int(repr(num)[-1])

exp = int(input("Enter exponent: "))

lastdigit_exp = int(repr(exp)[-1])
last2digit_exp = 10*int(repr(exp)[-2])+int(repr(exp)[-1])

mod_exp_2_3_7_8 = last2digit_exp % 4

if lastdigit_exp % 2 == 1:
    mod_exp_4_9 = 1
else:
    mod_exp_4_9 = 0

arr_2 = [2,4,8,6]
arr_3 = [3,9,7,1]
arr_4 = [4,6]
arr_7 = [7,9,3,1]
arr_8 = [8,4,2,6]
arr_9 = [9,1]

if lastdigit_num == 0:
    print(f"Last digit of {num}^{exp} is 0.")

elif lastdigit_num == 1:
    print(f"Last digit of {num}^{exp} is 1.")

elif lastdigit_num == 2:
    print(f"Last digit of {num}^{exp} is {arr_2[mod_exp_2_3_7_8 - 1]}.")
    
elif lastdigit_num == 3:
    print(f"Last digit of {num}^{exp} is {arr_3[mod_exp_2_3_7_8 - 1]}.")

elif lastdigit_num == 4:
    print(f"Last digit of {num}^{exp} is {arr_4[mod_exp_4_9 - 1]}.")

elif lastdigit_num == 5:
    print(f"Last digit of {num}^{exp} is 5.")

elif lastdigit_num == 6:
    print(f"Last digit of {num}^{exp} is 6.")

elif lastdigit_num == 7:
    print(f"Last digit of {num}^{exp} is {arr_7[mod_exp_2_3_7_8 - 1]}.")

elif lastdigit_num == 8:
    print(f"Last digit of {num}^{exp} is {arr_8[mod_exp_2_3_7_8 - 1]}.")

elif lastdigit_num == 9:
    print(f"Last digit of {num}^{exp} is {arr_9[mod_exp_4_9 - 1]}.")
\$\endgroup\$
0

4 Answers 4

8
\$\begingroup\$

As N3buchadnezzar notes, Python's built-in pow function already supports modular exponentiation. So, in practice, the correct and idiomatic way to find the last digit of \$a^b\$ for any integers \$a\$ and \$b\$ in Python is:

last_digit = pow(a, b, 10)

If you're doing this as a learning exercise and don't want to use the built-in solution, I would make a bit of a "frame challenge" and recommend that you implement a general modular exponentiation algorithm that works for any modulus, not just 10. Such algorithms actually have practical uses e.g. in cryptography, whereas using string manipulation and hardcoded remainder rules to find the last base-10 digit does not, making it a much more useful pedagogical exercise.


As this is (presumably) a learning exercise, I would encourage you to come up with your own algorithm and implementation rather than simply adapting an algorithm developed by someone else. Specifically, what you should do is:

  1. Sketch an implementation of an efficient exponentiation algorithm, such as exponentiation by squaring.

  2. Modify the algorithm to reduce any intermediate results modulo 10 (or rather modulo \$m\$, where \$m\$ is an argument to the function) at suitable points so that they cannot grow too large. As a practical goal, you should aim to keep all your intermediate values (excluding the exponent) smaller that \$m^2\$. (Keeping intermediate values below \$m\$ is also possible, but requires you to implement custom modular addition and multiplication routines. For small values of \$m\$ this is probably not worth doing.)

For step 2, remember that modular reduction distributes over addition and multiplication, in the sense that $$(a + b) \bmod m = ((a \bmod m) + b) \bmod m$$ and $$(a \times b) \bmod m = ((a \bmod m) \times b) \bmod m.$$ (Or, in Python code, (a + b) % m == ((a % m) + b) % m and (a * b) % m == ((a % m) * b) % m.)

Thus, if you have an integer variable that you're only going to be multiplying or adding integers to, and you know that you're going to take the remainder modulo \$m\$ of it at the end of your code, you can also safely reduce it modulo \$m\$ at any point during your algorithm without changing the remainder.

Once you have that algorithm working, feel free to post it here for another round of review. :)


Ps. In cases where the exponent may be significantly larger than the modulus, you could also make use of the identity $$a^b \bmod m = a^{b \bmod \lambda(m)} \bmod m,$$ where \$\lambda\$ is the Carmichael totient function. For example, \$\lambda(10) = 4\$, so $$a^b \bmod 10 = a^{b \bmod 4} \bmod 10 = (a \bmod 10)^{b \bmod 4} \bmod 10,$$ which your original code makes use of.

Unfortunately computing \$\lambda(m)\$ for arbitrary large \$m\$ can be quite difficult* — in general, it requires factoring \$m\$ into a product of prime numbers. There are, however, a number of special cases where calculating \$\lambda(m)\$ is relatively easy:

  • If \$m\$ is prime, \$\lambda(m) = m-1\$. Determining whether a number is prime is considerably easier than factoring.
  • More generally, if \$m = p^k\$ is a power of an odd prime \$p\$, \$\lambda(m) = p^{k-1}(p-1)\$.
  • If \$m\$ is a power of 2 and at least 8, \$\lambda(m) = \frac m4\$. (As special cases, \$\lambda(2) = 1\$ and \$\lambda(4) = 2\$.) When \$m\$ is given in binary, testing whether it's a power of 2 is extremely trivial.

If the prime factorization of \$m\$ is known, then \$\lambda(m)\$ can be computed based on the rules above and the theorem that if \$a\$ and \$b\$ have no common prime factors, then $$\lambda(ab) = \operatorname{lcm}(\lambda(a), \lambda(b)),$$ where \$\operatorname{lcm}\$ stands for least common multiple. For small and/or highly composite \$m\$, it can be feasible to calculate \$\lambda(m)\$ by factoring \$m\$ and then applying this formula.


*) In particular, if you could calculate \$\lambda\$ efficiently for products of two large primes without knowing those primes, you could break the RSA cryptosystem. So far, however, nobody's managed to figure out an efficient way do that, at least not without using a theoretical quantum computer more advanced than we can currently build.

\$\endgroup\$
14
\$\begingroup\$

There's really no need to convert the inputs to int. We're only using the last digit of a and the last two digits of b. So just check that we don't have any non-digit characters, then convert the last one or two digits to int.

The code produces incorrect results when b is zero. We should start by testing that:

    if b == 0:
        return 1

Instead of the big if/elif chain, we can simplify the code by making arrays for all our digit sequences, and use a to select which array is used. We could make them all the same length:

def last_pow_digit(a, b):
    if b == 0:
        return 1
    digits = [
        [ 0, 0, 0, 0 ],
        [ 1, 1, 1, 1 ],
        [ 6, 2, 4, 8 ],
        [ 1, 3, 9, 7 ],
        [ 6, 4, 6, 4 ],
        [ 5, 5, 5, 5 ],
        [ 6, 6, 6, 6 ],
        [ 1, 7, 9, 3 ],
        [ 6, 8, 4, 2 ],
        [ 1, 9, 1, 9 ],
    ]
    return digits[a % 10][b % 4]

Alternatively, the arrays can be different lengths, and we'd use the length to determine the modular reduction of b:

def last_pow_digit(a, b):
    if b == 0:
        return 1
    digits = [
        [ 0, ],
        [ 1, ],
        [ 6, 2, 4, 8 ],
        [ 1, 3, 9, 7 ],
        [ 6, 4 ],
        [ 5, ],
        [ 6, ],
        [ 1, 7, 9, 3 ],
        [ 6, 8, 4, 2 ],
        [ 1, 9 ],
    ]
    arr = digits[a % 10]
    return arr[b % len(arr)]

I think the first version is simpler, even if it does mean some repetition.

\$\endgroup\$
4
  • 2
    \$\begingroup\$ RE: if b == 0: return 1 Well technically 0^0 is indeterminate. \$\endgroup\$ Jun 22, 2021 at 17:22
  • 2
    \$\begingroup\$ @RBarryYoung With discrete exponents, \$0^0\$ is often defined to be 1. Continuous exponents and complex exponents are different animals, but in this case, the OP is expecting an integer value for exp. \$\endgroup\$
    – AJNeufeld
    Jun 22, 2021 at 18:58
  • 1
    \$\begingroup\$ Although beware that you may have to implement a tiny bit more logic if you try to generalize to other moduli. For example, when computing the last two digits of 2^n, the sequence does eventually enter a loop (as it must for any modulus), but 2 is not in the loop! \$\endgroup\$ Jun 22, 2021 at 20:36
  • 1
    \$\begingroup\$ @RBarryYoung: If you treat 0^0 as undefined behaviour for your program, you're allowed to do whatever you want in that case, including returning 1. I guess the mathematically correct way to handle it would be throwing an exception, though, or returning some kind of NaN. \$\endgroup\$ Jun 23, 2021 at 6:04
11
\$\begingroup\$

Why not just use Python's builtin pow? It takes in a third optional argument the modulo, so all you need to get the last digit would be pow(a, b, 10). You can see here for an explanation of how it works. It is much, much faster to do this in binary.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ wouldn't that be slower? \$\endgroup\$
    – sato
    Jun 23, 2021 at 4:55
  • 3
    \$\begingroup\$ I must admit I posted this before analyzing your answer in depth. After timing your answer versus pow, the latter still wins for most sensible inputs 5s vs 3s for most sensible inputs. Toby's is faster because yours uses string conversions. I would still, as a general principle, strongly encourage you to use builtins whenever possible. 1) to avoid bugs (yours crashes if exp is a single digit 2) scalability what if you wanted to find the last 3 digits? pow(a, b, 1000). If this is for learning then go ahead, but for production code? builtins. \$\endgroup\$ Jun 23, 2021 at 5:26
  • \$\begingroup\$ this was mainly for learning modular arithmetic but implementing it in code \$\endgroup\$
    – sato
    Jun 23, 2021 at 7:56
2
\$\begingroup\$

Since you stated in a comment that your aim was to learn modular arithmetic, you should certainly use it instead of string operations:

num = int(input("Enter number: "))

lastdigit_num = num % 10

exp = int(input("Enter exponent: "))

lastdigit_exp = exp % 10
last2digit_exp = exp % 100

...

This makes your code more readable while reducing unnecessary operations.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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