Programming Languages assignment III

Assignment III

Due date Tuesday February 27 and March 6.


The purpose of this assignment to design and implement some procedures to
manipulate floating-point numbers of arbitrary size. There is a successful
FORTRAN program of this kind, developed at NASA that supports a full library
of elementary functions that are evaluated to arbitrary precision. In this 
assignment we will examine the core of such a system, namely the representation
of numbers, and simple arithmetic.

1) Floating point numbers are represented as a record with three components:

a) A sign bit (can be a short integer).

b) An exponent: a 32-bit integer will suffice. The exponent represents a
power of 10.

c) A mantissa. The Mantissa is an array of digits, of arbitrary size. The
simplest is to represent the mantissa component as a pointer to an array
of digits, represented in a certain base. It turns out that the simplest
is to use a base that is a power of 10, because this makes input and output
simplest. So the base should be 10,000, and each digit therefore is an
number between 0 and 9999. In this fashion, multiplication of two digits
is always less than 32 bits, so there is no problem with overflow.

2) Arithmetic on such numbers is performed using the standard rules for
floating point operations:

a) For addition, the exponents must be equal, and the result is the result
of adding the mantissas. If the exponents are not equal, then the larger
exponent is adjusted (reduced) and the mantissa is increased by the corresponding power
of 10:
          15 * 10 ^4 = 1500 * 10^2

          12 * 10^6 + 34 * 10^2 = 120000 * 10^2 + 34 * 10^2 = 12034 * 10^2

b) For multiplication, the exponents are added and the mantissas are
multiplied.

For this assignment you will write a package that implements these operations,
and a short program to test it.

For the first part of the assignment (due Feb. 27), do the following:

Complete the following package declaration, and implement the operations
Create, Adjust, and Image. the mantissa should be stored from least-significant
to most-significant digit. This will simplify the arithmetic routines. For
this assignment assume that numbers are always positive.

package Large_Numbers is
   Base : constant := ...
   type Mantissa_digits is array ...
   type Mantissa_Ref is ..
   type Large_Number is record ...

   Zero: constant Large_Number := (...);
   One : constant Large_Number := (...);

   function Create (Mantissa: Integer; Exponent: Integer) return Large_Number;
   --  Build a large number (assumed positive) given the mantissa, as a 32
   --  bit integer, and the exponent. Note that the mantissa can have more
   --  than one digit.

   function Image (Num : Large_Number) return String;

   --  The external representation of a number is the usual scientific notation:
   --  123451234512345E12000,   
   --  Note that the exponent can be negative.

   function Adjust (Num : Large_Number; Bias : Integer) return Large_Number; 
   function "+" (N1, N2: Large_Number) return Large_Number;
   function "*" (N1, N2: Large_Number) return Large_Number; 
end Large_Numbers;

For the second part of the assignment, implement addition and multiplication.

a) For addition you want to develop a function to do addition of integers
represented as arrays of digits. 

          function Add_Mantissa (M1, M2 : Mantissa_Ref) return Mantissa_Ref;

The algorithm is like that of manual addition: add two digits, if larger than
base then subtract base and carry, and keep going from least significant to
most significant digit. The length of the result (the number of digits) is at
most one larger than the larger of the two operands.

b) For multiplication, you need to develop a similar function:

       function Multiply_Mantissa (M1, M2 : Mantissa_Ref) return Mantissa_Ref;

The algorithm uses the addition already developed. The size of the result is at
most the sum of the number of digits of the operands.

c) The test should be a procedure that computes and prints the factorials
of 100, 200, 300 in full. There will be lots of zeros at the end, so the
best is to put all the trailing zeros in the exponent. THis is an optional
frill.