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.

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 x 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 ** 31 2147483648L >>> type(10 0L) <type 'long int'>

>>> 10000000000000000000000000000000000000L + 25 1000000000000000000000000000000000002 5L

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

Please enter a whole number: 100

The factorial of 100 is 933262154439441526816992388562667004907159682 643816214 685 92 9638952175999 93 2299156 08 9414 639761565182862 53 69792 082 72 2375825118 5210916864000000000000000000000000

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.