[Haskell-cafe] Karatsuba Multiplication Parallel

[Burak Ekici]

Excuse me, in the last post I forgot to send the last version of the code
and some some needed functions.

So sorry for spamming.

Here is the code:

import Control.Parallel
import Control.Parallel.Strategies
import Control.DeepSeq
------

type Strategy a = a -> Main.Eval a

data Eval a = Done a

instance Monad Main.Eval where
    return x = Main.Done x
    Main.Done x >>= k = k x

runEval :: Main.Eval a -> a
runEval (Main.Done a) = a

using :: a -> Main.Strategy a -> a
x `using` strat = Main.runEval (strat x)

rseq :: Main.Strategy a
rseq x = x `pseq` Main.Done x
-- runEval(rseq 100) = 100
--  :t rseq 100 :: Num a => Eval a

rdeepseq :: NFData a => Main.Strategy a
rdeepseq x = rnf x `pseq` return x

rpar :: Main.Strategy a
rpar x = x `par` Main.Done x
-- runEval(rpar 100) = 100
-- :t rpar 100 :: Num a => Eval a

dot :: Main.Strategy a -> Main.Strategy a -> Main.Strategy a
strat2 `dot` strat1 = strat2 . Main.runEval . strat1

------

normalize [] = []
normalize (False : xs) = 
  let ns = normalize xs
  in if ns == [] then [] else (False : ns)
normalize (True : xs) = True : (normalize xs)

mul [] _ = []
mul (False : xs) ys = False : (mul xs ys)
mul (True : xs) ys = mul (False : xs) ys `add` ys

addc [] ys ci = add ys (normalize [ci])
addc xs [] ci = add xs (normalize [ci])
addc (x : xs) (y : ys) ci = 
  let s = xor (xor x y) ci
      co = (x && y) || ((x || y) && ci) 
      a = (addc xs ys co)
  in if s == False && a == [] then [] else s : a

add [] ys = ys
add xs [] = xs
add xs ys = addc xs ys False

subc xs [] ci = sub xs (normalize [ci])
subc (x : xs) (y : ys) ci = 
  let d = xor (xor x (not y)) (not ci)
      co = ((not x) && y) || (((not x) || y) && ci)
      s = (subc xs ys co) 
  in if d == False && s == [] then [] else d : s

sub xs [] = xs
sub xs ys = subc xs ys False

xor x y = x /= y

normalize [] = []
normalize (False : xs) = 
  let ns = normalize xs
  in if ns == [] then [] else (False : ns)
normalize (True : xs) = True : (normalize xs)

mul [] _ = []
mul (False : xs) ys = False : (mul xs ys)
mul (True : xs) ys = mul (False : xs) ys `add` ys

mulk3 [] _ = []
mulk3 _ [] = []
mulk3 xs ys =
 (normalize (mulk3 xs0 ys0)) `add` (replicate l False ++ (((mulk3 (add xs0 xs1) (add ys0 ys1)) `sub` (normalize (mulk3 xs0 ys0)) `sub` (normalize (mulk3 xs1 ys1))) `add` (replicate l False ++ (normalize (mulk3 xs1 ys1))))) using` strategy
 where
  l = (min (length xs) (length ys)) `div` 2
  (xs0, xs1) = splitAt l xs
  (ys0, ys1) = splitAt l ys
  if l > 32 then
   strategy res = do
    rpar (normalize (mulk3 xs0 ys0))
    rpar (normalize (mulk3 xs1 ys1)) 
    rpar ((mulk3 (add xs0 xs1) (add ys0 ys1)) `sub` (normalize (mulk3 xs0 ys0)) `sub` (normalize (mulk3 xs1 ys1)))
    rdeepseq res
  else
   mul xs ys

From: ekcburak at hotmail.com
To: haskell-cafe at haskell.org
Subject: Karatsuba Multiplication Parallel
Date: Fri, 16 Sep 2011 10:52:14 +0000








Dear All,

I am trying to parallelize the below Karatsuba multiplication code. However, 
at each trial of mine the error message speaking of "incorrect indentation"
is returned. I could not come up with ideas to solve the problem.

I will be more than glad and appreciated, if any of you sheds light on the
issue and point out the problem with its solution.

Many thanks in advance,

 Cheers,
Burak.

import Control.Parallel
import Control.Parallel.Strategies

normalize [] = []
normalize (False : xs) = 
  let ns = normalize xs
  in if ns == [] then [] else (False : ns)
normalize (True : xs) = True : (normalize xs)

mul [] _ = []
mul (False : xs) ys = False : (mul xs ys)
mul (True : xs) ys = mul (False : xs) ys `add` ys

mulk3 [] _ = []
mulk3 _ [] = []
mulk3 xs ys =
 (normalize (mulk3 xs0 ys0)) `add` (replicate l False ++ (((mulk3 (add xs0 xs1) (add ys0 ys1)) `sub` (normalize (mulk3 xs0 ys0)) `sub` (normalize (mulk3 xs1 ys1))) `add` (replicate l False ++ (normalize (mulk3 xs1 ys1)))))
 where
  l = (min (length xs) (length ys)) `div` 2
  (xs0, xs1) = splitAt l xs
  (ys0, ys1) = splitAt l ys
  if l > 32 then
   (normalize (mulk3 xs0 ys0)) `par`
   (normalize (mulk3 xs1 ys1)) `par`
   ((mulk3 (add xs0 xs1) (add ys0 ys1)) `sub` (normalize (mulk3 xs0 ys0)) `sub` (normalize (mulk3 xs1 ys1)))
  else
   mul xs ys


 		 	   		   		 	   		  
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110916/94d60e27/attachment.htm>