My Weblog

Blog about programming and math

Last Non zero digit of factorial

Today i found a problem on spoj which asks for finding last non zero digit of factorial of large number [ 10 ^100 ] . After searching a bit , i found couple of links which are quite good and self explanatory 1] comeoncode 2] mathproblem 3] mathpages [ this one contains other nice problems also ] . I implemented the algorithm given on first two links and got TLE but worth sharing this code because today i learned how to use Byte-String instead of String which is quite slower in Haskell. You may check SPOJ section on Haskell Wiki.

import Data.List
import qualified Data.ByteString.Char8 as BS 


helpMod::Integer->Integer->Integer->Integer
helpMod a d n= fun a d where
	fun a 1 = mod a n
	fun a 2 = mod (a^2) n
	fun a d = let
			p=fun (mod (a^2) n) (div d 2)
			q=if odd d then mod (a*p) n else p
		  in mod q n



readInt :: BS.ByteString -> Integer
readInt x = case BS.readInteger x of 
              Just ( i , _ ) -> i 
	      Nothing -> error " upseperable ints "

solve ::Integer -> Integer
solve 0 = 1
solve 1 = 1
solve 2 = 2 
solve 3 = 6
solve 4 = 4
solve n = mod ( ( helpMod 2 q 10 ) * ( solve q ) *( solve r ) )  10 where 
	  ( q , r ) = quotRem n 5 

main = BS.interact $ BS.unlines. map ( BS.pack . show . solve )  . map readInt. BS.lines

Looking forward to implement mathpages algorithm in Haskell.

Advertisements

May 23, 2011 - Posted by | Programming

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: