Created
January 14, 2018 11:00
-
-
Save RaphaelAslanian/7fc2b87084eabf008c53b44a778f9ed7 to your computer and use it in GitHub Desktop.
Last two digits of x^n
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def last_digits_power(n): | |
"""Display the last two digits of n to the power of n""" | |
result = last_digits(n, n) | |
result_tens, result_units = result // 10, result % 10 | |
print("First digit: {}, Second digit: {}".format(result_tens, result_units)) | |
return result_tens, result_units | |
def last_digits(base, exponent): | |
""" | |
Computes the modulo 100 of <base> to the power of <exponent>. | |
Computation method documentation found here: | |
http://learningroots.in/cat-and-omet/quant/last-two-digits-cyclicity/ | |
https://www.justquant.com/numbertheory/last-two-digits-of-large-number/ | |
""" | |
if not (isinstance(base, int) and isinstance(exponent, int)): | |
raise TypeError("Base and exponent should be of type int, received: {} and {}.".format(type(base), type(exponent))) | |
if base < 0 or exponent < 0: | |
raise ValueError("Base and exponent should be positive") | |
# All hundreds', thousands' digits and higher are irrelevant to compute the last two digits. | |
base = base % 100 | |
if exponent == 0: | |
return 1 | |
elif exponent == 1: | |
return base | |
# If base ends up with at least two zeros, then the last two digits are always two zeros. | |
if base == 0: | |
return 0 | |
# The method is based on multiplication cycles, and differentiates cases on the last digit of the base. (cf doc) | |
case = base % 10 | |
if case == 1: | |
return (((base // 10) * (exponent % 10)) * 10 + 1) % 100 | |
elif case in {0, 2, 4, 6, 8}: | |
base_part_odd = base // 2 | |
base_part_odd = last_digits(base_part_odd, exponent) | |
base_part_even = find_power_two(exponent) | |
return digit_multiply(base_part_odd, base_part_even) | |
elif case in {3, 7}: | |
base_square = digit_multiply(base, base) | |
base_fourth = digit_multiply(base_square, base_square) | |
exponent, rest = exponent // 4, exponent % 4 | |
base_fourth = last_digits(base_fourth, exponent) | |
base_remaining = (base ** rest) % 100 | |
return digit_multiply(base_fourth, base_remaining) | |
elif case == 9: | |
base_square = (base * base) % 100 | |
exponent, rest = exponent // 2, exponent % 2 | |
base_main = last_digits(base_square, exponent) | |
return digit_multiply(base, base_main) if rest == 1 else base_main | |
elif case == 5: | |
exponent_oddness = (exponent % 2) == 1 | |
tens_oddness = ((base // 10) % 2) == 1 | |
return 75 if exponent_oddness and tens_oddness else 25 | |
def find_power_two(exponent): | |
"""Computes mod 100 of a power of 2""" | |
exponent_little = exponent % 10 | |
exponent_big = exponent - exponent_little | |
res = (2 ** exponent_little) % 100 | |
if exponent_big > 0: | |
eveness = (exponent_big / 10 % 2) == 0 | |
return digit_multiply(76 if eveness else 24, res) | |
else: | |
return res % 100 | |
def digit_multiply(first, second): | |
"""Computes mod 100 of a product""" | |
first = first % 100 | |
second = second % 100 | |
value = (first * second) % 100 | |
return value |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import unittest | |
from powers import last_digits | |
class TestDigitFunctions(unittest.TestCase): | |
def test_small_numbers(self): | |
for i in range(1, 20): | |
self.assertEqual((i ** i) % 100, last_digits(i, i)) | |
def test_medium_numbers(self): | |
nbrs = [117, 768, 2339] | |
for i in nbrs: | |
self.assertEqual((i ** i) % 100, last_digits(i, i)) | |
def test_big_numbers(self): | |
nbrs = [12349, 112349] | |
for i in nbrs: | |
self.assertEqual((i ** i) % 100, last_digits(i, i)) | |
def test_exception(self): | |
self.assertRaises(TypeError, last_digits, "hello", 3) | |
self.assertRaises(TypeError, last_digits, 3, "hello") | |
self.assertRaises(ValueError, last_digits, -1, 3) | |
self.assertRaises(ValueError, last_digits, 3, -1) | |
if __name__ == '__main__': | |
unittest.main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment