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

[Ertugrul Soeylemez]

"Costello, Roger L." <costello at mitre.org> wrote:

> This book [1] has a neat, simple example of making code more
> efficient.
>
> [...]
>
> Thus, by a little rework the number of multiplications is reduced from
> three to two. That is a significant efficiency improvement.
>
> Cool, aye?

As Matthias noted correctly this is a well known method for
exponentiation with arbitrary integer exponents (works even for rational
exponents in certain groups).

I would like to add that exactly this method drives the (^)
exponentiation function, so your function becomes

    quad :: Num a => a -> a
    quad = (^4)

and benefits from the same exponential speedup, although writing the
direct multiplication may give you a performance improvement by a
constant factor, which may or may not be significant.


Greets,
Ertugrul


-- 
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://ertes.de/