Isqrt (integer square root) of X: Difference between revisions
Use the quadratic residue algorithm
(Use the quadratic residue algorithm) |
|||
Line 6,209:
=={{header|Seed7}}==
Seed7 has integer [https://seed7.sourceforge.net/libraries/integer.htm#sqrt(in_integer) sqrt()] and bigInteger [https://seed7.sourceforge.net/libraries/bigint.htm#sqrt(in_var_bigInteger) sqrt()] functions.
These functions could be used if an integer square root is needed.
But this task does not allow using the language's built-in sqrt() function.
Instead the ''quadratic residue'' algorithm for finding the integer square root must be used.
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i";
include "bigint.s7i";
Line 6,224 ⟶ 6,226:
stri := stri[.. index] & "," & stri[succ(index) ..];
end for;
end func;
const func bigInteger: isqrt (in bigInteger: x) is func
result
var bigInteger: r is 0_;
local
var bigInteger: q is 1_;
var bigInteger: z is 0_;
var bigInteger: t is 0_;
begin
while q <= x do
q *:= 4_;
end while;
z := x;
while q > 1_ do
q := q mdiv 4_;
t := z - r - q;
r := r mdiv 2_;
if t >= 0_ then
z := t;
r +:= q;
end if;
end while;
end func;
Line 6,233 ⟶ 6,258:
writeln("The integer square roots of integers from 0 to 65 are:");
for number range 0 to 65 do
write(
end for;
writeln("\n\nThe integer square roots of powers of 7 from 7**1 up to 7**73 are:");
Line 6,239 ⟶ 6,264:
writeln("----- --------------------------------------------------------------------------------- -----------------------------------------");
for number range 1 to 73 step 2 do
writeln(number lpad 2 <& commatize(pow7) lpad 85 <& commatize(
pow7 *:=
end for;
end func;</syntaxhighlight>
| |||