# My Weblog

## Blog about programming and math

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.

July 8, 2010 - Posted by | Programming