Programming Praxis – Look And Say, Revisited

In today’s Programming Praxis exercise, our goal is to calculate Conway’s constant. Let’s get started, shall we?

First we need to represent the polynomial that we’re going to take the root of.

conway :: Num a => a -> a
conway x = sum $ zipWith (*) (iterate (* x) 1)
    [ -6,  3,-6, 12,-4, 7,-7, 1, 0, 5,-2, -4,-12, 2, 7,12,-7,-10
    , -4,  3, 9, -7, 0,-8,14,-3, 9, 2,-3,-10, -2,-6, 1,10,-3,  1
    ,  7, -7, 7,-12,-5, 8, 6,10,-8,-8,-7, -3,  9, 1, 6, 6,-2, -3
    ,-10, -2, 3,  5, 2,-1,-1,-1,-1,-1, 1,  2,  2,-1,-2,-1, 0,  1]

Next, we calculate the root by halving the interval until the value at the middle is sufficiently close to 0.

root :: (Fractional a, Ord a) => (a -> a) -> a -> a -> a -> a
root f lo hi e | abs (f mid) < e = mid
               | f mid > 0       = root f lo mid e
               | otherwise       = root f mid hi e
               where mid = (lo + hi) / 2

Since we know the root lies somewhere between 1 and 2, we use those as the starting values.

main :: IO ()
main = print $ root conway 1 2 1e-7 == 1.303577269034296

We get the correct answer, so everything seems to be working properly.

About these ads

Tags: , , , , , , , ,

3 Responses to “Programming Praxis – Look And Say, Revisited”

  1. Graham Says:

    Just curious: what do you use to post/syntax highlight your haskell code? It doesn’t look like the sourcecode-tagged versions on the Praxis page.

  2. Remco Niemeijer Says:

    Since this a wordpress.com blog I can’t use any highlighting plugins, so I use a program called Highlight (http://www.andre-simon.de/doku/highlight/en/highlight.html) that outputs html. It’s not flawless, but it works well enough in most cases.

  3. Graham Says:

    Thanks! I’d seen Highlight before, but had forgotten how extensive it is.

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: