Previous | Table of Contents | Next |
In Fortran, the programmer can create generic procedures, define new operators, and extend the definition of intrinsic functions, existing operators, and assignment. These features will be illustrated by constructing a new data type for computing with large integers.
The Fortran intrinsic integer type has a limit on the size of numbers it can represent; the largest integer can be determined on any Fortran system as the value of the intrinsic function huge(0). A typical limit is 2311, which is 2,147,483,647. This problem can be solved by creating a new data type, called big_integer, deciding which operations are needed, and writing procedures that perform the operations on values of this type. All of this will be placed in a module called big_integers.
1.2.18.1. The Type Definition for Big Integers
The first task is to decide how these large integers will be represented. Although a linked list of digits is a possibility, it seems more straightforward to use an array of ordinary Fortran integers. The only remaining thing to decide is how much of a big integer to put into each element of the array. One possibility is to put as large a number into each element as possible. To make it easier to conceptualize with simple examples, I store one decimal digit in each element. However, because the abstract data type paradigm is followed, changing the representation so that larger integers are stored in each array element can be implemented easily without changing the programs that use the big_integer module.
The following type definition example does the job. This type definition uses a parameter nr_of_digits that has arbitrarily been set to 100, which allows decimal numbers with up to 100 digits to be represented using this scheme. The parameter nr_of_digits has the private attribute, which means it cannot be accessed outside the module:
integer, parameter, private :: nr_of_digits = 100 type, public :: big_integer private integer, dimension (0 : nr_of_digits) :: digit end type big_integer
The array digit has 101 elements: digit(0) holds the ones digit, digit(1) holds the tens digit, digit(2) holds the hundreds digit, and so on. The extra element in the array is used to check for overflow. If any value other than 0 gets put into the largest element, that is considered to exceed the largest big_integer value, and after we have extended the intrinsic function huge, the value is set to the largest possible big integer. The private statement indicates that we dont want anybody that uses the module to be able to access the component digit of a variable of type big_integer, even though the type itself is public; we provide all the operations necessary to compute with such values.
The next thing to do is to define some operations for big integers. The first necessary operations assign values to a big integer and print the value of a big integer. Lets take care of the printing first. The following subroutine prints the value of a big integer. It takes advantage of the fact that each element of the array digit is one decimal digit. This subroutine print_big is inside the module big_integers, so it has access to all the data and procedures in the module:
subroutine print_big (b) type (big_integer), intent (in) :: b integer :: n, first_significant_digit character (len = 10) :: format ! Find first significant digit first_significant_digit = 0 ! In case b = 0 do n = nr_of_digits, 1, -1 if (b % digit (n) /= 0) then first_significant_digit = n exit end if end do ! Set format = (<first_significant_digit+1>i1) write (unit = format, fmt = (a, i6, a)) & (, first_significant_digit + 1, i1) print format, & b % digit (first_significant_digit : 0 : -1) end subroutine print_big
The basic strategy is to print the digits in i1 format, where each digit occupies one character position in the output, but first the leftmost nonzero digit must be located, both to compute the multiplier in the format specification and to avoid printing long strings of leading zeros. This way, there is also no problem if the parameter nr_of_digits is changed.
Another interesting feature is that we use a formatted write to a character variable to convert an integer subscript to character form for inclusion in an edit descriptor. In effect, we calculate the appropriate print format on-the-fly.
To test this subroutine, we need a way to assign values to a big integer. One possibility is to write a procedure that assigns an ordinary Fortran integer to a big integer, but this limits the size of the integer that can be assigned. A second possibility is to write the integer as a character string consisting of only digits 09. (We are not allowing negative numbers.) This is done by the subroutine big_gets_char(b,c) that assigns the integer represented by the character string c to the big integer b. If c contains a character other than one of the digits or c contains more digits than can be stored in b, the value huge(b) is assigned:
subroutine big_gets_char (b, c) type (big_integer), intent (out) :: b character (len = *), intent (in) :: c integer :: n, i if (len (c) > nr_of_digits) then b = huge (b) return end if b % digit = 0 n = 0 do i = len (c), 1, -1 b % digit (n) = index (0123456789, c (i:i)) - 1 if (b % digit (n) == -1) then b = huge (b) return end if n = n + 1 end do end subroutine big_gets_char
Previous | Table of Contents | Next |