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.

</lang>

But for those whom only the quadratic residue algorithm will do, just substitute this form of the ISQRT() function. (The output is identical.)

<lang algol>

% RETURN INTEGER SQUARE ROOT OF N USING QUADRATIC RESIDUE ALGORITHM %

INTEGER FUNCTION ISQRT(X);

INTEGER X;

BEGIN

INTEGER Q, R, Z, T;

Q := 1;

WHILE Q <= X DO

Q := Q * 4;

Z := X;

R := 0;

WHILE Q > 1 DO

BEGIN

Q := Q / 4;

T := Z - R - Q;

R := R / 2;

IF T >= 0 THEN

BEGIN

Z := T;

R := R + Q;

END;

END;

ISQRT := R;

END;