[Haskell-cafe] Beginner's speed problem
Aditya M
aditya87 at gmail.com
Thu Dec 3 00:52:01 EST 2009
Hello
Thanks for all the help!
I only have a couple of questions.
On Thu, Dec 3, 2009 at 03:45, Daniel Fischer <daniel.is.fischer at web.de> wrote:
> 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
More information about the Haskell-Cafe
mailing list