Chapter 3
Associative Operations
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.
3.1 Associativity
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, ...
Get Elements of Programming now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
