[Haskell-beginners] A neat, simple example of making code more efficient

Costello, Roger L. costello at mitre.org
Thu Jun 16 12:34:27 CEST 2011

Hi Folks,

This book [1] has a neat, simple example of making code more efficient.

Suppose you want to create a function, quad, that raises a number to the 4th power.

Example: quad 2 = 2 * 2 * 2 * 2 = 16

The function could be implemented like this:

    quad a = a * a * a * a

That implementation requires three multiplications, which can be pretty expensive, especially with arbitrary numbers.

Let's see if we can make it more efficient, by finding an implementation that uses less multiplications. 

By the associative law we can group the expression:

    (a * a) * (a * a)

Each subexpression performs a square operation:

    (square a) * (square a)

Which is itself a square operation:

    square (square a)

That implementation requires only two multiplications. Let's take an example to see why:

quad 2 = square (square 2)
            = square (2 * 2)        -- First multiplication
            = square (4)              -- Reduction 
            = 4 * 4                       -- Second multiplication
            = 16                           -- Reduction to the answer

Thus, by a little rework the number of multiplications is reduced from three to two. That is a significant efficiency improvement.

Cool, aye?


[1] http://www.amazon.com/Introduction-Functional-Programming-using-Haskell/dp/0134843460/ref=sr_1_1?ie=UTF8&qid=1308220033&sr=8-1

More information about the Beginners mailing list