3
$\begingroup$

While browsing a disk image from the Soviet mainframe BESM-6, I've found some bits and pieces of a computational math library for Algol-60, stored in plaintext (if the Soviet GOST 10859 encoding with parity, as if on punched cards, can be considered plaintext).

One function is of particular interest because of an error message expressed in a jocular/familiar style. The function name means LAGRANGE2, and a few single-letter Cyrillic variable names should not be too confusing.

I've added spaces, indented and reflowed the text for readability:

_REAL _PRОCEDURE ЛАГРАНЖ2(A,Х,У,Х1,Х2,P,П,П1);
_REAL Х1, Х2; _INTEGER P, П, П1; _ARRAУ A, Х, У;
_BEGIN
_REAL S, Z, Z1;
_INTEGER I, J, J1, К;
_ARRAУ S1[0:20];
_INTEGER Я, Я1;
    _IF Х2 < A[1] _THEN _BEGIN
        Z := Х2;
        _GО _TО М3;
    _END ;
    _IF Х1 < Х[1] _THEN _BEGIN
        Z := Х1;
        _GО _TО М3;
    _END ;
    S := 0;
    _FOR J1 := 1 _STEP 1 _UNTIL П1 _DО
        _IF Х2 ≥ A[J1] ∧ Х2 ≤ A[J1+1] _THEN
            _GО _TО М1;
    Z := Х2;
    _GО _TО М2;
    М1: _FOR I := 1 _STEP 1 _UNTIL П _DО
    _IF Х1 ≥ Х[I] ∧ Х1 ≤ Х[I+1] _THEN
        _GО _TО М;
    Z := Х1;
    _IF Х1 ≤ Х[П] _THEN
        _GО _TО М;
    М2: _IF Х2 ≤ A[П1] _THEN
        _GО _TО М;
    М3: ОUTPUT(‘T’,‘ПРИ  ОБРАЩЕНИИ  К  ПРОЦЕДУРЕ  ЛАГРАНЖ2  АРГУМЕНТ=’,
        ‘E’,Z,‘T’,
        ‘ВЫШЕЛ  ЗА  ПРЕДЕЛЫ  ТАБЛИЦЫ. РАЗБЕРИСЬ  В  ЧЕМ  ДЕЛО, А  Я  ПРЕРЫВАЮ  СЧЕТ. ДО  ВСТРЕЧИ!’);
    ОUTPUT(‘×’);
    S := S / 0;
    М: _IF I ≤ П - P _THEN
        J := I
    _ELSE
        J := П - P;
    _IF J1 > П1 - P _THEN
        J1 := П1 - P;
    Я1 := J1;
    _FOR Я := 0 _STEP 1 _UNTIL P _DО _BEGIN
        S := 0;
        _FOR I := 0 _STEP 1 _UNTIL P _DО _BEGIN
            Z := Z1 := 1;
            _FOR К := 0 _STEP 1 _UNTIL P _DО _BEGIN
                _IF К ≠ I _THEN
                    Z := Z × (Х1 - Х[К+J]) / (Х[I+J] - Х[К+J]);
            _END ;
            S := S + У[I + J + (J1 - 1) × П] × Z;
        _END ;
        S1[Я] := S;
        J1 := J1 + 1;
    _END ;
    S := 0;
    _FOR I := 0 _STEP 1 _UNTIL P _DО _BEGIN
        Z := Z1 := 1;
        _FOR К := 0 _STEP 1 _UNTIL P _DО _BEGIN
            _IF К ≠ I _THEN
                Z := Z × (Х2 - A[К + Я1]) / (A[I + Я1] - A[К + Я1]);
        _END ;
        S := S + S1[I] × Z;
    _END ;
    ЛАГРАНЖ2 := S;
_END 

The error message means "When calling the LAGRANGE2 procedure, the argument value was outside the table. Find out what is the issue, and I am interrupting the calculation. SEE YOU!". After printing the message, a divide-by-zero error is forced.

What was that function calculating? A guess would be Lagrange interpolation, but computing all the coefficients only to produce a single result would be wasteful. Moreover, there are 3 input arrays instead of the expected two.

$\endgroup$

1 Answer 1

3
$\begingroup$

From the name, the error message, and the code, it appears that this code is doing Lagrange polynomial interpolation for a function $f(x)$, given

$x_{1} < x_{2} < \ldots < x_{n}$

and function values

$f(x_{1}), f(x_{2}), \ldots, f(x_{n})$

You can use a Lagrange interpolation polynomial to interpolate the value of $f(x)$ at any point $x$ where $x_{1} < x < x_{n}$. The method is unreliable (and the code refuses to accept) for values of $x$ outside of the range of $x$ values in the table.

$\endgroup$
5
  • $\begingroup$ That had been my first guess (see the last paragraph of the question), but the values of x_n, and f(x_n) would occupy two arrays, and the function takes three array arguments, all of which are used as input. $\endgroup$
    – Leo B.
    Jan 10 at 22:03
  • 1
    $\begingroup$ If you look at the code, you'll see that the scalar x1 input is used with Lagrange polynomials over the x array while x2 is used with Lagrange polynomials over the points in the A array. It appears to be evaluating two Lagrange interpolations in the same subroutine call. $\endgroup$ Jan 10 at 22:19
  • $\begingroup$ I agree that Lagrange interpolation evaluations are present in the code, but the overall function of the whole thing eludes me. $\endgroup$
    – Leo B.
    Jan 10 at 22:55
  • 1
    $\begingroup$ Could it be a 2D interpolation, with y = f(A,X)? $\endgroup$
    – Charlie S
    Jan 11 at 1:53
  • $\begingroup$ @CharlieS Looks plausible, but the layout of the Y array is not very clear. $\endgroup$
    – Leo B.
    Jan 11 at 8:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.