Daniel Fischer daniel.is.fischer at web.de
Thu Dec 3 19:55:05 EST 2009

```Am Donnerstag 03 Dezember 2009 06:52:01 schrieb 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:
> >> > 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.

Yes. Except there's not much finding to be done, you can pretty much write it down
immediately.

But I underestimated the slowness of String IO, so it's not gaining you terribly much
unless you resort to ByteString IO.
As an indication, for files containing 20.9 million, 2.85 million, 25942 (a,b) pairs
respectively:
ByteString + shortcut: 4.6 seconds, 0.66 seconds,  0.00 seconds
ByteString + modular exponentiation: 49.2 seconds, 6.74 seconds, 0.06 seconds
String + shortcut: 262 seconds, 35.04 seconds, 0.33 seconds
String + modular exponentiation: 303 seconds, 40.73 seconds, 0.38 seconds

(Note: I have tweaked the String IO, using

main = fmap lines getContents >>= putStr . unlines . (map doit) . tail

and modified doit (returns a String now, is a little stricter, calls words line only once;
also read - for the base, I use (digitToInt . last), it's much faster than read)

1. With "replicateM n getLine" or "sequence \$ take n \$ repeat getLine", the entire input
must be read in before processing can start. Firstly that's slower and secondly it needs a
lot of memory - more than I have, for the larger files.
2. (putStr . unlines) is faster than mapM_ putStrLn.

It could be tweaked more, but that wouldn't gain nearly as much as switching to
ByteString.)

So with String IO, in either method the overwhelming part of the time is used for IO (and
read), in comparison, the algorithmic difference pales. With ByteString IO, the
algorithmic difference stands out.

>
> 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.

??? without the LANGUAGE pragma, it would give a parse error, so you can't have forgotten
that. But in

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
| otherwise = lastdigit ( (a*a) `rem` 10 ) (b `quot` 2) ((a*c) `rem` 10)

there is simply no possibility for a pattern match error (other than having one argument
bottom). I'm flabbergasted.

> Is its only effect evaluating c instead of plain substitution?

Yes, it keeps c evaluated instead of building a thunk. You can get pretty much the same
effect by having

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
| otherwise = lastdigit ( (a*a) `rem` 10 ) (b `quot` 2) \$! ((a*c) `rem` 10)

using strict application on the last argument when it is modified.

```