I'm solving Last digit of a huge number in Codewars.
I managed to find out a way to calculate odd number ^ odd number and odd number ^ even number. However I got stuck in even ^ even/odd as the relation between the number and its power's mod is not obvious.
Here's what I managed to get:
lastDigit :: [Integer] -> IntegerlastDigit = (`rem` 10) . gowherego [] = 1go [x] = xgo (x : y : r)| odd x && odd y = x ^ (go (y : r) `rem` (x + 1))| odd x && even y = x ^ (foldMod y (go r) (x + 1))| otherwise = -- any hint?foldMod :: Integer -> Integer -> Integer -> IntegerfoldMod _ 0 _ = 1foldMod base 1 modulo = base `rem` modulofoldMod base power modulo = (base * foldMod base (power -1) modulo) `rem` moduloCan anyone give some hints on how to do about the even cases?
Best Answer
I recommend rethinking your approach, and beginning with a more general function. Specifically, can you compute
powMod :: Integer -> [Integer] -> Integerwhere powMod base exponents computes the exponential tower described in the problem mod base? Note that when you recurse, you will recurse with a different base -- because the cycle lengths of the various first exponents are not necessarily all divisors of base. For example, in base 10, any first exponent with a last digit of 7 cycles every four goes, not every ten; the last digit of the powers goes like this:
x 0 1 2 3 4 5 6 77^x `mod` 10 1 7 9 3 1 7 9 3You'll also want to watch out for situations where the first exponent is not itself in the eventual cycle that gets reached; for example, in base 4, we have:
x 0 1 2 3 4 5 6 72^x `mod` 4 1 2 0 0 0 0 0 0So you can't look at just x `mod` 1 and infer from it what 2^x `mod` 4 is, even though the cycle length is 1. (There are other examples, like 2^x `mod` 12, where the cycle is longer than 1 and still doesn't have the original 2 in it.)
You do not need to calculate the entire number to know the last digit, there are fast, and less fast approaches that can calculate the last digit without having to worry about all the other digits.
A simple approach that can calculate ab in O(log b) time is by making use of the following equivalence:
(a×b) mod m = ((a mod m) × (b mod m)) mod m.
This means we can each time calculate the last digit and work with that. It thus means that as long as we can represent all numbers up to 81, we can calculate the ab mod m powMod m a b:
powMod :: Int -> Int -> Int -> IntpowMod m = gowhere go _ 0 = 1go a b | even n = r| otherwise = (x * r) `mod` mwhere r = go ((a*a) `mod` m) (div b 2) `mod` mIf we assume we can calculate modulo, divide by two, check if a value is even, etc. in constant time, this runs in O(log b).
But we can even do this faster by looking for cycles. Imagine that we have to calculate a power of 7, then 7^0 is 1, 7^1 is 7, 7^2 mod 10 = 9, etc. We can make a table with multiplications:
× │ 0 1 2 3 4 5 6 7 8 9──┼─────────────────────0 │ 0 0 0 0 0 0 0 0 0 01 │ 1 2 3 4 5 6 7 8 92 │ 4 6 8 0 2 4 8 63 │ 9 2 5 8 1 4 74 │ 6 0 4 8 2 65 │ 5 0 5 0 56 │ 6 2 8 47 │ 9 6 38 | 4 29 | 1
If we thus look at the last digit for a power of 7, we see that for:
power │ │ last digit──────────────────────────0 │ │ 11 │ 7*1 │ 72 │ 7*7 │ 93 │ 7*9 │ 34 │ 7*3 │ 1
This thus means that there is a cycle, indeed, after each multiplication with 7, we move to the next state, and thus obtain the following graph:
1 → 7 → 9 → 3↖_______________/This thus means that the cycle has a length of four. It thus means that if we have to calculate 7 to the power of for example 374, then we know that these are 93 cycles of length four that have thus no impact, and two extra moves, we thus know that the last digit of 7393 is 9, without having to compute this number. Since such cycles has a maximum length of 10, this can thus done in constant time do determine the last digit of the decimal number.