NUMAL Section 1.4

BEGIN SECTION : 1.4 (October, 1974)

AUTHOR: H.J.J. TE RIELE.

INSTITUTE: MATHEMATICAL CENTRE.

RECEIVED: 740125; REVISED: 740514;

BRIEF DESCRIPTION:

    THIS SECTION CONTAINS A SET OF FIVE PROCEDURES FOR
    THE BASIC ARITHMETIC OPERATIONS WITH LONG INTEGERS:
    LNG INT ADD EXACTLY COMPUTES THE SUM OF TWO NONNEGATIVE INTEGERS.
    LNG INT SUBTRACT EXACTLY COMPUTES THE DIFFERENCE OF TWO NONNEGATIVE
    INTEGERS.
    LNG INT MULT EXACTLY COMPUTES THE PRODUCT OF TWO NONNEGATIVE
    INTEGERS.
    LNG INT DIVIDE EXACTLY COMPUTES THE QUOTIENT WITH REMAINDER OF TWO
    NONNEGATIVE INTEGERS.
    LNG INT POWER EXACTLY COMPUTES U**POWER,
    WHERE U IS A NONNEGATIVE LONG INTEGER AND POWER IS THE
    POSITIVE (SINGLE-LENGTH) EXPONENT.

KEYWORDS:

    LONG INTEGER ARITHMETIC,
    ADDITION,
    SUBTRACTION,
    MULTIPLICATION,
    DIVISION WITH REMAINDER,
    EXPONENTIATION.


SUBSECTION : LNG INT ADD.

CALLING SEQUENCE :

    THE HEADING OF THE PROCEDURE READS:
    "PROCEDURE" LNG INT ADD(U,V,SUM);
    "INTEGER" "ARRAY" U,V,SUM;
    "CODE" 31200;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    U,V,SUM: <ARRAY IDENTIFIER>;
            "INTEGER" "ARRAY" U[0:U[0]], V[0:V[0]],
                              SUM[0:MAX(U[0],V[0])+1];
            BEFORE THE CALL OF LNG INT ADD, U AND V MUST
            CONTAIN THE LONG INTEGERS TO BE ADDED;
            AFTER THE CALL, SUM CONTAINS THE MULTI-LENGTH
            SUM OF U AND V, WHILE U AND V REMAIN UNCHANGED.

PROCEDURES USED : NONE.

REQUIRED CENTRAL MEMORY :

    EXECUTION FIELD LENGTH : 7.

RUNNING TIME :

    WE GIVE A FORMULA FOR THE RUNNING TIME  IN MILLISECONDS ON THE
    CD CYBER 73-28 COMPUTER; THE RELATIVE PRECISION OF THE
    COEFFICIENTS IS AT MOST ONE OR TWO DIGITS:
    .10*MAX(U[0],V[0]) + .06*MIN(U[0],V[0]) + .56.

LANGUAGE : ALGOL 60.

METHOD AND PERFORMANCE : SEE LNG INT POWER (THIS SECTION).

EXAMPLE OF USE : SEE LNG INT POWER (THIS SECTION).


SUBSECTION : LNG INT SUBTRACT.

CALLING SEQUENCE :

    THE HEADING OF THE PROCEDURE READS :
    "PROCEDURE" LNG INT SUBTRACT (U,V,DIFFERENCE);
    "INTEGER" "ARRAY" U,V,DIFFERENCE;
    "CODE" 31201;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    U,V,DIFFERENCE: <ARRAY IDENTIFIER>;
            "INTEGER" "ARRAY" U[0:U[0]],V[0:V[0]],DIFFERENCE[0:U[0]];
            BEFORE THE CALL OF LNG INT SUBTRACT, U AND V MUST
            CONTAIN THE LONG INTEGERS TO BE SUBTRACTED(V FROM U);
            AFTER THE CALL, DIFFERENCE CONTAINS THE MULTI-LENGTH
            DIFFERENCE U-V; IF U<V THEN DIFFERENCE[0]=0
            IS DELIVERED; U AND V REMAIN UNCHANGED.

PROCEDURES USED : NONE.

REQUIRED CENTRAL MEMORY:

    EXECUTION FIELD LENGTH : 7.

RUNNING TIME :

    WE GIVE A FORMULA FOR THE RUNNING TIME  IN MILLISECONDS ON THE
    CD CYBER 73-28 COMPUTER; THE RELATIVE PRECISION OF THE
    COEFFICIENTS IS AT MOST ONE OR TWO DIGITS:
    .10*U[0] + .06*V[0] + .64.

LANGUAGE : ALGOL 60.

METHOD AND PERFORMANCE : SEE LNG INT POWER (THIS SECTION).

EXAMPLE OF USE : SEE LNG INT POWER (THIS SECTION).


SUBSECTION : LNG INT MULT.

CALLING SEQUENCE :

    THE HEADING OF THE PROCEDURE READS:
    "PROCEDURE" LNG INT MULT(U,V,PRODUCT);
    "INTEGER" "ARRAY" U,V,PRODUCT;
    "CODE" 31202;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    U,V,PRODUCT: <ARRAY IDENTIFIER>;
            "INTEGER" "ARRAY" U[0:U[0]], V[0:V[0]],
                              PRODUCT[0:U[0]+V[0]];
            BEFORE THE CALL OF LNG INT MULT, U AND V MUST
            CONTAIN THE LONG INTEGERS TO BE MULTIPLIED;
            AFTER THE CALL, PRODUCT CONTAINS THE MULTI-LENGTH
            PRODUCT OF U AND V, WHILE U AND V REMAIN UNCHANGED.

PROCEDURES USED : NONE.

REQUIRED CENTRAL MEMORY  :

    EXECUTION FIELD LENGTH : 7.

RUNNING TIME :

    WE GIVE A FORMULA FOR THE RUNNING TIME  IN MILLISECONDS ON THE
    CD CYBER 73-28 COMPUTER; THE RELATIVE PRECISION OF THE
    COEFFICIENTS IS AT MOST ONE OR TWO DIGITS:
    .18*U[0]*V[0] + .15*U[0] + .06*V[0] + .46.

LANGUAGE : ALGOL 60.

METHOD AND PERFORMANCE : SEE LNG INT POWER (THIS SECTION).

EXAMPLE OF USE : SEE LNG INT POWER (THIS SECTION).


SUBSECTION : LNG INT DIVIDE.

CALLING SEQUENCE :

    THE HEADING OF THE PROCEDURE READS:
    "PROCEDURE" LNG INT DIVIDE(U,V,QUOTIENT,REMAINDER); "VALUE" U;
    "INTEGER" "ARRAY" U,V,QUOTIENT,REMAINDER;
    "CODE" 31203;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    U,V,QUOTIENT,REMAINDER: <ARRAY IDENTIFIER>;
            "INTEGER" "ARRAY" U[0:U[0]], V[0:V[0]],
            QUOTIENT[0:U[0]-V[0]+1], REMAINDER[0:V[0]];
            BEFORE THE CALL OF LNG INT DIVIDE, U MUST CONTAIN THE
            DIVIDEND, V THE DIVISOR(V ^= 0);
            AFTER THE CALL, THE RESULTS OF THE LONG DIVISION
            OF U BY V (I.E. U//V AND U-U//V) ARE STORED INTO
            QUOTIENT AND REMAINDER; U AND V REMAIN UNCHANGED.

PROCEDURES USED : NONE.

REQUIRED CENTRAL MEMORY :

    11 + U[0] + (IF V[0]=1 OR U[0]<V[0] THEN 0 ELSE V[0]+1),

RUNNING TIME :

    WE GIVE A FORMULA FOR THE RUNNING TIME  IN MILLISECONDS ON THE
    CD CYBER 73-28 COMPUTER; THE RELATIVE PRECISION OF THE
    COEFFICIENTS IS AT MOST ONE OR TWO DIGITS:
    IF V[0]=1 THEN (.34*U[0] + .67) ELSE IF V[1] >= 5 000 000 THEN
                        (.26*DIFF*V[0] + .57*DIFF + .10*V[0] + 1.8)
              ELSE  (.27*DIFF*V[0] + .66*DIFF + .66*V[0] + 2.0)
    (HERE DIFF=U[0]-V[0]+1, I.E. THE NUMBER OF EXECUTIONS
    OF THE STATEMENT, IN WHICH DIVISION OF A (V[0]+1)-PLACE
    NUMBER BY A V[0]-PLACE NUMBER IS PERFORMED).

LANGUAGE : ALGOL 60.

METHOD AND PERFORMANCE : SEE LNG INT POWER (THIS SECTION).

EXAMPLE OF USE : SEE LNG INT POWER (THIS SECTION).


SUBSECTION : LNG INT POWER.

CALLING SEQUENCE :

    THE HEADING OF THE PROCEDURE READS:
    "PROCEDURE" LNG INT POWER(U,EXPONENT,RESULT);
    "VALUE" EXPONENT; "INTEGER" EXPONENT; "INTEGER" "ARRAY" U,RESULT;
    "CODE" 31204;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    EXPONENT: <ARITHMETIC EXPRESSION>;
            THE (POSITIVE) POWER TO WHICH THE LONG INTEGER U
            WILL BE RAISED;
    U,RESULT: <ARRAY IDENTIFIER>;
            "INTEGER" "ARRAY" U[0:U[0]], RESULT[0:U[0]*EXPONENT];
            BEFORE THE CALL OF LNG INT POWER, U MUST CONTAIN
            THE LONG INTEGER WHICH HAS TO BE RAISED TO THE
            POWER EXPONENT;
            AFTER THE CALL, RESULT CONTAINS THE VALUE OF THE
            LONG INTEGER U**EXPONENT; U REMAINS UNCHANGED.

PROCEDURES USED :

    LNG INT MULT = CP31202.

REQUIRED CENTRAL MEMORY :

    EXECUTION FIELD LENGTH : 4 + 3 * (U[0] * EXPONENT + 1).

RUNNING TIME :

    FOR THIS PROCEDURE THE TIME FORMULA IS A COMPLICATED FUNCTION OF
    U[0], EXPONENT AND  THE NUMBER OF ONES IN THE BINARY REPRESENTATION
    OF EXPONENT, BUT ROUGHLY THE TIME IS  OF THE ORDER :
    (U(0)*EXPONENT)**2).
    TWO TESTCASES :
    EXPONENT    TIME(IN SEC.) FOR:
                  U[0]=1     U[0]=2
        20           .04        .10
        40           .13        .34
       100           .68       1.94
       300          5.48      16.6
       500         16.8       51.0

LANGUAGE : ALGOL 60.

METHOD AND PERFORMANCE:

    DEFINITION:
    A LONG INTEGER OF LENGTH N, OR AN N-PLACE INTEGER
    (N>0) IS ANY NONNEGATIVE INTEGER LESS THAN BASE**N,
    AND GREATER THAN OR EQUAL TO BASE**(N-1), WHERE BASE
    IS THE (POSITIVE) RADIX OF THE POSITIONAL NOTATION, IN
    WHICH THE INTEGERS ARE EXPRESSED.

    ALL FIVE PROCEDURES USE THE BASE 10 000 000; THIS IS THE LARGEST
    POWER OF 10, THE SQUARE OF WHICH CAN BE REPRESENTED EXACTLY
    ON THE CD CYBER 73-28 COMPUTER. IF ONE WANTS TO USE THE
    PROCEDURES WITH ANOTHER VALUE OF THE BASE, SAY R (NOT
    NECESSARILY A POWER OF 10), THEN IN THE SOURCE TEXTS OF THE
    PROCEDURES THE NUMBER 10 000 000 HAS TO BE REPLACED BY R
    (8 TIMES IN LNG INT ADD,
     2 TIMES IN LNG INT SUBTRACT,
     2 TIMES IN LNG INT MULT AND
    16 TIMES IN LNG INT DIVIDE).
    MOREOVER, IN LNG INT DIVIDE THE NUMBER 9 999 999 HAS TO BE
    REPLACED BY THE NUMBER R - 1.

    IF A[1], A[2], ..., A[N] ARE THE N "DIGITS" OF THE LONG
    INTEGER M OF LENGTH N (A[1] ^= 0), THEN

    M=((...(A[1]*BASE+A[2])*BASE+...+A[N-2])*BASE+A[N-1])*BASE+A[N].

    ACCORDINGLY, A LONG INTEGER M OF LENGTH N ALWAYS WILL
    BE STORED INTO A CORRESPONDING "INTEGER" "ARRAY" A,
    THE LENGTH N WILL BE STORED INTO THE ARRAY ELEMENT A[0].

    FOR THE METHOD OF THE PROCEDURES LNG INT ADD, LNG INT SUBTRACT,
    LNG INT MULT AND LNG INT DIVIDE, SEE [1; PP.229-248];
    PROCEDURE LNG INT POWER USES THE BINARY METHOD FOR
    EXPONENTIATION (SEE [1; PP.398-401]).

REFERENCES:

    [1]. DONALD E. KNUTH.
         THE ART OF COMPUTER PROGRAMMING, VOLUME 2/
         SEMINUMERICAL ALGORITHMS.
         ADDISON-WESLEY PUBLISHING COMPANY, 1969.

EXAMPLE OF USE:

    "BEGIN"

       "PROCEDURE" OUT(A); "INTEGER" "ARRAY" A;
       "BEGIN" "INTEGER" I,L; L:= A[0];
          OUTPUT(61,"("B6ZD")",A[1]);
          "FOR" I:= 2 "STEP" 1 "UNTIL" L "DO" OUTPUT(61,"("B7D")",
             A[I]); OUTPUT(61,"("/")")
       "END" OUT;
       "INTEGER" "ARRAY" U,V,R1,R2[0:100];

       U[0]:=5; U[1]:=333; U[2]:=U[3]:=U[4]:=U[5]:=7 000 000; OUT(U);
       V[0]:=2; V[1]:=4 444; V[2]:=4 444 444; OUT(V);

       LNG INT ADD(U,V,R1); OUT(R1);
       LNG INT SUBTRACT(U,V,R1); OUT(R1);
       LNG INT MULT(U,V,R1); OUT(R1);
       LNG INT DIVIDE(U,V,R1,R2); OUT(R1); OUT(R2);
       LNG INT POWER(V,5,R1); OUT(R1)
    "END"

    DELIVERS:
        333 7000000 7000000 7000000 7000000
       4444 4444444
        333 7000000 7000000 7004445 1444444
        333 7000000 7000000 6995556 2555556
    1483111 1114073 9114221 9114221 9111110 8000000
     750825 0001650 0826575
        734 0700700
      17341 5299149 6553709 6327185 8964586 9972395 8069589 6628224

SOURCE TEXT(S):

"CODE" 31200;
"CODE" 31201;

"CODE" 31202;
"CODE" 31203;

"CODE" 31204;