Isqrt (integer square root) of X: Difference between revisions
Content added Content deleted
(Use the quadratic residue algorithm) |
|||
Line 6,209: | Line 6,209: | ||
=={{header|Seed7}}== |
=={{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. |
|||
{{incorrect|Seed7|<br><br>This Rosetta Code task is to use a ''quadratic residue'' algorithm for finding the integer square root.<br><br>The pseudo-code is shown in the task's preamble which does ''not'' use the language's built-in sqrt() function.<br><br>Please use the required pseudo-code as shown in the task's preamble.<br><br>}} |
|||
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"; |
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i"; |
||
include "bigint.s7i"; |
include "bigint.s7i"; |
||
Line 6,224: | Line 6,226: | ||
stri := stri[.. index] & "," & stri[succ(index) ..]; |
stri := stri[.. index] & "," & stri[succ(index) ..]; |
||
end for; |
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; |
end func; |
||
Line 6,233: | Line 6,258: | ||
writeln("The integer square roots of integers from 0 to 65 are:"); |
writeln("The integer square roots of integers from 0 to 65 are:"); |
||
for number range 0 to 65 do |
for number range 0 to 65 do |
||
write( |
write(isqrt(bigInteger(number)) <& " "); |
||
end for; |
end for; |
||
writeln("\n\nThe integer square roots of powers of 7 from 7**1 up to 7**73 are:"); |
writeln("\n\nThe integer square roots of powers of 7 from 7**1 up to 7**73 are:"); |
||
Line 6,239: | Line 6,264: | ||
writeln("----- --------------------------------------------------------------------------------- -----------------------------------------"); |
writeln("----- --------------------------------------------------------------------------------- -----------------------------------------"); |
||
for number range 1 to 73 step 2 do |
for number range 1 to 73 step 2 do |
||
writeln(number lpad 2 <& commatize(pow7) lpad 85 <& commatize( |
writeln(number lpad 2 <& commatize(pow7) lpad 85 <& commatize(isqrt(pow7)) lpad 42); |
||
pow7 := |
pow7 *:= 49_; |
||
end for; |
end for; |
||
end func;</syntaxhighlight> |
end func;</syntaxhighlight> |