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-231...231-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 1.0
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
3.5.HANDLING LARGE NUMBERS:LONG INTS 33 Please enter a whole number.15 The factorial of 15 is 1.307674368e+12 We do not get an overflow error,but we also do not get an exact answer. A very large(or very small)floating point value is printed out using exponential,or scientific,notation. The e+12 at the end means that the result is equal to 1.307674368=1012.You can think of the+12 at the end as a marker that shows where the decimal point should be placed.In this case,it must move 12 places to the right to get the actual value.However,there are only 9 digits to the right of the decimal,so we have"lost" the last three digits. Remember,floats are approximations.Using a float allows us to represent a much larger range of values, but the amount of precision is still fixed.In fact,a computer stores floating point numbers as a pair of fixed- length (binary)integers.One integer represents the string of digits in the value,and the second represents the exponent value that keeps track of where the whole part ends and the fractional part begins. Fortunately,Python provides a better solution for large,exact values in the form of a third numeric type long int.A long int is not a fixed size,but expands to accommodate whatever value it holds.The only limit is the amount of memory the computer has available to it.To get a long int,you put an"L"suffix on a numeric literal.So,the literal 5 is an int representation of the number five,but 5L is a long int representation of the number five.Of course,for a number this small,there is no reason to use a long int.However,using a long int causes Python to use long int operations,and our value can grow to any size.Here are some examples that illustrate: >>>2L 2L >>>2L**31 2147483648L >>>type(100L) <type 'long int'> >>>10000000000000000000000000000000000000L+25 10000000000000000000000000000000000025L Notice how calculations involving a long int produce a long int result.Using long ints allows us to compute with really large numbers. We can modify our factorial program to use long int by simply initializing fact to 1L.Since we start with a long int,each successive multiplication will produce another long int. factorial2.py def main(): n input ("Please enter a whole number:" fact 1L Use a long int here for factor in range(n,0,-1): factfact factor print "The factorial of",n,"is",fact Now we can take the factorial of arbitrarily large inputs. >>import factorial2 Please enter a whole number:13 The factorial of 13 is 6227020800 >>factorial2.main() Please enter a whole number:100 The factor1a1of100is933262154439441526816992388562667004907159682 643816214685929638952175999932299156089414639761565182862536979208272 23758251185210916864000000000000000000000000
3.5. HANDLING LARGE NUMBERS: LONG INTS 33 Please enter a whole number. 15 The factorial of 15 is 1.307674368e+12 We do not get an overflow error, but we also do not get an exact answer. A very large (or very small) floating point value is printed out using exponential, or scientific, notation. The e+12 at the end means that the result is equal to 1 307674368 1012 . You can think of the +12 at the end as a marker that shows where the decimal point should be placed. In this case, it must move 12 places to the right to get the actual value. However, there are only 9 digits to the right of the decimal, so we have “lost” the last three digits. Remember, floats are approximations. Using a float allows us to represent a much larger range of values, but the amount of precision is still fixed. In fact, a computer stores floating point numbers as a pair of fixedlength (binary) integers. One integer represents the string of digits in the value, and the second represents the exponent value that keeps track of where the whole part ends and the fractional part begins. Fortunately, Python provides a better solution for large, exact values in the form of a third numeric type long int. A long int is not a fixed size, but expands to accommodate whatever value it holds. The only limit is the amount of memory the computer has available to it. To get a long int, you put an “L” suffix on a numeric literal. So, the literal 5 is an int representation of the number five, but 5L is a long int representation of the number five. Of course, for a number this small, there is no reason to use a long int. However, using a long int causes Python to use long int operations, and our value can grow to any size. Here are some examples that illustrate: >>> 2L 2L >>> 2L ** 31 2147483648L >>> type(100L) <type ’long int’> >>> 10000000000000000000000000000000000000L + 25 10000000000000000000000000000000000025L Notice how calculations involving a long int produce a long int result. Using long ints allows us to compute with really large numbers. We can modify our factorial program to use long int by simply initializing fact to 1L. Since we start with a long int, each successive multiplication will produce another long int. # factorial2.py def main(): n = input("Please enter a whole number: ") fact = 1L # Use a long int here for factor in range(n,0,-1): fact = fact * factor print "The factorial of", n, "is", fact Now we can take the factorial of arbitrarily large inputs. >>> import factorial2 Please enter a whole number: 13 The factorial of 13 is 6227020800 >>> factorial2.main() Please enter a whole number: 100 The factorial of 100 is 933262154439441526816992388562667004907159682 643816214685929638952175999932299156089414639761565182862536979208272 23758251185210916864000000000000000000000000
34 CHAPTER 3.COMPUTING WITH NUMBERS If you have an older version of Python (prior to version 2.0),these answers will be printed with an "L" appended.This is Python's way of saying that the number is a long int.In newer versions,this artifact is automatically removed by the print statement.In the next chapter,you will learn how you could take care of getting the"L"out yourself. Now we have a factorial program that can compute interestingly large results.Long ints are pretty cool; you might be tempted to use them all the time.The down-side of using long ints is that these representations are less efficient than the plain int data type.The operations needed to do arithmetic on ints is built into the CPU of the computer.When doing operations on long ints,Python has to employ algorithms that simulate long arithmetic using the computer's built-in fixed-length operations.As a result,long int arithmetic is much slower than int arithmetic.Unless you need very large values,ints are preferred. 3.6 Type Conversions Sometimes values of one data type need to be converted into another.You have seen that combining an int with an int produces an int,and combining a float with a float creates another float.But what happens if we write an expression that mixes an int with a float?For example,what should the value of x be after this assignment statement? ×=5.0/2 If this is floating point division,then the result should be the float value 2.5.If integer division is performed, the result is 2.Before reading ahead for the answer,take a minute to consider how you think Python should handle this situation. In order to make sense of the expression 5.0 2,Python must either change 5.0 to 5 and perform integer division or convert 2 to 2.0 and perform floating point division.In general,converting a float to an int is a dangerous step,because some information(the fractional part)will be lost.On the other hand,an int can be safely turned into a float just by adding a fractional part of.0.So,in mixed-typed expressions,Python will automatically convert ints to floats and perform floating point operations to produce a float result. Sometimes we may want to perform a type conversion ourselves.This is called an explicit type conver- sion.For example,suppose we are writing a program that finds the average of some numbers.Our program would first sum up the numbers and then divide by n,the count of how many numbers there are.The line of code to compute the average might look like this. average sum /n Unfortunately,this line may not always produce the result we intend. Consider a specific example.The numbers to be averaged are the ints 4,5,6,7.The sum variable will hold 22,also an int,and dividing by 4 gives the answer 5,not 5.5.Remember,an int divided by an int always produces an int. To solve this problem,we need to tell Python to convert one of the operands to a floating point value. average float(sum)/n The float (function converts an int into a float.We only need to convert the numerator,because this produces a mixed-type expression,and Python will automatically convert the denominator. Notice that putting the float (around the entire expression would not work. average float(sum/n) In this form,sum and n could both be ints causing Python to perform an integer division and then convert the resulting quotient to a float.Of course,this float would always end in.0,since it is being converted from an int.That is not what we want. Python also provides int (and long()functions that can be used to convert numbers into ints and longs,respectively.Here are a few examples
34 CHAPTER 3. COMPUTING WITH NUMBERS If you have an older version of Python (prior to version 2.0), these answers will be printed with an “L” appended. This is Python’s way of saying that the number is a long int. In newer versions, this artifact is automatically removed by the print statement. In the next chapter, you will learn how you could take care of getting the “L” out yourself. Now we have a factorial program that can compute interestingly large results. Long ints are pretty cool; you might be tempted to use them all the time. The down-side of using long ints is that these representations are less efficient than the plain int data type. The operations needed to do arithmetic on ints is built into the CPU of the computer. When doing operations on long ints, Python has to employ algorithms that simulate long arithmetic using the computer’s built-in fixed-length operations. As a result, long int arithmetic is much slower than int arithmetic. Unless you need very large values, ints are preferred. 3.6 Type Conversions Sometimes values of one data type need to be converted into another. You have seen that combining an int with an int produces an int, and combining a float with a float creates another float. But what happens if we write an expression that mixes an int with a float? For example, what should the value of x be after this assignment statement? x = 5.0 / 2 If this is floating point division, then the result should be the float value 2 5. If integer division is performed, the result is 2. Before reading ahead for the answer, take a minute to consider how you think Python should handle this situation. In order to make sense of the expression 5.0 / 2, Python must either change 5.0 to 5 and perform integer division or convert 2 to 2.0 and perform floating point division. In general, converting a float to an int is a dangerous step, because some information (the fractional part) will be lost. On the other hand, an int can be safely turned into a float just by adding a fractional part of 0. So, in mixed-typed expressions, Python will automatically convert ints to floats and perform floating point operations to produce a float result. Sometimes we may want to perform a type conversion ourselves. This is called an explicit type conversion. For example, suppose we are writing a program that finds the average of some numbers. Our program would first sum up the numbers and then divide by n, the count of how many numbers there are. The line of code to compute the average might look like this. average = sum / n Unfortunately, this line may not always produce the result we intend. Consider a specific example. The numbers to be averaged are the ints 4, 5, 6, 7. The sum variable will hold 22, also an int, and dividing by 4 gives the answer 5, not 5.5. Remember, an int divided by an int always produces an int. To solve this problem, we need to tell Python to convert one of the operands to a floating point value. average = float(sum) / n The float() function converts an int into a float. We only need to convert the numerator, because this produces a mixed-type expression, and Python will automatically convert the denominator. Notice that putting the float() around the entire expression would not work. average = float(sum/n) In this form, sum and n could both be ints causing Python to perform an integer division and then convert the resulting quotient to a float. Of course, this float would always end in 0, since it is being converted from an int. That is not what we want. Python also provides int() and long() functions that can be used to convert numbers into ints and longs, respectively. Here are a few examples