6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 4.3.1 Lets take another quick look at how we can create procedures Using different processes for the same goal ith different orders of growth to compute the same function We want to compute a b, just using multiplication and As a specific example, suppose we want to compute exponentials, such as a raised to the b power but to do so only using the simpler operations of multiplication and addition How might we use the tools we have been developing to accomplish this? Using different processes for the same goal Slide 4.3.2 We want to compute a b, just using multiplication and So, recall the stages we used to solve problems like this:w will use some wishful thinking to assume that solutions to Remember our stages: Wishful thinking simpler versions of the problem exist; we will then decompose the problem into a simpler version of the same problem, plus some other simple operations, and we will use this to construct a solution to the more general problem; and finally, we will determine the smallest sized subproblem into which we want to do decomposition. Let's look at using these tools on the problem of exponentiation 6001 SICP Slide 4.3.3 Using different processes for the same goal wishful thinking is our tool for using induction. It says, let's assume that some procedure my-expt exists, so that we can. Assume that the procedure my-expt exists, but only use it, but that it only solves smaller versions of the same solves smaller versions of the same problem problem Using different processes for the same goal Slide 4.3.4 Wishful thinking Given that assumption, we can then turn to the tricky part, Assume that the procedure mry-expt exists, but only which is determining how to decompose the problem into a soles smaller versions of the same problem simpler version of the same problem Decompose problem into soking smaller version and using Here is one method: Notice that a to the power b result b=a*a*,*a=a*a^{b-1 mathematically is just b products of a. But this we can also group as a times b-l products of a, and that latter we ecognize as a smaller version of the same exponentiation problem. Thus, we can reduce a to the bth power as a times 1001 SICP I to the b-1st power. Thus we can reduce the problem to a simpler version of the same problem, together with some simple operations, in this case, an additional multiplication6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 4.3.1 Let's take another quick look at how we can create procedures with different orders of growth to compute the same function. As a specific example, suppose we want to compute exponentials, such as a raised to the b power, but to do so only using the simpler operations of multiplication and addition. How might we use the tools we have been developing to accomplish this? Slide 4.3.2 So, recall the stages we used to solve problems like this: we will use some wishful thinking to assume that solutions to simpler versions of the problem exist; we will then decompose the problem into a simpler version of the same problem, plus some other simple operations, and we will use this to construct a solution to the more general problem; and finally, we will determine the smallest sized subproblem into which we want to do decomposition. Let's look at using these tools on the problem of exponentiation. Slide 4.3.3 Wishful thinking is our tool for using induction. It says, let's assume that some procedure my-expt exists, so that we can use it, but that it only solves smaller versions of the same problem. Slide 4.3.4 Given that assumption, we can then turn to the tricky part, which is determining how to decompose the problem into a simpler version of the same problem. Here is one method: Notice that a to the power b mathematically is just b products of a. But this we can also group as a times b-1 products of a, and that latter we recognize as a smaller version of the same exponentiation problem. Thus, we can reduce a to the bth power as a times a to the b-1st power. Thus we can reduce the problem to a simpler version of the same problem, together with some simple operations, in this case, an additional multiplication