*** The following was the original documentation supplied by the author,
*** Rob Sykes, with the package. In this package the files mentioned below
*** were all supplied in a single `directory'. For the CALGO distribution
*** these files have been split into a number of directories according
*** to implementation language and use. The supplied Makefile has been
*** very slightly altered to allow it to execute correctly with the new
*** file layout and expected results files have also been added. 
***
*** Tim Hopkins (April 28 2020)
                               _  _    ___   ___
                              | || |  / _ \ / _ \
                              | || |_| | | | (_) |
                              |__   _| |_| |\__, |
                                 |_|  \___/   /_/

OVERVIEW

    This package contains materials supplementary to ‘Algorithm 409, Discrete
    Chebychev Curve Fit’ by H. Schmitt, ‘Communications of the ACM’, May 1971,
    Volume 14 Number 5, pp. 355–356.

    The files contained are:
        409.pres    Transcript of the 1971 article (in ‘presentation’ Algol).
        409.algol    Conversion of the above to ‘MARST’-compatible Algol.
                     (contributed by T. R. Hopkins).
        409.c        Translation to C of 409.algol.
        main.c       Test programme in C.
        Makefile     Build rules.
        plots        Plots results.
        README       This file.

    Files are UTF-8 encoded.


LICENSING

    Files 409.pres, 409.algol, and 409.c are made available under the terms of
    the ‘ACM Software License Agreement’ at
    https://www.acm.org/publications/policies/software-copyright-notice

    All other files in the package are made available under the terms of the
    ‘(un)licensing statement’ at https://unlicense.org


DESCRIPTION

    The transcript, 409.pres, was obtained via OCR as a faithful reproduction
    of the original text.  As such, it includes a few typographical oddities of
    the original, such as ‘to go’ used instead of ‘go to’ and inconsistent use
    of some symbols, e.g. minus vs. hyphen, ≤ vs. ≦.  A machine-processable
    version of the original programme would likely have been ‘stropped’,
    allowing keywords (rendered as bold text in the article) and identifiers to
    be parsed in separate spaces (e.g. ‘end’ is used both as a keyword and as a
    label in this programme).  Stropping has not been applied in the transcript.

    Translation to C was chosen as the means to exercise this programme,
    considering that:
      • modern C now has most of Algol’s language features,
      • mapping Algol syntax to C is straightforward,
      • C compilers are commonplace whilst Algol tools are now scarce.

    The translation from Algol to C was largely automated, using a series of
    ‘sed’ text substitutions that dealt with both regular syntax differences and
    the aforementioned typographical and lexical issues.  A small number of
    manual modifications were needed, including changes to the procedure
    declarations, and using return codes to emulate Algol’s inter-procedural ‘go
    to’.  To quash compiler warnings, three variables (in line #97) were given
    initialisation values.  The resultant C implementation, 409.c, is believed
    to behave identically to the original Algol (excepting, owing to the
    initialisations, abnormal cases).

    The test programme, main.c, performs a selection of function approximations
    in order to exercise the implementation.  This, according to the ‘gcov’
    analysis tool, achieves source-code coverage of 100%.

    Files 409.c and main.c are compatible with gcc and with C++11 onwards.


INSTRUCTIONS

    For a unix-like system:

    To build the test programme, enter:
        make           To build with gcc.
    or:
        make cc=arg    With arg ∈ {gcc, g++, 'clang -x c++'}.

    To run the test programme, enter:
        ./409          To run all tests, with summary output.

        ./409 n        To run test #n, n ≥ 0, with polynomial coefficients and
                       summary output.

        ./409 n h      As above but also stores normalised approximation error
                       data in the file named ‘h’.

    To check (per the programme documentation) the error function of one
    test, use, for example, one of:
        Octave:        plot(load('h'))
        gnuplot:       plot 'h' with lines

    Or, to plot the error function of all tests as PNG files (using gnuplot),
    enter one of:
        ./plots        Plots the error value.
        ./plots abs    Plots the error magnitude.

    Note that plots as described above show the error function only as it
    corresponds to the given domain (i.e. non-negative for odd or even functions
    with k non-zero).  For approximations made on multiple domain intervals, the
    corresponding error function will appear concatenated.


OBSERVATIONS

    1. On an x86_64 system with gcc 8.3.0 and clang 8.0.0-3, all three compiler
    options (cc=arg, above) produced the same coefficients, and the same summary
    output as follows:

       # exit its    hmax     k   m  Expression for f(x)    Domain intervals
       0   -   0  0.0000e+00  0   3  (x-1)*(x-2)*(x-3)      0:4
       1  PAR 19         inf  1   9  sin(pi/2*x)            0:1
       2  SIG  0  2.0039e-11  0  17  log2(x)                1:2
       3  MAX 19  3.7956e-03  0  31  sin(exp(3*x))          -1:1
       4   -   2  1.7154e-07  0   6  sqrt(x)                1:2
       5   -   4  1.7154e-07  0  -6  sqrt(x)                1:2
       6   -  11  1.0000e+00  0   8  cos(x)+cos(21*x+1)     -1:1
       7   -   4  1.4321e-01  0  10  1-sin(5*fabs(x-.5))    -1:1
       8   -   8  5.0712e-02  0  15  x>.4                   -1:0.3  0.5:1
       9   -   6  5.1143e-02  0   4  asin(x)                -1:-0.9  0.9:1
      10   -   2  5.1143e-02  1   3  asin(x)                0.9:1
      11   -   1  1.3179e-05  1   7  erf(x)                 1e-12:1
      12   -   1  3.3381e-09  1   9  sin(pi/2*x)            1e-12:1
      13   -   3  2.7845e-02  2  10  fabs(x)                0:1
      14   -   7  3.1218e-02  2  14  x<.7                   0:0.6  0.8:1
      15   -   5  1.9556e-01  2  12  asin(cos(x*pi*3))      0:1

    2. Execution on an ARM7 system with gcc produced the same coefficients and
    summary output as with the x86_64 system, for all tests excepting
    (unsuccessful) test #2.

    3. In test #0, both the approximating and the approximated functions are
    third-order polynomials; the resultant reported approximation error is
    zero.

    4. The programme’s three ‘emergency exits’ are exercised in test #s 1–3.

    5. Per the example shown in figure 1 below, the approximation error function
    for test #s 3–15 show well-characterised local extrema.  Specifically,
    mixed approximations (i.e. test #s 3–8) exhibit M+2 maximal error points
    with alternating signs (where M is the approximation order) and odd or even
    approximations (i.e. test #s 9–15) yield M+3 such alternations.  Note that
    some approximation error functions exhibit additional non-maximal local
    extrema and that the non-maximality of such may be not be easily visually
    discernible.  For example, the normalised error function in test #14 has
    non-maximal local extrema at abscissa ±1 with value −0.9999974.

        ___________________________________________________________________
       |                                                                   |
    +1 +··········ooo····································oo··············o·|
       |       oooo oooo                               oooooo            o |
       |      oo       oo                             oo    oo           o |
       |    ooo         oo                           oo      oo          o |
       |   oo            ooo                        oo        o          o |
       |  oo               oo                      oo         oo         o |
       | oo                 o                     oo           o        o  |
       |oo                  oo                    o            oo       o  |
     0 +o····················oo··················oo·············o·······o··|
       |                      oo                oo              oo      o  |
       |                       oo              oo                o      o  |
       |                        oo             o                 oo    oo  |
       |                         oo           oo                  o    o   |
       |                          oo         oo                   oo   o   |
       |                           ooo     ooo                     oo oo   |
       |                             ooo ooo                        ooo    |
    −1 +·······························ooo···························oo····|
       |___________________________________________________________________|

                Figure 1. Normalised approximation error (test #11)

    6. Though test #3 produced satisfactory results, convergence was not
    detected.  This is attributed to approaching the limits of machine precision
    in this test; i.e. here, numerical issues give rise to noise in the error
    function and consequently, jitter in the extrema.  For this reason, there
    may be slight variation in the results for this test on some systems.

    7. Test #s 4 and 5 perform the same approximation; however, the initial
    reference abscissae for the former have the default (Chebyshev) spacing,
    whilst they are linearly-spaced for the latter.  The two tests produced
    identical polynomial coefficients but test #5 needed more exchange
    iterations before convergence was achieved.

    8. With this implementation, odd or even function approximation necessitates
    particular parametrisation.  Test #s 10–15 exemplify the documented method
    of setting k non-zero and the domain non-negative.  An alternative (but
    deprecated) approach is to set m to degree+1 and to leave k and the domain
    unchanged.  The two approaches as applied to the same approximation can be
    seen in tests #s 9 and 10.


CONCLUSIONS

    The above observations were all as expected or justifiable.  Schmitt’s
    implementation can be commended for its capability, usability and
    presentation which, 50 years later, remain impressive.


ACKNOWLEDGEMENT

    Thanks are due to T. R. Hopkins for reviewing this work.

                                           R. Sykes <robs@users.sourceforge.net>
                                                                      April 2020
