Isqrt (integer square root) of X: Difference between revisions
Content added Content deleted
(→{{header|Ruby}}: Use refinement instead of global monkey-patching of Integer class) |
Not a robot (talk | contribs) (Add CLU) |
||
Line 859: | Line 859: | ||
73 | 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 | 7,015,820,362,023,593,956,150,476,655,802 |
73 | 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 | 7,015,820,362,023,593,956,150,476,655,802 |
||
</pre> |
</pre> |
||
=={{header|CLU}}== |
|||
<lang clu>% This program uses the 'bigint' cluster from PCLU's 'misc.lib' |
|||
% Integer square root of a bigint |
|||
isqrt = proc (x: bigint) returns (bigint) |
|||
% Initialize a couple of bigints we will reuse |
|||
own zero: bigint := bigint$i2bi(0) |
|||
own one: bigint := bigint$i2bi(1) |
|||
own two: bigint := bigint$i2bi(2) |
|||
own four: bigint := bigint$i2bi(4) |
|||
q: bigint := one |
|||
while q <= x do q := q * four end |
|||
t: bigint |
|||
z: bigint := x |
|||
r: bigint := zero |
|||
while q>one do |
|||
q := q / four |
|||
t := z - r - q |
|||
r := r / two |
|||
if t >= zero then |
|||
z := t |
|||
r := r + q |
|||
end |
|||
end |
|||
return(r) |
|||
end isqrt |
|||
% Format a bigint using commas |
|||
fmt = proc (x: bigint) returns (string) |
|||
own zero: bigint := bigint$i2bi(0) |
|||
own ten: bigint := bigint$i2bi(10) |
|||
if x=zero then return("0") end |
|||
out: array[char] := array[char]$[] |
|||
ds: int := 0 |
|||
while x>zero do |
|||
array[char]$addl(out, char$i2c(bigint$bi2i(x // ten) + 48)) |
|||
x := x / ten |
|||
ds := ds + 1 |
|||
if x~=zero cand ds//3=0 then |
|||
array[char]$addl(out, ',') |
|||
end |
|||
end |
|||
return(string$ac2s(out)) |
|||
end fmt |
|||
start_up = proc () |
|||
po: stream := stream$primary_output() |
|||
% print square roots from 0..65 |
|||
stream$putl(po, "isqrt of 0..65:") |
|||
for i: int in int$from_to(0, 65) do |
|||
stream$puts(po, fmt(isqrt(bigint$i2bi(i))) || " ") |
|||
end |
|||
% print square roots of odd powers |
|||
stream$putl(po, "\n\nisqrt of odd powers of 7:") |
|||
seven: bigint := bigint$i2bi(7) |
|||
for p: int in int$from_to_by(1, 73, 2) do |
|||
stream$puts(po, "isqrt(7^") |
|||
stream$putright(po, int$unparse(p), 2) |
|||
stream$puts(po, ") = ") |
|||
stream$putright(po, fmt(isqrt(seven ** bigint$i2bi(p))), 41) |
|||
stream$putl(po, "") |
|||
end |
|||
end start_up</lang> |
|||
{{out}} |
|||
<pre>isqrt of 0..65: |
|||
0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 |
|||
isqrt of odd powers of 7: |
|||
isqrt(7^ 1) = 2 |
|||
isqrt(7^ 3) = 18 |
|||
isqrt(7^ 5) = 129 |
|||
isqrt(7^ 7) = 907 |
|||
isqrt(7^ 9) = 6,352 |
|||
isqrt(7^11) = 44,467 |
|||
isqrt(7^13) = 311,269 |
|||
isqrt(7^15) = 2,178,889 |
|||
isqrt(7^17) = 15,252,229 |
|||
isqrt(7^19) = 106,765,608 |
|||
isqrt(7^21) = 747,359,260 |
|||
isqrt(7^23) = 5,231,514,822 |
|||
isqrt(7^25) = 36,620,603,758 |
|||
isqrt(7^27) = 256,344,226,312 |
|||
isqrt(7^29) = 1,794,409,584,184 |
|||
isqrt(7^31) = 12,560,867,089,291 |
|||
isqrt(7^33) = 87,926,069,625,040 |
|||
isqrt(7^35) = 615,482,487,375,282 |
|||
isqrt(7^37) = 4,308,377,411,626,977 |
|||
isqrt(7^39) = 30,158,641,881,388,842 |
|||
isqrt(7^41) = 211,110,493,169,721,897 |
|||
isqrt(7^43) = 1,477,773,452,188,053,281 |
|||
isqrt(7^45) = 10,344,414,165,316,372,973 |
|||
isqrt(7^47) = 72,410,899,157,214,610,812 |
|||
isqrt(7^49) = 506,876,294,100,502,275,687 |
|||
isqrt(7^51) = 3,548,134,058,703,515,929,815 |
|||
isqrt(7^53) = 24,836,938,410,924,611,508,707 |
|||
isqrt(7^55) = 173,858,568,876,472,280,560,953 |
|||
isqrt(7^57) = 1,217,009,982,135,305,963,926,677 |
|||
isqrt(7^59) = 8,519,069,874,947,141,747,486,745 |
|||
isqrt(7^61) = 59,633,489,124,629,992,232,407,216 |
|||
isqrt(7^63) = 417,434,423,872,409,945,626,850,517 |
|||
isqrt(7^65) = 2,922,040,967,106,869,619,387,953,625 |
|||
isqrt(7^67) = 20,454,286,769,748,087,335,715,675,381 |
|||
isqrt(7^69) = 143,180,007,388,236,611,350,009,727,669 |
|||
isqrt(7^71) = 1,002,260,051,717,656,279,450,068,093,686 |
|||
isqrt(7^73) = 7,015,820,362,023,593,956,150,476,655,802</pre> |
|||
=={{header|Cowgol}}== |
=={{header|Cowgol}}== |
||
<lang cowgol>include "cowgol.coh"; |
<lang cowgol>include "cowgol.coh"; |