Hello
Thanks for all the help!
I only have a couple of questions.
On Thu, Dec 3, 2009 at 03:45, Daniel Fischer
Am Mittwoch 02 Dezember 2009 22:44:01 schrieb Don Stewart:
aditya87:
Hi,
I am trying to solve this problem: https://www.spoj.pl/problems/LASTDIG/ It is very simple. Given a and b, return the last digit of a^b. b could be large, so I used logarithmic exponentiation and
Just to mention it, you can do something much much faster for this problem. Something in the microsecond range (if IO is fast enough, millisecond otherwise).
I guess you mean that we can find the cycle that the last digits follow while multiplying repeatedly by a, and then use that. I'll try that next in Haskell!
{-# LANGUAGE BangPatterns #-}
lastdigit :: Int -> Int -> Int -> Int lastdigit 0 0 _ = 1 lastdigit a b !c | even b = lastdigit ( (a*a) `rem` 10 ) (b `quot` 2) c
| b == 1 = (a*c) `rem` 10
However,
| otherwise = lastdigit ( (a*a) `rem` 10 ) (b `quot` 2) (a*c)
This bang pattern (!c) is giving me pattern match errors. Is its only effect evaluating c instead of plain substitution? -- Aditya Manthramurthy