28 CHAPTER 3.COMPUTING WITH NUMBERS root1 (-b discRoot)/(2 a) root2 (-b-discRoot)/(2 a) print print "The solutions are:"root1,root2 main() This program makes use of the square root function sqrt from the math library module.The line at the top of the program: import math tells Python that we are using the math module.Importing a module makes whatever is defined in it available to the program.To compute vx,we use math.sqrt (x).You may recall this dot notation from Chapter 1. This tells Python to use the sqrt function that"lives"in the math module.In the quadratic program we calculate vb2-4*ac with the line discRoot math.sgrt(b b-4 a c) Here is how the program looks in action: This program finds the real solutions to a quadratic Please enter the coefficients (a,b,c):3,4,-2 The so1 utions are:0.387425886723-1.72075922006 This program is fine as long as the quadratics we try to solve have real solutions.However,some inputs will cause the program to crash.Here's another example run: This program finds the real solutions to a quadratic Please enter the coefficients (a,b,c):1,2,3 Traceback (innermost last): File "<stdin>",line 1,in File "quadratic.py",line 13,in discRoot math.sqrt(b b-4 a c) OverflowError:math range error The problem here is that b2-4*a*c<0,and the sgrt function is unable to compute the square root of a negative number.Python prints a math range error.Right now,we don't have the tools to fix this problem,so we will just have to assume that the user gives us solvable equations. Actually,quadratic.py did not need to use the math library.We could have taken the square root using exponentiation **.(Can you see how?)Using math.sqrt is somewhat more efficient and allowed me to illustrate the use of the math library.In general,if your program requires a common mathematical function,the math library is the first place to look.Table 3.2 shows some of the other functions that are available in the math library. 3.3 Accumulating Results:Factorial Suppose you have a root beer sampler pack containing six different kinds of root beer.Drinking the various flavors in different orders might affect how good they taste.If you wanted to try out every possible ordering, how many different orders would there be?It turns out the answer is a surprisingly large number,720.Do you know where this number comes from?The value 720 is the factorial of 6. In mathematics,factorial is often denoted with an exclamation("").The factorial of a whole number n is defined as n!=n(n-1)(n-2)...(1).This happens to be the number of distinct arrangements for n items. Given six items,we compute 6!=(6)(5)(4)(3)(2)(1)=720 possible arrangements
28 CHAPTER 3. COMPUTING WITH NUMBERS root1 = (-b + discRoot) / (2 * a) root2 = (-b - discRoot) / (2 * a) print print "The solutions are:", root1, root2 main() This program makes use of the square root function sqrt from the math library module. The line at the top of the program: import math tells Python that we are using the math module. Importing a module makes whatever is defined in it available to the program. To compute ✁ x, we use math.sqrt(x). You may recall this dot notation from Chapter 1. This tells Python to use the sqrt function that “lives” in the math module. In the quadratic program we calculate ✁ b 2 ✂ 4 ac with the line discRoot = math.sqrt(b * b - 4 * a * c) Here is how the program looks in action: This program finds the real solutions to a quadratic Please enter the coefficients (a, b, c): 3, 4, -2 The solutions are: 0.387425886723 -1.72075922006 This program is fine as long as the quadratics we try to solve have real solutions. However, some inputs will cause the program to crash. Here’s another example run: This program finds the real solutions to a quadratic Please enter the coefficients (a, b, c): 1, 2, 3 Traceback (innermost last): File "<stdin>", line 1, in ? File "quadratic.py", line 13, in ? discRoot = math.sqrt(b * b - 4 * a * c) OverflowError: math range error The problem here is that b 2 ✂ 4 a c 0, and the sqrt function is unable to compute the square root of a negative number. Python prints a math range error. Right now, we don’t have the tools to fix this problem, so we will just have to assume that the user gives us solvable equations. Actually, quadratic.py did not need to use the math library. We could have taken the square root using exponentiation **. (Can you see how?) Using math.sqrt is somewhat more efficient and allowed me to illustrate the use of the math library. In general, if your program requires a common mathematical function, the math library is the first place to look. Table 3.2 shows some of the other functions that are available in the math library. 3.3 Accumulating Results: Factorial Suppose you have a root beer sampler pack containing six different kinds of root beer. Drinking the various flavors in different orders might affect how good they taste. If you wanted to try out every possible ordering, how many different orders would there be? It turns out the answer is a surprisingly large number, 720. Do you know where this number comes from? The value 720 is the factorial of 6. In mathematics, factorial is often denoted with an exclamation (“!”). The factorial of a whole number n is defined as n! n n ✂ 1 ✁ n ✂ 2✁ 1 ✁ . This happens to be the number of distinct arrangements for n items. Given six items, we compute 6! 6✁ 5✁ 4✁ 3✁ 2✁ 1 ✁ 720 possible arrangements
3.3.ACCUMULATING RESULTS:FACTORIAL 29 Python Mathematics English pi 元 An approximation of pi. e An approximation ofe. sin(x) sinx The sine of x. cos(x) cOSx The cosine of x tan(x) tanx The tangent of x. asin(x) arcsinx The inverse of sine x. acos(x) arccosx The inverse of cosine x. atan (x) arctanx The inverse of tangent x log(x) Inx The natural (base e)logarithm of x 1og10(x) logiox The common(base 10)logarithm of x exp(x) er The exponential of x. ceil(x) 「x] The smallest whole number<=x floor(x) x The largest whole number<=x Table 3.2:Some math library functions. Let's write a program that will compute the factorial of a number entered by the user.The basic outline of our program follows an Input-Process-Output pattern. Input number to take factorial of,n Compute factorial of n,fact Output fact Obviously,the tricky part here is in the second step. How do we actually compute the factorial?Let's try one by hand to get an idea for the process.In computing the factorial of 6,we first multiply 65=30.Then we take that result and do another multipli- cation 304=120.This result is multiplied by three 1203=360.Finally,this result is multiplied by 2 3602=720.According to the definition,we then multiply this result by 1,but that won't change the final value of 720. Now let's try to think about the algorithm more generally.What is actually going on here?We are doing repeated multiplications,and as we go along,we keep track of the running product.This is a very common algorithmic pattern called an accumulator.We build up,or accumulate,a final value piece by piece.To accomplish this in a program,we will use an accumulator variable and a loop structure.The general pattern looks like this. Initialize the accumulator variable Loop until final result is reached update the value of accumulator variable Realizing this is the pattern that solves the factorial problem,we just need to fill in the details.We will be accumulating the factorial.Let's keep it in a variable called fact.Each time through the loop,we need to multiply fact by one of the factors n,(n-1),...,1.It looks like we should use a for loop that iterates over this sequence of factors.For example,to compute the factorial of6,we need a loop that works like this fact =1 for factor in [6,5,4,3,2,1]: fact fact factor Take a minute to trace through the execution of this loop and convince yourself that it works.When the loop body first executes,fact has the value 1 and factor is 6.So,the new value of fact is 126=6. The next time through the loop,factor will be 5,and fact is updated to 65=30.The pattern continues for each successive factor until the final result of 720 has been accumulated. The initial assignment of 1 to fact before the loop is essential to get the loop started.Each time through the loop body (including the first),the current value of fact is used to compute the next value.The
3.3. ACCUMULATING RESULTS: FACTORIAL 29 Python Mathematics English pi π An approximation of pi. e e An approximation of e. sin(x) sinx The sine of x. cos(x) cosx The cosine of x. tan(x) tanx The tangent of x. asin(x) arcsinx The inverse of sine x. acos(x) arccosx The inverse of cosine x. atan(x) arctanx The inverse of tangent x. log(x) lnx The natural (base e) logarithm of x log10(x) log10 x The common (base 10) logarithm of x. exp(x) e x The exponential of x. ceil(x) x✁ The smallest whole number x floor(x) ✂x✄ The largest whole number x Table 3.2: Some math library functions. Let’s write a program that will compute the factorial of a number entered by the user. The basic outline of our program follows an Input-Process-Output pattern. Input number to take factorial of, n Compute factorial of n, fact Output fact Obviously, the tricky part here is in the second step. How do we actually compute the factorial? Let’s try one by hand to get an idea for the process. In computing the factorial of 6, we first multiply 6 5 30. Then we take that result and do another multiplication 30 4 120. This result is multiplied by three 120 3 360. Finally, this result is multiplied by 2 360 2 720. According to the definition, we then multiply this result by 1, but that won’t change the final value of 720. Now let’s try to think about the algorithm more generally. What is actually going on here? We are doing repeated multiplications, and as we go along, we keep track of the running product. This is a very common algorithmic pattern called an accumulator. We build up, or accumulate, a final value piece by piece. To accomplish this in a program, we will use an accumulator variable and a loop structure. The general pattern looks like this. Initialize the accumulator variable Loop until final result is reached update the value of accumulator variable Realizing this is the pattern that solves the factorial problem, we just need to fill in the details. We will be accumulating the factorial. Let’s keep it in a variable called fact. Each time through the loop, we need to multiply fact by one of the factors n ☎ n ✂ 1✁✆☎ ✝☎ 1. It looks like we should use a for loop that iterates over this sequence of factors. For example, to compute the factorial of 6, we need a loop that works like this. fact = 1 for factor in [6,5,4,3,2,1]: fact = fact * factor Take a minute to trace through the execution of this loop and convince yourself that it works. When the loop body first executes, fact has the value 1 and factor is 6. So, the new value of fact is 1 6 6. The next time through the loop, factor will be 5, and fact is updated to 6 5 30. The pattern continues for each successive factor until the final result of 720 has been accumulated. The initial assignment of 1 to fact before the loop is essential to get the loop started. Each time through the loop body (including the first), the current value of fact is used to compute the next value. The
30 CHAPTER 3.COMPUTING WITH NUMBERS initialization ensures that fact has a value on the very first iteration.Whenever you use the accumulator pattern,make sure you include the proper initialization.Forgetting it is a common mistake of beginning programmers. Of course,there are many other ways we could have written this loop.As you know from math class, multiplication is commutative and associative,so it really doesn't matter what order we do the multiplications in.We could just as easily go the other direction.You might also notice that including 1 in the list of factors is unnecessary,since multiplication by 1 does not change the result.Here is another version that computes the same result. fact 1 for factor in [2,3,4,5,6]: factfact factor Unfortunately,neither of these loops solves the original problem.We have hand-coded the list of factors to compute the factorial of six.What we really want is a program that can compute the factorial of any given input n.We need some way to generate an appropriate list from the value of n. Luckily,this is quite easy to do using the Python range function.Recall that range (n)produces a list of numbers starting with 0 and continuing up to,but not including,n.There are other variations of range that can be used to produce different sequences.With two parameters,range (start,n)produces a sequence that starts with the value start and continues up to,but not including,n.A third version range(start, n,step)is like the two parameter version,except that it uses step as the increment between numbers. Here are some examples. >>range(10) [0,1,2,3,4,5,6,7,8,9] >>range(5,10) [5,6,7,8,9] >>range(5,10,3) [5,8] Given our input value n we have a couple of different range commands that produce an appropriate list of factors for computing the factorial of n.To generate them from smallest to largest(a la our second loop), we could use range(2,n+1).Notice how I used n+1 as the second parameter,since the range will go up to.but not including this value.We need the +1 to make sure that n itself is included as the last factor. Another possibility is to generate the factors in the other direction(a la our first loop)using the three- parameter version of range and a negative step to cause the counting to go backwards:range(n,1,-1). This one produces a list starting with n and counting down (step-1)to,but not including 1. Here then is one possible version of the factorial program. factorial.py Program to compute the factorial of a number Illustrates for loop with an accumulator def main(): n=input ("Please enter a whole number:" fact 1 for factor in range(n,1,-1): factfact factor print "The factorial of",n,"is",fact main() Of course there are numerous other ways this program could have been written.I have already mentioned changing the order of factors.Another possibility is to initialize fact to n and then use factors starting at n-1 (as long as n>0).You might try out some of these variations and see which you like best
30 CHAPTER 3. COMPUTING WITH NUMBERS initialization ensures that fact has a value on the very first iteration. Whenever you use the accumulator pattern, make sure you include the proper initialization. Forgetting it is a common mistake of beginning programmers. Of course, there are many other ways we could have written this loop. As you know from math class, multiplication is commutative and associative, so it really doesn’t matter what order we do the multiplications in. We could just as easily go the other direction. You might also notice that including 1 in the list of factors is unnecessary, since multiplication by 1 does not change the result. Here is another version that computes the same result. fact = 1 for factor in [2,3,4,5,6]: fact = fact * factor Unfortunately, neither of these loops solves the original problem. We have hand-coded the list of factors to compute the factorial of six. What we really want is a program that can compute the factorial of any given input n. We need some way to generate an appropriate list from the value of n. Luckily, this is quite easy to do using the Python range function. Recall that range(n) produces a list of numbersstarting with 0 and continuing up to, but not including, n. There are other variations of range that can be used to produce different sequences. With two parameters, range(start,n) produces a sequence that starts with the value start and continues up to, but not including, n. A third version range(start, n, step) is like the two parameter version, except that it uses step as the increment between numbers. Here are some examples. >>> range(10) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> range(5,10) [5, 6, 7, 8, 9] >>> range(5, 10, 3) [5, 8] Given our input value n we have a couple of different range commands that produce an appropriate list of factors for computing the factorial of n. To generate them from smallest to largest (a la our second loop), we could use range(2,n+1). Notice how I used n+1 as the second parameter, since the range will go up to, but not including this value. We need the +1 to make sure that n itself is included as the last factor. Another possibility is to generate the factors in the other direction (a la our first loop) using the threeparameter version of range and a negative step to cause the counting to go backwards: range(n,1,-1). This one produces a list starting with n and counting down (step -1) to, but not including 1. Here then is one possible version of the factorial program. # factorial.py # Program to compute the factorial of a number # Illustrates for loop with an accumulator def main(): n = input("Please enter a whole number: ") fact = 1 for factor in range(n,1,-1): fact = fact * factor print "The factorial of", n, "is", fact main() Of course there are numerous other ways this program could have been written. I have already mentioned changing the order of factors. Another possibility is to initialize fact to n and then use factors starting at n ✂ 1 (as long as n 0). You might try out some of these variations and see which you like best
3.4.THE LIMITS OF INT 31 3.4 The Limits of Int So far,I have talked about numeric data types as representations of familiar numbers such as integers and decimal fractions.It is important to keep in mind,however,that these numeric types are just representations, and they do not always behave exactly like the numbers that they represent.We can see an example of this as we test out our new factorial program. >>import factorial Please enter a whole number:6 The factorial of 6 is 720 >>factorial.main() Please enter a whole number:10 The factorial of 10 is 3628800 >>factorial.main() Please enter a whole number:13 Traceback (innermost last): File "<stdin>",line 1,in File "factorial.py",line 9,in main factfact factor OverflowError:integer multiplication Everything seems fine until we try to compute the factorial of 13.When computing 13!the program prints out an OverflowError message.What is going on here? The problem is that this program is representing whole numbers using Python's int data type.Unfortu- nately,ints are not exactly like mathematical integers.There are infinitely many integers,but only a finite range of ints.Inside the computer,ints are stored in a fixed-sized binary representation.To make sense of this,we need to look at what's going on at the hardware level. Computer memory is composed of electrical "switches,"each of which can be in one of two possible states,basically on or off.Each switch represents a binary digit or bit of information.One bit can encode two possibilities,usually represented with the numerals 0(for off)and 1(for on).A sequence of bits can be used to represent more possibilities.With two bits,we can represent four things. bit 2 bit 1 0 0 0 Three bits allow us to represent eight different values by adding a zero or one to each of the four two-bit patterns. bit 3 bit 2 bit 1 0 0 0 0 0 0 0 0 0 1 You can see the pattern here.Each extra bit doubles the number of distinct patterns.In general,n bits can represent 2"different values. The number of bits that a particular computer uses to represent an int depends on the design of the CPU. Typical PCs today use 32 bits.That means there are 232 possible values.These values are centered at 0 to
3.4. THE LIMITS OF INT 31 3.4 The Limits of Int So far, I have talked about numeric data types as representations of familiar numbers such as integers and decimal fractions. It is important to keep in mind, however, that these numeric types are just representations, and they do not always behave exactly like the numbers that they represent. We can see an example of this as we test out our new factorial program. >>> import factorial Please enter a whole number: 6 The factorial of 6 is 720 >>> factorial.main() Please enter a whole number: 10 The factorial of 10 is 3628800 >>> factorial.main() Please enter a whole number: 13 Traceback (innermost last): File "<stdin>", line 1, in ? File "factorial.py", line 9, in main fact = fact * factor OverflowError: integer multiplication Everything seems fine until we try to compute the factorial of 13. When computing 13! the program prints out an OverflowError message. What is going on here? The problem is that this program is representing whole numbers using Python’s int data type. Unfortunately, ints are not exactly like mathematical integers. There are infinitely many integers, but only a finite range of ints. Inside the computer, ints are stored in a fixed-sized binary representation. To make sense of this, we need to look at what’s going on at the hardware level. Computer memory is composed of electrical “switches,” each of which can be in one of two possible states, basically on or off. Each switch represents a binary digit or bit of information. One bit can encode two possibilities, usually represented with the numerals 0 (for off) and 1 (for on). A sequence of bits can be used to represent more possibilities. With two bits, we can represent four things. bit 2 bit 1 0 0 0 1 1 0 1 1 Three bits allow us to represent eight different values by adding a zero or one to each of the four two-bit patterns. bit 3 bit 2 bit 1 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 You can see the pattern here. Each extra bit doubles the number of distinct patterns. In general, n bits can represent 2 n different values. The number of bits that a particular computer uses to represent an int depends on the design of the CPU. Typical PCs today use 32 bits. That means there are 2 32 possible values. These values are centered at 0 to
32 CHAPTER 3.COMPUTING WITH NUMBERS represent a range of positive and negative integers.NowSo the range of integers that can be represented in a 32 bit int value is-231231-1.The reason for the-1 on the high end is to account for the representation of 0 in the top half of the range. Let's try out some expressions in Python to test this analysis.Remember that *is the Python exponen- tiation operator. >>>2**30 1073741824 >>>2**31 Traceback (innermost last): File "<stdin>",line 1,in OverflowError:integer pow ( Python can calculate 230,but"blows up"trying to compute 231.You can see that the overflow happens somewhere between the 30th and 31st power of two.That is consistent with our analysis that the largest int is231-1. Suppose we try to display the largest int. >>>2*★31-1 Traceback (innermost last): File "<stdin>",line 1,in OverflowError:integer pow ( Our first try didn't work.Can you see why?Python evaluates this expression by first trying to calculate 2 *31.That calculation produces the error before Python has a chance to subtract one. We need to be a little cleverer and sneak up on the value from underneath.We can use the fact that 231=230+230.Strategically subtracting one from each side gives us 231-1=230-1+230.By subtracting one in the middle of the computation,we can ensure that the intermediate value never gets bigger than the final result.Here's what Python says: >>>2**30-1+2**30 2147483647 By the way,this expression illustrates another way that Python ints differ from the integers that they represent.In normal arithmetic,there is no difference between 231-1 and 230-1+230.They both represent the same value.In computer arithmetic,however,one is computable and the other is not!Representations of numbers do not always obey all the properties that we take for granted with numbers. Now that we have a numeric value,we can directly test our conjecture that this is the largest int. >>>2147483647 2147483647 >>>2147483648 OverflowError:integer literal too large There you have it.The largest int that can be represented in 32 bits is 2,147,483,647. Now you know exactly why our program for factorial can't compute 13!.This value is larger than the limit of 2,147,483,647.Naturally,the next step is to figure out a way around this limitation. 3.5 Handling Large Numbers:Long Ints As long as our factorial program relies on the int data type,we will not be able to find the factorial of larger numbers.We need to use another numeric type.You might first think of using a float instead.This does not really solve our problem.Here is an example run of a modified factorial program that initializes fact to the float 19
32 CHAPTER 3. COMPUTING WITH NUMBERS represent a range of positive and negative integers. Now 2 32 2 2 31 . So, the range of integers that can be represented in a 32 bit int value is ✂2 31 2 31 ✂ 1. The reason for the ✂1 on the high end is to account for the representation of 0 in the top half of the range. Let’s try out some expressions in Python to test this analysis. Remember that ** is the Python exponentiation operator. >>> 2 ** 30 1073741824 >>> 2 ** 31 Traceback (innermost last): File "<stdin>", line 1, in ? OverflowError: integer pow() Python can calculate 2 30 , but “blows up” trying to compute 2 31 . You can see that the overflow happens somewhere between the 30th and 31st power of two. That is consistent with our analysis that the largest int is 2 31 ✂ 1. Suppose we try to display the largest int. >>> 2 ** 31 - 1 Traceback (innermost last): File "<stdin>", line 1, in ? OverflowError: integer pow() Our first try didn’t work. Can you see why? Python evaluates this expression by first trying to calculate 2 ** 31. That calculation produces the error before Python has a chance to subtract one. We need to be a little cleverer and sneak up on the value from underneath. We can use the fact that 2 31 2 30 ✂ 2 30 . Strategically subtracting one from each side gives us 2 31 ✂ 1 2 30 ✂ 1 ✂ 2 30 . By subtracting one in the middle of the computation, we can ensure that the intermediate value never gets bigger than the final result. Here’s what Python says: >>> 2 ** 30 - 1 + 2 ** 30 2147483647 By the way, this expression illustrates another way that Python ints differ from the integers that they represent. In normal arithmetic, there is no difference between 2 31 ✂ 1 and 2 30 ✂ 1 ✂ 2 30 . They both represent the same value. In computer arithmetic, however, one is computable and the other is not! Representations of numbers do not always obey all the properties that we take for granted with numbers. Now that we have a numeric value, we can directly test our conjecture that this is the largest int. >>> 2147483647 2147483647 >>> 2147483648 OverflowError: integer literal too large There you have it. The largest int that can be represented in 32 bits is 2 ☎ 147 ☎ 483 ☎ 647. Now you know exactly why our program for factorial can’t compute 13!. This value is larger than the limit of 2 ☎ 147 ☎ 483 ☎ 647. Naturally, the next step is to figure out a way around this limitation. 3.5 Handling Large Numbers: Long Ints As long as our factorial program relies on the int data type, we will not be able to find the factorial of larger numbers. We need to use another numeric type. You might first think of using a float instead. This does not really solve our problem. Here is an example run of a modified factorial program that initializes fact to the float 1 0