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

Matthias Guedemann matthias.guedemann at ovgu.de
Thu Jun 16 12:51:39 CEST 2011

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)


More information about the Beginners mailing list