June 2009
Intermediate to advanced
288 pages
5h 59m
English
This chapter discusses associative binary operations. Associativity allows regrouping the adjacent operations. This ability to regroup leads to an efficient algorithm for computing powers of the binary operation. Regularity enables a variety of program transformations to optimize the algorithm. We then use the algorithm to compute linear recurrences, such as Fibonacci numbers, in logarithmic time.
A binary operation is an operation with two arguments:

The binary operations of addition and multiplication are central to mathematics. Many more are used, such as min, max, conjunction, disjunction, ...