[Haskell-cafe] Beginner's speed problem

[Aditya M]

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