## 2013 in review

The WordPress.com stats helper monkeys prepared a 2013 annual report for this blog.

Here’s an excerpt:

The concert hall at the Sydney Opera House holds 2,700 people. This blog was viewed about

18,000times in 2013. If it were a concert at Sydney Opera House, it would take about 7 sold-out performances for that many people to see it.

## We, after 67 years of Independence

India has been invaded by many emperors since its inception but if we start looking back from colonial era, it is mainly ruled by British from 1757 – 1947. British ruled only here because of our nature to fight with each other[Battle of Plassey]. We were declared as free country on 15 August 1947 and from that day onwards we stand as one big nation. Did we learn anything from our mistakes in the past we committed. Probably not! Out of these 67 years, Indian National Congress is ruling the country for 48 of the 60 years since independence in 1947. Now below are some facts about how we are doing as a nation or we should be proud of

[1]Scams

We are very good at this and those who raised their voice against corruption is either killed or punished[ Satyendra Dubey and Ashok Khemka]. You haven’t seen enough! Our Minister of Home affairs Sushil Kumar Shinde on coal scam “Earlier, the Bofors was a talking point. People forgot about it. Now it is coal. This too will be forgotten. Once hands are washed off coal, they again become clean.” The union minister later said he was just joking. Certainly, this is joke on us that we elected you.

[2] Poverty

Our 33% population earns less than US$ 1.25 per day while 81 % live on less than US$ 2.50 per day[World Bank]. Quoting from The Guardian “A pledge to eliminate poverty has figured prominently in the election campaigns of all of India’s political parties since the country gained independence in 1947. Yet the ruling Congress party – and particularly prime minister Manmohan Singh, labelled as ‘Mr Silent’ for failing to answer questions on the landmark food security bill – is accused of exploiting poverty rather than putting in place effective measures to tackle it”.

[3] Literacy

The literacy rate in India stand to 74.04% in 2011 and the level is well below the world average literacy rate of 84%, and of all nations, India currently has the largest illiterate population. There are many reasons for this but I have a strong believe that lack of strong will power among political leaders to educate their people is the major reason.

[4] Communal violence

It’s very common among India to have a fight on very petty things. We are still fighting with each other for something happened 500 years ago[ RamJamanbhoomi ] and this led to many unfortunate events including Mumbai Bomb blast, Mumbai Riots and emergence of many terrorist groups. One of our leading political party BJP always promises to construct a temple to Rama at the site. They are still not aware that we have already payed a heavy price and lost many beloved ones!

Now why I am writing this ? Today a political party named Aam Aadmi Party formally launched on 26 November 2012 by Arvind Kejriwal defeated the Indian Nation Congress in Delhi elections. This is certainly not a miracle but because of their dedication to clean the Indian politics. Delhi is ruled by Indian Nation Congress for 15 years and Delhi holds the top position in crime against women. In 2012, We had seen the worst crime in Delhi[2012 Delhi gang rape]. Delhi government and Central government tried to downplay the crime but it was the protest of common man which pushed the government to act fast. It was the anger of common man against the corrupt politicians and promise of Arvind Kejriwal to clean the politics which swept away the Indian National Congress from Delhi. I hope Arvind Kejriwal would fulfill his promise to clean the politics and I will remember this day ( 8 December 2013 ) as a day in history which changed the India and Indian Politics.

## Proving the correctness of code using SMT sovler.

SMT solvers are great tool in computer science. One use of these solvers to prove the correctness of code. I wrote Haskell code to compute the inverse of polynomial using extended euclidean algorithm in Galois Field GF ( 2^{n} ). If we try to analyze the code of *inversePolynomial* then every thing is normal except passing the depth parameter. It is unnecessary because we know that recursion is going to terminate. Initially I wrote the code without depth and the program was not terminating so I wrote mail to Levent Erkok and according to him

*Your code suffers from what’s known as the “symbolic termination”. See Section 7.4 of: http://goo.gl/0E7wkm for a discussion of this issue in the context of Cryptol; but the same comments apply here as well. Briefly, when you recurse in inversePoly, SBV does not know when to stop the recursion of both branches in the ite: Thus it keeps expanding both branches ad infinitum.*

Luckily, symbolic termination is usually easy to deal with once you identify what the problem is. Typically, one needs to introduce a recursion depth counter, which would stop recursion when it reaches a pre-determined depth that is determined to be safe. In fact, SBV comes with the regular GCD example that talks about this issue in detail:

I’d recommend reading the source code of the above; it should clarify the problem. You’ll need to find out a recursion-depth that’ll work for your example (try running it on concrete values and coming up with a safe number); and then prove that the bound is actually correct as explained in the above. The recursion depth bound just needs to be an overapproximation: If the algorithm needs 20 iterations but you use 30 as your recursion depth, nothing will go wrong; it’ll just produce bigger code and thus be less efficient and maybe more complicated for the backend prover. Of course, if you put a depth of 18 when 20 is needed, then it will be wrong and you won’t be able to establish correctness.

My verification condition is inverse of inverse of polynomial is same as polynomial. Right now I have no idea about proving the upper bound on depth so I just took 20. If you have any suggestion/comments then please let me know.

import Data.SBV.Bridge.Z3 import Data.Maybe inversePolynomial :: [ Int ] -> [ Int ] -> SWord16 inversePolynomial poly reducer = inversePoly reducer' rem' first' second' depth' where poly' = polynomial poly :: SWord16 reducer' = polynomial reducer :: SWord16 first' = 0 :: SWord16 second' = 1 :: SWord16 depth' = 20 :: SWord16 ( quot', rem' ) = pDivMod poly' reducer' inversePoly :: SWord16 -> SWord16 -> SWord16 -> SWord16 -> SWord16 -> SWord16 inversePoly reducer'' poly'' first'' second'' depth'' = ite ( depth'' .== 0 ||| rem'' .== ( 0 :: SWord16 ) ) ( second'' ) ( inversePoly poly'' rem'' second'' ret ( depth'' - 1 ) ) where ( quot'', rem'' ) = pDivMod reducer'' poly'' ret = pAdd ( pMult ( quot'', second'', [] ) ) first'' isInversePolyCorrect :: SWord16 -> SWord16 -> SBool isInversePolyCorrect poly reducer = inversePoly reducer ( inversePoly reducer rem first second depth ) first second depth .== rem where ( quot, rem ) = pDivMod poly reducer first = 0 :: SWord16 second = 1 :: SWord16 depth = 20 :: SWord16 *Main> showPoly ( inversePolynomial [ 6,4,1,0] [ 8,4,3,1,0] ) "x^7 + x^6 + x^3 + x" *Main> proveWith z3 { verbose=False } $ forAll ["x"] $ \x -> pMod x ( 283 :: SWord16 ) ./=0 ==> isInversePolyCorrect x ( 283 :: SWord16 ) Q.E.D. *Main> proveWith cvc4 { verbose=False } $ forAll ["x"] $ \x -> pMod x ( 283 :: SWord16 ) ./=0 ==> isInversePolyCorrect x ( 283 :: SWord16 ) *** Exception: fd:10: hFlush: resource vanished (Broken pipe) *Main> proveWith yices { verbose=False } $ forAll ["x"] $ \x -> pMod x ( 283 :: SWord16 ) ./=0 ==> isInversePolyCorrect x ( 283 :: SWord16 ) Q.E.D.

## Counting Inversions

First week of algorithm course programming assignment is to compute the number of inversion count of given array. We have a given array A[0...n - 1] of n distinct positive integers and we have to count all the pairs ( i , j ) such that i < j and A[i] > A[j].

1. Brute Force

Brute force idea is very simple. Run two loops and keep counting the respective pairs for which i < j and A[i] > A[j]. The complexity of brute force is O( n^{2} ).

bruteForce :: [ Int ] -> Int bruteForce [] = 0 bruteForce [_] = 0 bruteForce ( x : xs ) = ( length . filter ( x > ) $ xs ) + bruteForce xs *Main> bruteForce [ 3 , 1 , 2] Loading package array-0.4.0.1 ... linking ... done. Loading package deepseq-1.3.0.1 ... linking ... done. Loading package bytestring-0.10.0.0 ... linking ... done. 2 *Main> bruteForce [ 2,3,8,6,1] 5

2. Divide and Conquer

We can modify the merge sort to compute the inversion count. The idea is to compute the inversion count of during the merge phase. Inversion count of array C resulting from merging two sorted array A and B is sum of inversion count of A, inversion count of B and their cross inversion. The inversion count of single element is 0 ( base case ). The only trick is compute the cross inversion. What will be the inversion count of following array if we merge them ?

A = [ 1 , 2 , 3 ]

B = [ 4 , 5 , 6 ]

Clearly 0 because all element of A is less than the first element of B. What is the inversion count of C = [ 4 , 5 , 6 ] and D = [ 1 , 2 , 3 ] ? First element of D ( 1 ) is less than first element of C ( 4 ) so we have total three pairs ( 4 , 1 ) ( 5 , 1 ) ( 6 , 1). Similarly for 2 and 3 ( total 9 inversion count ). It reveals that if we have any element y in D is less than certain element x in C then all the element of A after x will also be greater than y and we will have those many cross inversion counts. More clear explanation. Wrote a quick Haskell code and got the answer.

import Data.List import Data.Maybe ( fromJust ) import qualified Data.ByteString.Lazy.Char8 as BS inversionCnt :: [ Int ] -> [ Int ] -> [ Int ] -> Int -> ( Int , [ Int ] ) inversionCnt [] ys ret cnt = ( cnt , reverse ret ++ ys ) inversionCnt xs [] ret cnt = ( cnt , reverse ret ++ xs ) inversionCnt u@( x : xs ) v@( y : ys ) ret cnt | x <= y = inversionCnt xs v ( x : ret ) cnt | otherwise = inversionCnt u ys ( y : ret ) ( cnt + length u ) merge :: ( Int , [ Int ] ) -> ( Int , [ Int ] ) -> ( Int , [ Int ] ) merge ( cnt_1 , xs ) ( cnt_2 , ys ) = ( cnt_1 + cnt_2 + cnt , ret ) where ( cnt , ret ) = inversionCnt xs ys [] 0 mergeSort :: [ Int ] -> ( Int , [ Int ] ) mergeSort [ x ] = ( 0 , [ x ] ) mergeSort xs = merge ( mergeSort xs' ) ( mergeSort ys' ) where ( xs' , ys' ) = splitAt ( div ( length xs ) 2 ) xs main = BS.interact $ ( \x -> BS.pack $ show x ++ "\n" ) . fst . mergeSort . map ( fst . fromJust . BS.readInt :: BS.ByteString -> Int ) . BS.lines Mukeshs-MacBook-Pro:Puzzles mukeshtiwari$ ghc -fforce-recomp -O2 Inversion.hs [1 of 1] Compiling Main ( Inversion.hs, Inversion.o ) Linking Inversion ... Mukeshs-MacBook-Pro:Puzzles mukeshtiwari$ time ./Inversion < IntegerArray.txt 2407905288 real 0m8.002s user 0m7.881s sys 0m0.038s

I tried to compare this solution with GeeksforGeeks‘s solution written in C and it was a complete surprise to me.

Mukeshs-MacBook-Pro:Puzzles mukeshtiwari$ time ./a.out < IntegerArray.txt Number of inversions are 2407905288 real 0m0.039s user 0m0.036s sys 0m0.002s

Almost 200 times faster! My Haskell intuition told me that I am doing certainly some wrong. I started analyzing the code and got the point. In inversionCnt function, I am doing extra work for computing the length of list u ( O ( n ) ) so rather than doing this extra work, I can pass the length.

import Data.List import Data.Maybe ( fromJust ) import qualified Data.ByteString.Lazy.Char8 as BS inversionCnt :: [ Int ] -> [ Int ] -> [ Int ] -> Int -> Int -> ( Int , [ Int ] ) inversionCnt [] ys ret _ cnt = ( cnt , reverse ret ++ ys ) inversionCnt xs [] ret _ cnt = ( cnt , reverse ret ++ xs ) inversionCnt u@( x : xs ) v@( y : ys ) ret n cnt | x <= y = inversionCnt xs v ( x : ret ) ( pred n ) cnt | otherwise = inversionCnt u ys ( y : ret ) n ( cnt + n ) merge :: ( Int , [ Int ] ) -> ( Int , [ Int ] ) -> ( Int , [ Int ] ) merge ( cnt_1 , xs ) ( cnt_2 , ys ) = ( cnt_1 + cnt_2 + cnt , ret ) where ( cnt , ret ) = inversionCnt xs ys [] ( length xs ) 0 mergeSort :: [ Int ] -> ( Int , [ Int ] ) mergeSort [ x ] = ( 0 , [ x ] ) mergeSort xs = merge ( mergeSort xs' ) ( mergeSort ys' ) where ( xs' , ys' ) = splitAt ( div ( length xs ) 2 ) xs main = BS.interact $ ( \x -> BS.pack $ show x ++ "\n" ) . fst . mergeSort . map ( fst . fromJust . BS.readInt :: BS.ByteString -> Int ) . BS.lines Mukeshs-MacBook-Pro:Puzzles mukeshtiwari$ time ./Inversion < IntegerArray.txt 2407905288 real 0m0.539s user 0m0.428s sys 0m0.031s

Now 10 times slower and still lot of room for improvement but for now I am happy with this :). You can also try to solve INVCNT. Run this code on Ideone.

## Computing a^n using binary representation of natural number in Agda

While following the Agda tutorial, I wrote this code to compute a^{n}. Not very elegant example probably because I am not expert and still learning about dependent types. Maybe after getting some more experience and knowledge, I will try to prove the correctness and complexity of this algorithm. See the post of Twan van Laarhoven about proving correctness and complexity of merge sort in Agda.

module PowerFunction where data ℕ⁺ : Set where one : ℕ⁺ double : ℕ⁺ → ℕ⁺ double⁺¹ : ℕ⁺ → ℕ⁺ add : ℕ⁺ → ℕ⁺ → ℕ⁺ add one one = double one add one ( double x ) = double⁺¹ x add one ( double⁺¹ x ) = double ( add x one ) add ( double x ) one = double⁺¹ x add ( double x ) ( double y ) = double ( add x y ) add ( double x ) ( double⁺¹ y ) = double⁺¹ ( add x y ) add ( double⁺¹ x ) one = double ( add x one ) add ( double⁺¹ x ) ( double y ) = double⁺¹ ( add x y ) add ( double⁺¹ x ) ( double⁺¹ y ) = double ( add ( add x y ) one ) mult : ℕ⁺ → ℕ⁺ → ℕ⁺ mult x one = x mult x ( double y ) = double ( mult x y ) mult x ( double⁺¹ y ) = add x ( double ( mult x y ) ) pow : ℕ⁺ → ℕ⁺ → ℕ⁺ pow one _ = one pow x one = x pow x ( double one ) = mult x x pow x ( double y ) = pow ( pow x y ) ( double one ) pow x ( double⁺¹ y ) = mult x ( pow ( pow x y ) ( double one ) )

Computing 2 ^ 6

pow ( double one ) ( double ( double⁺¹ one ))

double (double (double (double (double (double one)))))

If you have suggestion then please let me know.

## ZeroMQ for distributed computing.

This post is influenced by ØMQ – The Guide By Pieter Hintjens and translation of codes in Haskell. I suggest you to read The Guide By Pieter Hintjens and if you are interested in Haskell code then you see these codes.

### Request-Reply

The client sends “Accept hello from Client. ” to the server, which replies with “I got you.”. This Haskell server opens a ØMQ socket on port 5555, reads requests on it, and replies with “I got you” to each request.The REQ-REP socket pair is in lockstep. The client issues send and then receive, in a loop (or once if that’s all it needs). Doing any other sequence (e.g., sending two messages in a row) will result in a return code of -1 from the send or receive call.

import System.ZMQ3 import Control.Monad import qualified Data.ByteString.Char8 as BS import Data.ByteString.Lazy.Internal as BL import Data.IORef import Control.Concurrent ( threadDelay ) main = do c <- context s <- socket c Rep bind s "tcp://127.0.0.1:5555" counter <- newIORef 0 forever $ do t <- readIORef counter res <- receive s print res send' s [] ( BL.packChars $ "I got you. " ++ show t ) modifyIORef counter ( +1 ) threadDelay 10000 close s destroy c return ()

Client

import System.ZMQ3 import Control.Monad import qualified Data.ByteString.Char8 as BS import qualified Data.ByteString.Lazy.Internal as BL import Data.IORef import Control.Concurrent ( threadDelay ) main = do c <- context s <- socket c Req connect s "tcp://127.0.0.1:5555" counter <- newIORef 0 forever $ do t <- readIORef counter send' s [] ( BL.packChars $ "Accept hello from Client. " ++ show t ) msg <- receive s print msg modifyIORef counter ( +1 ) threadDelay 10000 return ()

Running a server with two clients.

Mukeshs-MacBook-Pro:ZMQ mukeshtiwari$ ./ZeroMqServer "Accept hello from Client. 0" "Accept hello from Client. 1" "Accept hello from Client. 2" "Accept hello from Client. 3" "Accept hello from Client. 4" "Accept hello from Client. 5" "Accept hello from Client. 6" "Accept hello from Client. 7" "Accept hello from Client. 8" "Accept hello from Client. 9" "Accept hello from Client. 10" "Accept hello from Client. 11" "Accept hello from Client. 12" "Accept hello from Client. 13" "Accept hello from Client. 14" "Accept hello from Client. 15" "Accept hello from Client. 0" "Accept hello from Client. 228" "Accept hello from Client. 1" "Accept hello from Client. 229" "Accept hello from Client. 2" "Accept hello from Client. 230" "Accept hello from Client. 3" "Accept hello from Client. 231" "Accept hello from Client. 4" "Accept hello from Client. 232" First client. Mukeshs-MacBook-Pro:ZMQ mukeshtiwari$ ./ZeroMqClient "I got you. 0" "I got you. 1" "I got you. 2" "I got you. 3" "I got you. 4" "I got you. 5" "I got you. 6" "I got you. 7" "I got you. 8" "I got you. 9" "I got you. 10" "I got you. 11" "I got you. 12" Second client Mukeshs-MacBook-Pro:ZMQ mukeshtiwari$ ./ZeroMqClient "I got you. 228" "I got you. 230" "I got you. 232" "I got you. 234" "I got you. 236" "I got you. 238" "I got you. 240" "I got you. 242" "I got you. 244" "I got you. 246" "I got you. 248" "I got you. 250" "I got you. 252" "I got you. 254" "I got you. 256" "I got you. 258" "I got you. 260" "I got you. 262" "I got you. 264" "I got you. 266"

### Publish-Subscribe

Data publishing server which publishes weather data for zip codes in range 500 and 2000.

import System.ZMQ3 import Control.Monad import qualified Data.ByteString.Char8 as BS hiding ( putStrLn ) import qualified Data.ByteString.Lazy.Internal as BL import Control.Concurrent ( threadDelay ) import System.Random main = do c <- context publisher <- socket c Pub bind publisher "tcp://127.0.0.1:5556" bind publisher "ipc://weather.ipc" forever $ do zipcode <- randomRIO ( ( 500 , 2000 ) :: ( Int , Int ) ) temp <- randomRIO ( 10 , 45 ) :: IO Int relhum <- randomRIO ( 0 , 100 ) :: IO Int putStrLn $ show zipcode ++ " " ++ show temp ++ " " ++ show relhum send' publisher [] ( BL.packChars $ show zipcode ++ " " ++ show temp ++ " " ++ show relhum ) close publisher destroy c return ()

Client who is only interested in two zip codes.

import System.ZMQ3 import Control.Monad import qualified Data.ByteString.Char8 as BS import qualified Data.ByteString.Lazy.Internal as BL import Control.Concurrent ( threadDelay ) import System.Random main = do c <- context subscriber <- socket c Sub connect subscriber "tcp://127.0.0.1:5556" subscribe subscriber ( BS.pack "1000" ) subscribe subscriber ( BS.pack "1010" ) forever $ do update <- receive subscriber print update close subscriber destroy c

Our server is publishing lot of data but client is only interested in two zip codes.

Mukeshs-MacBook-Pro:ZMQ mukeshtiwari$ ./ZeroMqWeatherPubServer 1568 27 85 924 41 46 1461 15 46 1867 44 28 1013 23 100 1052 13 6 1720 45 6 1480 12 94 1852 33 4 1295 20 6 925 18 77 935 37 94 1670 11 6 1285 39 38 1613 44 99 1888 26 62 1011 21 45 993 45 45 1402 26 86 1639 13 65 1285 18 40 1960 38 18 1160 27 39 1374 16 59 665 25 22 Mukeshs-MacBook-Pro:ZMQ mukeshtiwari$ ./ZeroMqWeatherClient "1000 34 89" "1010 19 70" "1010 15 86" "1000 38 57" "1010 12 42" "1000 25 1" "1000 28 78" "1000 25 16" "1000 28 82" "1010 28 98" "1000 12 77" "1010 11 16" "1010 44 14" "1010 12 89" "1000 32 8" "1010 37 55" "1010 17 21" "1000 13 96" "1000 18 51" "1010 16 38" "1000 18 21" "1010 37 60" "1010 17 25" "1000 33 43" "1000 34 44" "1010 33 78" "1010 35 63" "1000 39 50" "1000 45 70" "1000 26 3" "1010 34 12" "1010 26 3" "1000 32 75" "1010 14 68" "1000 44 75" "1010 27 54" "1000 21 39" "1010 12 65" "1010 43 29" "1010 25 60"

### Divide and Conquer

For this problem we will calculate the number of primes less than . Our ventilator will push the task to workers and they will perform the task. After finishing the job, they will send the result back to sink.

import System.ZMQ3 import Control.Monad import qualified Data.ByteString.Char8 as BS import Data.ByteString.Lazy.Internal as BL import Data.IORef import Control.Concurrent ( threadDelay ) main = do c <- context sender <- socket c Push bind sender "tcp://127.0.0.1:5557" sink <- socket c Push connect sink "tcp://127.0.0.1:5558" putStrLn "Press enter when workers are ready." _ <- getChar putStrLn "Sending the task to workers.\n" send' sink [] ( BL.packChars . show $ 0 ) forM_ [ 0..9999 ] $ \ i -> do putStrLn $ "Sending the range [ " ++ show ( 1000 * i + 1 ) ++ " .. " ++ show ( 1000 * i + 1 + 999 ) ++ "] to worker for primality testing." send' sender [] ( BL.packChars . show $ 1000 * i + 1 ) close sink close sender destroy c

Worker for computing the prime number.

import System.ZMQ3 import Control.Monad import qualified Data.ByteString.Char8 as BS import qualified Data.ByteString.Lazy.Internal as BL import Data.IORef import Control.Concurrent ( threadDelay ) import Data.Bits powM :: Integer -> Integer -> Integer -> Integer powM a d n = powM' a d n where powM' a d n | d == 0 = 1 | d == 1 = mod a n | otherwise = mod q n where p = powM' ( mod ( a^2 ) n ) ( shiftR d 1 ) n q = if (.&.) d 1 == 1 then mod ( a * p ) n else p calSd :: Integer -> ( Integer , Integer ) calSd n = ( s , d ) where s = until ( \x -> testBit ( n - 1) ( fromIntegral x ) ) ( +1 ) 0 d = div ( n - 1 ) ( shiftL 1 ( fromIntegral s ) ) rabinMiller::Integer->Integer->Integer->Integer-> Bool rabinMiller n s d a | n == a = True | otherwise = case x == 1 of True -> True _ -> any ( == pred n ) . take ( fromIntegral s ) . iterate (\e -> mod ( e^2 ) n ) $ x where x = powM a d n isPrime::Integer-> Bool isPrime n | n <= 1 = False | n == 2 = True | even n = False | otherwise = all ( == True ) . map ( rabinMiller n s d ) $ [ 2 , 3 , 5 , 7 , 11 , 13 , 17 ] where ( s , d ) = calSd n primeRange :: Integer -> Integer -> [ Bool ] primeRange m n = map isPrime [ m .. n ] main = do c <- context receiver <- socket c Pull connect receiver "tcp://127.0.0.1:5557" sender <- socket c Push connect sender "tcp://127.0.0.1:5558" forever $ do num <- receive receiver let n = read . BS.unpack $ num :: Integer let len = length . filter ( == True ) . primeRange n $ n + 999 putStrLn $ "Received range [ " ++ show n ++ " .. " ++ show ( n + 999 ) ++ " and number of primes in this range is " ++ show len send' sender [] ( BL.packChars . show $ len ) close receiver close sender destroy c

Sink for collecting the results.

import System.ZMQ3 import Control.Monad import qualified Data.ByteString.Char8 as BS import qualified Data.ByteString.Lazy.Internal as BL import Data.IORef import Control.Concurrent ( threadDelay ) main = do c <- context receiver <- socket c Pull bind receiver "tcp://127.0.0.1:5558" m <- receive receiver print m sum <- newIORef 0 forM_ [ 1.. 10000 ] $ \i -> do num <- receive receiver let n = read . BS.unpack $ num :: Integer putStrLn $ "Received a number " ++ show n ++ " from one of worker" modifyIORef sum ( + n ) t <- readIORef sum putStrLn $ "Total number of primes in the range is " ++ show t close receiver destroy c

Running Ventilator, 3 workers and sink

Mukeshs-MacBook-Pro:ZMQ mukeshtiwari$ ./TaskVent Sending the range [ 9992001 .. 9993000] to worker for primality testing. Sending the range [ 9993001 .. 9994000] to worker for primality testing. Sending the range [ 9994001 .. 9995000] to worker for primality testing. Sending the range [ 9995001 .. 9996000] to worker for primality testing. Sending the range [ 9996001 .. 9997000] to worker for primality testing. Sending the range [ 9997001 .. 9998000] to worker for primality testing. Sending the range [ 9998001 .. 9999000] to worker for primality testing. Sending the range [ 9999001 .. 10000000] to worker for primality testing. Task worker - 1 Mukeshs-MacBook-Pro:ZMQ mukeshtiwari$ ./TaskWorkder Received range [ 9978001 .. 9979000 and number of primes in this range is 60 Received range [ 9981001 .. 9982000 and number of primes in this range is 49 Received range [ 9984001 .. 9985000 and number of primes in this range is 69 Received range [ 9987001 .. 9988000 and number of primes in this range is 57 Received range [ 9990001 .. 9991000 and number of primes in this range is 60 Received range [ 9993001 .. 9994000 and number of primes in this range is 71 Received range [ 9996001 .. 9997000 and number of primes in this range is 58 Received range [ 9999001 .. 10000000 and number of primes in this range is 53 Task worker - 2 Mukeshs-MacBook-Pro:ZMQ mukeshtiwari$ ./TaskWorkder Received range [ 9982001 .. 9983000 and number of primes in this range is 69 Received range [ 9985001 .. 9986000 and number of primes in this range is 62 Received range [ 9988001 .. 9989000 and number of primes in this range is 58 Received range [ 9991001 .. 9992000 and number of primes in this range is 57 Received range [ 9994001 .. 9995000 and number of primes in this range is 64 Received range [ 9997001 .. 9998000 and number of primes in this range is 67 Task Worker - 3 Received range [ 9986001 .. 9987000 and number of primes in this range is 59 Received range [ 9989001 .. 9990000 and number of primes in this range is 58 Received range [ 9992001 .. 9993000 and number of primes in this range is 58 Received range [ 9995001 .. 9996000 and number of primes in this range is 62 Received range [ 9998001 .. 9999000 and number of primes in this range is 64 Sink Received a number 53 from one of worker Received a number 67 from one of worker Received a number 64 from one of worker Received a number 52 from one of worker Received a number 59 from one of worker Received a number 58 from one of worker Received a number 58 from one of worker Received a number 62 from one of worker Received a number 64 from one of worker Total number of primes in the range is 664579

First start all the workers and sink and then run ventilator. See more about distributed computing in Haskell Eden and distributed-process. If you have any suggestion then please let me know. Some of the contents and images are taken from Pieter Hintjens‘s tutorial by his permission.

## Missionaries and cannibals problem

In the missionaries and cannibals problem, three missionaries and three cannibals must cross a river using a boat which can carry at most two people, under the constraint that, for both banks, if there are missionaries present on the bank, they cannot be outnumbered by cannibals (if they were, the cannibals would eat the missionaries.) The boat cannot cross the river by itself with no people on board. We can solve this problem using depth first search. Representing the states as number of missionaries, cannibals and boat location in following way.

data Side = Side { missionaries :: Int , cannibals :: Int } deriving ( Show , Eq ) data Loc = L | R deriving ( Show , Eq ) data State = State { left :: Side , right :: Side , bloc :: Loc } deriving ( Show , Eq )

Target is to move every missionaries and cannibals from left to right so our initial state is initialState and final state is finalState.

initialState = State { left = Side 3 3 , right = Side 0 0 , bloc = L } finalState = State { left = Side 0 0 , right = Side 3 3 , bloc = R }

Possible movements

1. move ( 2 , 0 )

2. move ( 1 , 0 )

3. move ( 1 , 1 )

4. move ( 0 , 1 )

5. move ( 0 , 2 )

where move ( M , C ) is movement of M missionaries and C cannibals from one side to other side depending on boat location. If boat location is left then move ( M , C ) is moving M missionaries and C cannibals from left to right and vice versa. Using depth first search, we can explore every possible movement

path :: [ State ] -> [ State ] -> [ State ] path [] vis = reverse vis path ( x : xs ) vis | x == finalState = reverse ( x : vis ) | elem x vis = path xs vis | otherwise = path xs' vis' where vis' = x : vis xs' = ( filter isLegal ( move x ) ) ++ xs

Encoding the moves and testing the legality

move :: State -> [ State ] move ( State ( Side ml cl ) ( Side mr cr ) L ) = [ State ( Side ( ml - 2 ) cl ) ( Side ( mr + 2 ) cr ) R , State ( Side ( ml - 1 ) cl ) ( Side ( mr + 1 ) cr ) R , State ( Side ( ml - 1 ) ( cl - 1 ) ) ( Side ( mr + 1 ) ( cr + 1 ) ) R , State ( Side ml ( cl - 2 ) ) ( Side mr ( cr + 2 ) ) R , State ( Side ml ( cl - 1 ) ) ( Side mr ( cr + 1 ) ) R ] move ( State ( Side ml cl ) ( Side mr cr ) R ) = [ State ( Side ( ml + 2 ) cl ) ( Side ( mr - 2 ) cr ) L , State ( Side ( ml + 1 ) cl ) ( Side ( mr - 1 ) cr ) L , State ( Side ( ml + 1 ) ( cl + 1 ) ) ( Side ( mr - 1 ) ( cr - 1 ) ) L , State ( Side ml ( cl + 2 ) ) ( Side mr ( cr - 2 ) ) L , State ( Side ml ( cl + 1 ) ) ( Side mr ( cr - 1 ) ) L ] isLegal :: State -> Bool isLegal ( State ( Side ml cl ) ( Side mr cr ) y ) | ml == 0 = mr >= cr && cr >= 0 | mr == 0 = ml >= cl && cl >= 0 | otherwise = ml >= cl && mr >= cr && cl >= 0 && cr >= 0

Complete source code ( In case if you are lazy :) )

import Data.List data Side = Side { missionaries :: Int , cannibals :: Int } deriving ( Show , Eq ) data Loc = L | R deriving ( Show , Eq ) data State = State { left :: Side , right :: Side , bloc :: Loc } deriving ( Show , Eq ) initialState = State { left = Side 3 3 , right = Side 0 0 , bloc = L } finalState = State { left = Side 0 0 , right = Side 3 3 , bloc = R } path :: [ State ] -> [ State ] -> [ State ] path [] vis = reverse vis path ( x : xs ) vis | x == finalState = reverse ( x : vis ) | elem x vis = path xs vis | otherwise = path xs' vis' where vis' = x : vis xs' = ( filter isLegal ( move x ) ) ++ xs move :: State -> [ State ] move ( State ( Side ml cl ) ( Side mr cr ) L ) = [ State ( Side ( ml - 2 ) cl ) ( Side ( mr + 2 ) cr ) R , State ( Side ( ml - 1 ) cl ) ( Side ( mr + 1 ) cr ) R , State ( Side ( ml - 1 ) ( cl - 1 ) ) ( Side ( mr + 1 ) ( cr + 1 ) ) R , State ( Side ml ( cl - 2 ) ) ( Side mr ( cr + 2 ) ) R , State ( Side ml ( cl - 1 ) ) ( Side mr ( cr + 1 ) ) R ] move ( State ( Side ml cl ) ( Side mr cr ) R ) = [ State ( Side ( ml + 2 ) cl ) ( Side ( mr - 2 ) cr ) L , State ( Side ( ml + 1 ) cl ) ( Side ( mr - 1 ) cr ) L , State ( Side ( ml + 1 ) ( cl + 1 ) ) ( Side ( mr - 1 ) ( cr - 1 ) ) L , State ( Side ml ( cl + 2 ) ) ( Side mr ( cr - 2 ) ) L , State ( Side ml ( cl + 1 ) ) ( Side mr ( cr - 1 ) ) L ] isLegal :: State -> Bool isLegal ( State ( Side ml cl ) ( Side mr cr ) y ) | ml == 0 = mr >= cr && cr >= 0 | mr == 0 = ml >= cl && cl >= 0 | otherwise = ml >= cl && mr >= cr && cl >= 0 && cr >= 0

Main> path [ initialState ] []

[State {left = Side {missionaries = 3, cannibals = 3}, right = Side {missionaries = 0, cannibals = 0}, bloc = L},State {left = Side {missionaries = 2, cannibals = 2}, right = Side {missionaries = 1, cannibals = 1}, bloc = R},State {left = Side {missionaries = 3, cannibals = 2}, right = Side {missionaries = 0, cannibals = 1}, bloc = L},State {left = Side {missionaries = 3, cannibals = 0}, right = Side {missionaries = 0, cannibals = 3}, bloc = R},State {left = Side {missionaries = 3, cannibals = 1}, right = Side {missionaries = 0, cannibals = 2}, bloc = L},State {left = Side {missionaries = 1, cannibals = 1}, right = Side {missionaries = 2, cannibals = 2}, bloc = R},State {left = Side {missionaries = 2, cannibals = 2}, right = Side {missionaries = 1, cannibals = 1}, bloc = L},State {left = Side {missionaries = 0, cannibals = 2}, right = Side {missionaries = 3, cannibals = 1}, bloc = R},State {left = Side {missionaries = 0, cannibals = 3}, right = Side {missionaries = 3, cannibals = 0}, bloc = L},State {left = Side {missionaries = 0, cannibals = 1}, right = Side {missionaries = 3, cannibals = 2}, bloc = R},State {left = Side {missionaries = 1, cannibals = 1}, right = Side {missionaries = 2, cannibals = 2}, bloc = L},State {left = Side {missionaries = 0, cannibals = 0}, right = Side {missionaries = 3, cannibals = 3}, bloc = R}]

*Main> map bloc . path [ initialState ] $ []

[L,R,L,R,L,R,L,R,L,R,L,R]

If you have any suggestion or comment then please let me know.

## SPOJ Pell (Mid pelling)

Pell (Mid pelling) is related to Pell’s equation. It is similar to Project Euler 66 and SPOJ EQU2. I just wrote the quick solution from mathworld but I found Chakravala method very interesting. Accepted Haskell code.

import qualified Data.ByteString.Char8 as BS import Data.List import Data.Maybe ( fromJust ) continuedFraction :: Integer -> [ Integer ] continuedFraction n = map ( \ ( a , _ , _ ) -> a ) . iterate fun $ ( d , 0 , 1 ) where d = truncate . sqrt . fromIntegral $ n fun ( a0 , p0 , q0 ) = ( a1 , p1 , q1 ) where p1 = a0 * q0 - p0 q1 = div ( n - p1 ^ 2 ) q0 a1 = div ( d + p1 ) q1 pellSolver :: Integer -> BS.ByteString pellSolver n | perfectSqr n = BS.pack. show $ ( -1 ) | otherwise = ( BS.pack . show $ p ) `BS.append` ( BS.pack " " ) `BS.append` ( BS.pack.show $ q ) where d = truncate . sqrt . fromIntegral $ n lst = takeWhile ( /= 2 * d ) . continuedFraction $ n len = length lst r@( x : y : xs ) = take ( if even len then len else 2 * len ) . continuedFraction $ n ( p0 , p1 , q0 , q1 ) = ( x , x * y + 1 , 1 , y ) ( p , _ ) = foldl' compute ( p1 , p0 ) $ xs ( q , _ ) = foldl' compute ( q1 , q0 ) $ xs compute :: ( Integer , Integer ) -> Integer -> ( Integer , Integer ) compute ( p1 , p0 ) a = ( a * p1 + p0 , p1 ) perfectSqr :: Integer -> Bool perfectSqr n = d * d == n where d = truncate . sqrt . fromIntegral $ n readI :: BS.ByteString -> Integer readI = fst . fromJust . BS.readInteger main = BS.interact $ BS.unlines . map ( pellSolver . readI ) . tail . BS.lines

## SPOJ EMAIL ID

Finally solved EMAIL ID using python though it was very hard for me to switch from Haskell to python. While doing this problem, I learned quite a lot about regular expressions, found some cool site like pythontutor and problem solving with python . Accepted code in python.

import re if __name__ == "__main__": n = int ( raw_input() ) c = 1 while c <= n : email = re.findall ( "[a-zA-Z0-9][a-zA-Z0-9._]{4,}@[a-zA-Z0-9]+\.(?:com|edu|org|co\.in)", raw_input() ) t = len ( email ) print 'Case #' + str ( c ) + ': ' + str ( t ) for i in xrange ( t ) : print email[i] c += 1

## My experience with online learning

I am one big confused soul who is always curious for learning. I found Coursera and Udacity very helpful. I try to take as many courses as possible but recently I took the Heterogeneous Parallel Programming by Professor Wen-mei W. Hwu and it was fun course. The video lectures were excellent and assignments were not very hard. They were designed to make us familiar with basics of cuda programming and apart from that I got certificate signed by Professor Wen-mei W. Hwu :). While doing some more research about heterogeneous computing which involves CPU, GPU and FPGA all together in single system, today I found FPGA Programming for the Masses. There are two promising technologies, one from Altera and other is Liquid Metal from IBM.

**Altera OpenCL-to-FPGA Framework**.

Altera proposed a framework for synthesizing bitstreams from OpenCL. The framework consists of a kernel compiler, a host library, and a system integration component. The kernel compiler, based on the open source LLVM compiler infrastructure, synthesizes OpenCL kernel code into hardware. The host library provides APIs and bindings for establishing communication between the host part of the application running on the processor and the kernel part of the application running on the FPGA. The system integration component wraps the kernel code with memory controllers and a communication interface (such as PCIe)

**Liquid Metal**.

The Liquid Metal project at IBM aims to provide not only high-level synthesis for FPGAs,1 but also, more broadly, a single unified language for programming heterogeneous architectures. The project offers a language called Lime, which can be used to program hardware (FPGAs), as well as software running on conventional CPUs and more exotic architectures such as GPUs. The Lime language was founded on principles that eschew the complicated program analysis that plagues C-based frameworks, while also offering powerful programming models that espouse the benefits of functional and stream-oriented programming.

Heterogeneous parallel programming looks very promising but still long way to go. My certificate ;)

.