Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Bitwise multiplication
-- Numbers represented as infinite streams of bits
data Bits
= O Bits
| I Bits
-- Increments a number
suc :: Bits -> Bits
suc (O xs) = I xs
suc (I xs) = O (suc xs)
-- Adds two numbers
add :: Bits -> Bits -> Bits
add (O xs) (O ys) = (O (add xs ys))
add (O xs) (I ys) = (I (add xs ys))
add (I xs) (O ys) = (I (add xs ys))
add (I xs) (I ys) = (suc (I (add xs ys)))
-- Multiplies two numbers
mul :: Bits -> Bits -> Bits
mul (O xs) ys = (O (mul xs ys))
mul (I xs) ys = add ys (O (mul xs ys))
-- The number zero is an infinite sequence of the bit 0
b0 :: Bits
b0 = O b0
-- Converts integer to bits
fromInt :: Integer -> Bits
fromInt 0 = b0
fromInt n = suc (fromInt (n - 1))
-- Convert bits to integer reading `l` bits
toInt :: Integer -> Bits -> Integer
toInt l = go l 1 where
go 0 m xs = 0
go n m (O xs) = go (n - 1) (m * 2) xs
go n m (I xs) = m + go (n - 1) (m * 2) xs
-- Prints bits reading at most `l` bits
prin :: Integer -> Bits -> IO ()
prin size bs = putStrLn (format size bs ++ " (" ++ show (toInt size bs) ++ ")")
-- Formats bits reading at most `l` bits
format :: Integer -> Bits -> String
format 0 xs = ""
format n (O xs) = "O" ++ format (n - 1) xs
format n (I xs) = "I" ++ format (n - 1) xs
-- Random 256 bit number
rnd256a :: Bits
rnd256a =
O . I . O . O . O . I . O . O .
I . I . O . O . I . I . O . I .
O . O . O . I . O . O . O . O .
I . O . I . I . I . I . I . O .
O . O . I . O . I . O . O . I .
O . O . I . O . I . O . O . I .
O . I . I . I . I . O . O . I .
O . O . I . I . O . O . I . I .
O . O . O . O . I . O . O . O .
O . O . I . O . O . I . I . O .
O . O . O . O . I . O . O . O .
I . O . I . O . I . O . I . I .
O . O . I . O . I . I . O . I .
I . I . O . I . I . O . O . I .
O . O . I . O . I . I . O . I .
O . O . I . O . O . I . I . I .
O . I . O . O . O . I . I . O .
O . O . O . O . I . I . I . O .
I . I . I . I . O . I . O . O .
O . I . I . I . I . I . O . I .
O . I . O . I . I . O . O . O .
O . O . O . I . I . O . I . O .
O . I . O . I . O . O . O . I .
O . O . O . I . I . O . O . O .
I . I . O . I . I . O . I . O .
I . O . O . O . O . O . I . O .
I . O . I . O . I . O . I . O .
I . O . O . I . O . O . I . I .
I . O . I . O . I . O . I . O .
O . O . I . O . I . I . I . I .
I . O . O . I . O . O . O . O .
O . I . I . I . I . I . I . I $ b0
-- Random 256 bit number
rnd256b :: Bits
rnd256b =
O . I . O . O . O . I . I . I .
I . I . I . O . O . O . O . O .
I . O . O . O . O . I . O . O .
I . I . I . O . I . I . O . O .
I . O . I . O . O . O . O . O .
I . O . O . I . I . O . I . O .
O . I . O . O . I . O . I . I .
I . I . O . I . O . I . O . O .
I . I . O . O . I . I . O . O .
I . I . O . O . O . I . I . O .
O . I . O . O . I . I . O . O .
I . I . I . I . I . O . I . O .
I . I . I . I . I . O . I . O .
I . O . I . O . O . I . I . O .
I . O . O . I . I . O . O . O .
O . O . O . O . O . O . O . I .
I . O . O . I . O . O . O . I .
O . O . I . O . I . O . I . I .
O . O . I . I . O . I . I . O .
I . O . I . I . O . O . O . I .
O . O . I . O . O . O . O . I .
I . O . I . O . O . I . I . I .
O . I . I . O . I . O . O . I .
I . I . O . O . I . I . O . O .
I . I . I . I . O . O . O . O .
O . O . O . O . O . I . I . I .
O . I . I . I . O . I . O . I .
I . I . O . O . O . O . I . I .
I . O . O . O . O . I . O . O .
O . O . O . O . I . O . I . I .
O . O . I . O . I . O . I . I .
O . O . I . O . I . O . O . I $ b0
main :: IO ()
main = do
prin 256 $ rnd256a
prin 256 $ rnd256b
prin 512 $ mul rnd256a rnd256b
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.