Programming Praxis – Three Binary Algorithms

In today’s Programming Praxis we have to implement binary algorithms for multiplying, dividing, and finding the greatest common divisor of two numbers. Let’s get started.

Since all our functions require the Bits typeclass, for which Haskell doesn’t do type defaulting, we use the following language pragma so we don’t have to specify types in the tests.

{-# LANGUAGE ExtendedDefaultRules #-}

We need an import to do bitshifting.

import Data.Bits

And because we’re going to be doing quite a bit of it, two quick convenience convenience functions for doubling and halving numbers:

left, right :: Bits a => a -> a
left = flip shiftL 1
right = flip shiftR 1

Binary multiplication. Piece of cake.

binmult :: (Bits a, Integral a) => a -> a -> a
binmult 1 b = b
binmult a b = binmult (right a) (left b) + if odd a then b else 0

Binary division. By using the until function we don’t have use explicit recursion to find t.

bindiv :: (Bits a, Ord a) => a -> a -> (a, a)
bindiv n d = f (right $ until (> n) left d) 0 n where
    f t q r | t < d     = (q, r)
            | t <= r    = f (right t) (left q + 1) (r - t)
            | otherwise = f (right t) (left q)     r

Binary gcd. A lot of different conditions, but all very straightforward.

bingcd :: (Bits a, Integral a) => a -> a -> a
bingcd a 0 = a
bingcd 0 b = b
bingcd a b | even a && even b = 2 * bingcd (right a) (right b)
           | even a           = bingcd (right a) b
           | even b           = bingcd a (right b)
           | a > b            = bingcd (a - b) b
           | otherwise        = bingcd a (b - a)

A quick test shows that everything is working correctly:

main :: IO ()
main = do print $ binmult 14 12
          print $ bindiv 837 43
          print $ bingcd 2322 654
About these ads

Tags: , , , , , , , , , ,

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


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: