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;