SICP Exercise 1.16

This problem challenged me to really think about the efficiency of my algorithm. I have trouble relating arithmetic notions to computing, so understanding the information that the authors had laid out was a problem for me at first.

Whatever solution you come up with for this, be sure to check its Big-O function. I thought I had written a novel solution, based on the ideas in the book. What I found after checking the number of steps it took was that its performance was better than linear, but it was close to linear. I wasn’t satisfied with that. So I looked at ways of making it more efficient, and found that not only was I inefficient in my process, but I was also inefficient with my code. You need to put the focus on successive squaring. A good working knowledge of what exponents represent will work in your favor.

I thought at first that I needed two functions: one for even powers, and one for odd, because I figured out different implementations for each. Then I found that I needed only one function for computing an exponent. There’s a hint about that in the text: bn = b ⋅ bn-1.

I found the hints written into the exercise a bit confusing, but now that I’ve solved it I see what they were getting at. To me, they turned out to be somewhat helpful, but also somewhat misleading. They tried to be helpful, but they didn’t want to reveal too much. In the end I think they were “too smart” for their own good.

One of the hints is an abstraction. One of the hints relates to a concept that was discussed earlier, and it’s just supposed to help you see it more clearly so you can use the idea in your code. Don’t think that you need to translate all of the hints literally into equivalent code. Use them as inspiration–use what you find useful at the moment. If it doesn’t make sense after thinking about it for a bit, just put it out of your mind. Focus on developing what you think will solve the problem. Once you get something going, see how it does performance-wise, and then perhaps reconsider the hints. Don’t be thinking about, “Did I put all of the hints in my code correctly?” Once you get the problem solved, you’ll see as I did what the hints were all about.

In one of my early versions of a solution, I noticed it was making “leaps and bounds” using successive squaring in computing the answer, and then I had it slow down quite a bit because I was trying to get to an intermediate step, which the successive squaring technique would overshoot. I’m being a bit misleading by saying this, but I don’t want to give too much away. Look at the gap between where successive squaring gets you, and where you need to go, and think of how to get through that gap more quickly. The hint I’ll give you is: once you’ve gotten to the point of considering this, the answer is already within your grasp.