SICP Exercise 1.16 ... what does "invariant quantity" hint mean?

Question

I see there are a few other questions around this exercise but none specifically are asking what is meant within the hint... "define the state transition in such a way that the product abⁿ is unchanged from state to state".

They also mention that this idea of using an "invariant quantity" is a powerful idea with respect to "iterative algorithms". By the way, this problem calls for the design of a "logarithmic" exponent algorithm that has a space complexity of O(1).

Mainly I just have no idea what is meant by this hint and am pretty confused. Can anyone give me a nudge in what is meant by this? The only thing I can really find about "invariant quantities" are described using examples in physics which only makes this concept more opaque.

Exercise description in full:

Exercise 1.16: Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fast-expt. (Hint: Using the observation that (b^n/2)² = (b²)^n/2, keep, along with the exponent n and the base b, an additional state variable a, and define the state transformation in such a way that the product abⁿ is unchanged from state to state.

At the beginning of the process a is taken to be 1, and the answer is given by the value of a at the end of the process. In general, the technique of defining an invariant quantity that remains unchanged from state to state is a powerful way to think about the design of iterative algorithms.)

Thanks in advance.

Answer 1

To specifically answer the question of what "invariant" means here, and not describe the algorithm or provide a complete solution:

The idea is to keep a * b^n the same, while changing a, b, and n at each step of the algorithm. (Well, one or more of a, b, and n might stay the same in a particular step while the others change). You start out with a = 1. Then you iteratively transform each variable so that a accumulates all the factors of the original quantity.

Answer 2

It's easiest to explain if we start from a working solution and then point to the things the authors are calling the "states" and "invariant quantity". Here's such a solution:

(define (even? n)
    (= (remainder n 2) 0))

(define (square n)
    (* n n))

(define (fast-expt b n)
    (fast-expt-iter 1 b n))

(define (fast-expt-iter a b n)
    (cond ((= n 0) a)
          ((even? n) (fast-expt-iter a (square b) (/ n 2)))
          (else (fast-expt-iter (* a b) b (- n 1))))
)

What the authors are calling a "state" is a triple of arguments passed to fast-expt-iter. So when we call, for instance, (fast-expt 3 7) to compute 3⁷, the series of states we go through is:

• a=1, b=3, n=7
• a=3, b=3, n=6
• a=3, b=9, n=3
• a=27, b=9, n=2
• a=27, b=81, n=1
• a=2187, b=81, n=0

(Note that since fast-expt-iter is tail recursive, each such state replaces the last one in memory; the Lisp interpreter doesn't maintain a call stack with all 6 states on it.)

What the authors are calling an "invariant quantity" is the value of the expression abⁿ. I think your puzzlement at the wording "invariant quantity" here is reasonable; I might've named this an "invariant expression" if I were making up my own terminology. The key idea, though, is that the value of that expression abⁿ does not change from one state to the next:

• The transition ((even? n) (fast-expt-iter a (square b) (/ n 2))) leaves abⁿ unchanged (since a(b²)^n/2 = abⁿ for all possible values of a, b, and n)
• The transition (else (fast-expt-iter (* a b) b (- n 1))) leaves abⁿ unchanged (since, again, abb^n-1 = abⁿ for all possible values of a, b, and n)

We can use the fact that abⁿ doesn't change to prove the correctness of fast-expt. First we note that if fast-expt-iter is correct (i.e. if it correctly computes abⁿ for all possible a, b and n) then fast-expt is correct too (since (1)bⁿ = bⁿ). Then we prove fast-expt-iter correct by first noting that it is correct in the base case where n=0, then noting as our inductive step that if it is correct for all integer values up to some integer n then it is also correct for n (since state transitions don't modify the value of abⁿ), and then concluding by induction that it computes abⁿ for any integer value of n.

See also the very similar concept of a loop invariant as a way to reason about what a loop does!

Answer 3

when fast-exp execute, the trace looks something like this

b^14 = (b^2)^7 ; where: b' = b^2; a = 1, n = 7
b^14 = (b^2)^6 * b^2 ; where: b' = b^2; a = b^2, n = 6
b^14 = ((b^2)^2)^3 *b^2 ; where: b' = b^2^2 ; a = b^2, n = 3
b^14 = ((b^2)^2)^2 *b^2 *(b^2)^2 ; where: b' = b^2^2; a = b^2*(b^2)^2, n = 2

notice that all these statements have the general form of b^n = b'^n' * a', and this does not change

Answer 4

This is not about any "logarithmic exponentiation", which is a very vague and confusing terminology.

As the quote you provided says, it is about exponentiation function that takes logarithmic number of steps to get its final result.

So we want to develop a function, exp(b,n), which would take O(log n) time to finish.

The numbers involved are all integers.

So how do we calculate bn? We notice that

b^n = b * b * b * b *... * b 
      `------n times------/        O(n) time process

and, when n is even,

b^n = b * b * b * b * ... * b *  
      `------n/2 times-----/   
      b * b * b * b * ... * b   
      `------n/2 times-----/   
    = (b^(n/2))^2                ; viewed from the side
    = (b^2)^(n/2)                ; viewed from above

and when n is odd,

b^n = b * b * b * b * ... * b *  
      `------n/2 times-----/   
      b * b * b * b * ... * b *
      `------n/2 times-----/   
      b
      `--1 time--/
    = (b^(n/2))^2  *  b
    = (b^2)^(n/2)  *  b

Note that both expression fall into same category if we write the first one as (b^2)^(n/2) * 1.

Also note that the equation

  b^n = (b   )^(n  )  *  { a where a = 1   }
      = (b ^2)^(n/2)  *  { a where a = ... }
      = (b'  )^(n' )  *  { a' }

means that to calculate b^n * a is the same as to calculate b'^n' * a' with the changed values of { b' = b^2 ; n' = n/2 ; a' = {if {n is even} then {a} else {a * b}} }.

So we don't actually compute either of the sides of that equation. Instead we keep the triples { b, n, a } at each step and transform them according to that rule

 { b, n, a } --> { b', n', a' } --> ...

with the initial values of b and n as given to us, and the first a equal to 1; and know that the final result calculated from any of the triples would be the same if we'd actually calculated it somehow. We still don't know how exactly we'd do that; just that it would be the same. That's the "invariant" part.

So what all this is good for? Well, since the chain { n --> n/2 --> ... } will certainly reach a point where n == 1, we know that at that point we can break the chain since

 c^1 * d  ==  c * d

and this one simple multiplication of these two numbers will produce the same result as the initial formula.

Which is the final result of the function.

And that's the meaning of the hint: maintain the state of the computation as a (here) triple of numbers (or just three variables named b, n, a), and implement your computation as a chain of state-transforming steps. When the chain is broken according to some test (here, n == 1), we've reached our destination and can calculate the final result according to some simple rule (here, c * d).

This gives us a nice and powerful methodology for problem solving.

Oh, and we also know that the length of that chain of changing states is O(log n), since we halve that n at each step.