My Weblog

Blog about programming and math

Binary search in Haskell

Now a days i am addicted to Haskell programming and try to learn as much as possible. The best thing to learn a programming language is writing codes. I tried to follow this methodology in my free time and implemented BInary Search and Rabin Miller primality testing .Being a new to Haskell i don’t have idea about efficient codes but it works.

Binary Search Single comparison per iteration Implementation.

bsearch :: [Integer]->Integer->Maybe Int
bsearch ps k = let 
		      n=length ps
		      t=bsearch_ 0 n where 
				bsearch_ lo hi 	| lo>=hi = lo
					      	| ps!!mid <k =  bsearch_ (mid+1) hi
						| otherwise =  bsearch_ lo mid
						where 	mid = div (lo+hi) 2
		                
		in if (t< n && ps!!t==k) then Just t else  Nothing

Rabin Miller Primality Testing

import System.Random  
fun :: Integer->(Integer,Integer)
fun n = f 0 (n-1) where
                    f d m | mod m 2 == 0 = f (d+1) (div m 2)
                          | otherwise =(d,m)

rabinmiller:: Integer-> Integer->  Bool
rabinmiller n a | b0 == 1 || b0== (n-1) = True
                |otherwise = iter (tail b) 
                where
                    (d,m)=fun n
                    b0= mod (a^m)  n
                    b = take (fromIntegral d) $ iterate (\x-> mod (x*x) n) b0
                    iter [] = False
                    iter (x:xs) | x==1 = False
				| x==(n-1) = True
                                | otherwise = iter xs


primetest n | n<2 =  False
            | n==2 = True
            | even n =  False
            | otherwise =testfun n (take 5 $ randomRs (2,n-2) (mkStdGen 3) :: [Integer]) 
            where
                --testfun n []= 
                testfun n (x:xs) | tmp == False =  False
				 | tmp == True =  True
                                 | otherwise = testfun n xs
				 where tmp = rabinmiller n x

Here is slightly different implementation of Rabin MIller which takes only one iteration and bit efficient than previous one.

import System.Random
fun2mk :: Integer->(Integer,Integer)
fun2mk n = let 
		(s,d)= f 0 (n-1) where 
			  f s d | mod d 2 ==0 = f (s+1) (div d 2)
				| otherwise = (s,d)	
	   in (s,d)
rabinmiller :: Integer->Bool
rabinmiller n   | n<2 = False
		| n==2 = True
		| even n = False
		| b0==1 || b0== n' = True
		| otherwise = iter (tail b)
		where 
			n'= n-1
			(k,m)=fun2mk n
			a= head ( take 1 $ randomRs (2,n-2) (mkStdGen 3) :: [Integer])
			b0 = mod (a^m) n
			b= take (fromIntegral k) $ iterate (\x-> mod (x*x) n) b0
			iter []= False
			iter (x:xs) | x==1 = False
				    | x==n'= True
				    | otherwise = iter xs

If you want to run any of the program, save it as filename.hs. Now run GHCI from your command prompt [ i use linux but windows should be also similar ] and type :load filename.hs. If there is no error then it will load all the functions present in your file. To find out element in the list [ binary search in first code ] you can try bsearch [1..100] 10 and it will return the index of element 10. If element is not in the list and program will return Nothing.
If you find something wrong then let me know. I will try to improve the article.

Advertisements

July 8, 2010 - Posted by | Programming

3 Comments »

  1. !! operator takes O(n) time, so there is no any benefit from this implementation of binsearch. You should consider using Data.Array instead of a list.

    Comment by hash | August 12, 2011 | Reply

    • Yes you are correct. I wrote it long time ago when I was learning Haskell . Data.Array gives constant time access to elements so it is perfect for binary search. Thank you pointing out.

      Comment by tiwari_mukesh | August 12, 2011 | Reply

  2. Cool, I was looking for a binary search in Haskell and this is one of the first things that shows up in a search. I’m going to try to convert your bsearch function to one that does a binary search on any ascending function (Ord a)=>(Int -> a), not just on lists or arrays. Seems like it should be pretty straightforward…

    Comment by gcbenison | March 24, 2012 | Reply


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: