Isqrt (integer square root) of X: Difference between revisions

The approach here, while not the quadratic residue algorithm, works just fine. The output has been put into columnar form to avoid what would otherwise be an ugly mess on a typical 80 column display.

% RETURN INTEGER SQUARE ROOT OF N %

INTEGER FUNCTION ISQRT(N);

INTEGER N;

INTEGER R1, R2;

R1 := N;

R2 := 1;

WHILE R1 > R2 DO

R1 := (R1+R2) / 2;

R2 := N / R1;

ISQRT := R1;

But for those for whom only the quadratic residue algorithm will do, just substitute this for the ISQRT() function in the previous example. (The output is identical.) But be warned: there is a bug lurking in the algorithm as presented in the task description. The statement q := q * 4 in the first while loop will overflow the limits of ALGOL-M's integer data type (-16,383 to +16,383) for any value of x greater than 4095 and trigger an endless loop.

COMMENT

RETURN INTEGER SQUARE ROOT OF N USING QUADRATIC RESIDUE

ALGORITHM. WARNING: THE FUNCTION WILL FAIL FOR X GREATER

THAN 4095;

INTEGER FUNCTION ISQRT(X);

INTEGER X;

INTEGER Q, R, Z, T;

Q := 1;

WHILE Q <= X DO

Q := Q * 4; % WARNING! OVERFLOW YIELDS 0 %

Z := X;

R := 0;

WHILE Q > 1 DO

Q := Q / 4;

T := Z - R - Q;

R := R / 2;

IF T >= 0 THEN

BEGIN

Z := T;

R := R + Q;

END;

ISQRT := R;

</syntaxhighlight>