Complex numbers in the library

[Brian Hawley <bhawley@luc.edu>]

Hi all!

I have a couple questions that relate to the efficiency of the
implementation of complex numbers in the library. Perhaps this should be
addressed to Griebling, but I thought that the rest of us would have some
input. These questions assume the declaration:
  TYPE
    COMPLEX = POINTER TO COMPLEXDesc;
    COMPLEXDesc = RECORD r, i: (*LONG*)REAL END;

As I see it, there are three notations to choose from for the implementation
of complex math:

- Functional, i.e. PROCEDURE sin(x: COMPLEX): COMPLEX;
  - Advantages: Mathematical notation should be much easier to use.
  - Disadvantages: Allocates a number on the heap with every invocation,
which      is essentially a side effect and which would be extremely
inefficient, both
    in time and in heap fragmentation; also has space overhead for both the
record header and the pointer. Overcoming these would require some rather 
    difficult heap object lifetime analysis and a more advanced collector.

- Procedural, i.e. PROCEDURE sin(x: COMPLEXDesc; VAR ret: COMPLEXDesc);
  - Advantages: Greater space efficiency, allows the programmer to choose 
    whether or not to heap-allocate the numbers. This style allows you to use 
    arrays of COMPLEXDesc records when doing matrix/vector work. Such arrays 
    have been typically implemented with one type header for the array and one
    for _all_ of the elements. If the elements had to be allocated individually,
    there would be a space overhead of the pointer and a type header for _each_
    element. This would get very big, very quick, and become very fragmented.
  - Disadvantages: Using this notation would not be as easy for the programmer.
    The users of this library would have to allocate the space for the numbers
    themselves, and manage all of the temporaries. Many mathematicians would
    like to avoid having to do this because it confuses the algorithms with
    implementation details. 

- Recycling Functional, i.e. PROCEDURE sin(x, ret: COMPLEX): COMPLEX;
  The second parameter is either given a pointer to a preallocated COMPLEXDesc
  that can be reused, or NIL. The result is returned from the function, either 
  the recycled record or a newly allocated one with new values filling it.
  - Advantages: Can be used in a functional style with only minor wierdness 
    (none in a language with optional parameters, but that's another matter :).
    If we are careful to minimize aliasing effects in the implementation, this
    notation can be used to speed calculation dramatically and cut down on heap
    fragmentation. The programmer that uses these functions can allocate one or
    two temporaries early on, and these temporaries can be reused over and over
    again. The compiler and collector would have fewer objects to do lifetime
    analysis with. If the programmer doesn't want to go through the trouble of 
    allocating temporaries, this notation has the same characteristics of the
    first notation (you always have had to choose to recycle :).
  - Disadvantages: This still has that space and time overhead of heap objects,
    and doesn't strictly follow the math notation. The programmer has to do a
    little work to speed things up that would be done by the compiler with the 
    procedural notation.

Complex math is currently implemented with the functional notation in the
library. Here's my proposal for how the library could be implemented:

- Modules LowComplexMath and LowLongComplexMath, done in the Procedural style,
  and exporting the COMPLEX and COMPLEXDesc types.
- Modules ComplexMath and LongComplexMath, done in the Recycling Functional
  style, implemented using the Low* modules, and exporting aliases to the Low*
  types as their own.
- Other modules yet to be determined that do math on arrays of COMPLEXDesc, 
  using the Low* modules to do their dirty work.

This arrangement would allow you to do math in the functional style where it
matters, i.e. with individual complex numbers, but would still allow you to
use the procedural style where you really need to minimize overhead, i.e.
when you are working with arrays or other large quantities of numbers.

So what do you think?
Brian Hawley
bhawley@luc.edu