A neat, simple example of making code more efficient

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? /Roger [1] http://www.amazon.com/Introduction-Functional-Programming-using-Haskell/dp/0134843460/ref=sr_1_1?ie=UTF8&qid=1308220033&sr=8-1

Hi Roger,
Which is itself a square operation:
square (square a)
this is a special case of square-and-multiply or binary exponentiation (see http://en.wikipedia.org/wiki/Exponentiation_by_squaring) general square and multiply also works for an odd exponent and reduces the complexity from O(n) to O(log n) regards Matthias

"Costello, Roger L."
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/
participants (3)
-
Costello, Roger L.
-
Ertugrul Soeylemez
-
Matthias Guedemann