Isqrt (integer square root) of X: Difference between revisions
→{{header|Swift}}
Line 5,244:
isqrt(7^73): 7,015,820,362,023,593,956,150,476,655,802
</pre>
=={{header|Standard ML}}==
{{trans|Scheme}}
{{trans|OCaml}}
{{works with|MLton}}
<lang sml>(*
The Rosetta Code integer square root task, in Standard ML.
Compile with, for example:
mlton isqrt.sml
*)
val zero = IntInf.fromInt (0)
val one = IntInf.fromInt (1)
val seven = IntInf.fromInt (7)
val word1 = Word.fromInt (1)
val word2 = Word.fromInt (2)
fun
find_a_power_of_4_greater_than_x (x) =
let
fun
loop (q) =
if x < q then
q
else
loop (IntInf.<< (q, word2))
in
loop (one)
end;
fun
isqrt (x) =
let
fun
loop (q, z, r) =
if q = one then
r
else
let
val q = IntInf.~>> (q, word2)
val t = z - r - q
val r = IntInf.~>> (r, word1)
in
if t < zero then
loop (q, z, r)
else
loop (q, t, r + q)
end
in
loop (find_a_power_of_4_greater_than_x (x), x, zero)
end;
fun
insert_separators (s, sep) =
(* Insert separator characters (such as #",", #".", #" ") in a numeral
that is already in string form. *)
let
fun
loop (revchars, i, newchars) =
case (revchars, i) of
([], _) => newchars
| (revchars, 3) => loop (revchars, 0, sep :: newchars)
| (c :: tail, i) => loop (tail, i + 1, c :: newchars)
in
implode (loop (rev (explode s), 0, []))
end;
fun
commas (s) =
(* Insert commas in a numeral that is already in string form. *)
insert_separators (s, #",");
val pad_with_spaces = StringCvt.padLeft #" "
fun
main () =
let
val i = ref 0
in
print ("isqrt(i) for 0 <= i <= 65:\n\n");
i := 0;
while !i < 65 do (
print (IntInf.toString (isqrt (IntInf.fromInt (!i))));
print (" ");
i := !i + 1
);
print (IntInf.toString (isqrt (IntInf.fromInt (65))));
print ("\n\n\n");
print ("isqrt(7**i) for 1 <= i <= 73, i odd:\n\n");
print (pad_with_spaces 2 "i");
print (pad_with_spaces 85 "7**i");
print (pad_with_spaces 44 "sqrt(7**i)");
print ("\n");
i := 1;
while !i <= 131 do (
print ("-");
i := !i + 1
);
print ("\n");
i := 1;
while !i <= 73 do (
let
val pow7 = IntInf.pow (seven, !i)
val root = isqrt (pow7)
in
print (pad_with_spaces 2 (Int.toString (!i)));
print (pad_with_spaces 85 (commas (IntInf.toString pow7)));
print (pad_with_spaces 44 (commas (IntInf.toString root)));
print ("\n");
i := !i + 2
end
)
end;
main ();
(* local variables: *)
(* mode: sml *)
(* sml-indent-level: 2 *)
(* sml-indent-args: 2 *)
(* end: *)</lang>
{{out}}
<pre>$ mlton isqrt.sml && ./isqrt
isqrt(i) for 0 <= i <= 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(7**i) for 1 <= i <= 73, i odd:
i 7**i sqrt(7**i)
-----------------------------------------------------------------------------------------------------------------------------------
1 7 2
3 343 18
5 16,807 129
7 823,543 907
9 40,353,607 6,352
11 1,977,326,743 44,467
13 96,889,010,407 311,269
15 4,747,561,509,943 2,178,889
17 232,630,513,987,207 15,252,229
19 11,398,895,185,373,143 106,765,608
21 558,545,864,083,284,007 747,359,260
23 27,368,747,340,080,916,343 5,231,514,822
25 1,341,068,619,663,964,900,807 36,620,603,758
27 65,712,362,363,534,280,139,543 256,344,226,312
29 3,219,905,755,813,179,726,837,607 1,794,409,584,184
31 157,775,382,034,845,806,615,042,743 12,560,867,089,291
33 7,730,993,719,707,444,524,137,094,407 87,926,069,625,040
35 378,818,692,265,664,781,682,717,625,943 615,482,487,375,282
37 18,562,115,921,017,574,302,453,163,671,207 4,308,377,411,626,977
39 909,543,680,129,861,140,820,205,019,889,143 30,158,641,881,388,842
41 44,567,640,326,363,195,900,190,045,974,568,007 211,110,493,169,721,897
43 2,183,814,375,991,796,599,109,312,252,753,832,343 1,477,773,452,188,053,281
45 107,006,904,423,598,033,356,356,300,384,937,784,807 10,344,414,165,316,372,973
47 5,243,338,316,756,303,634,461,458,718,861,951,455,543 72,410,899,157,214,610,812
49 256,923,577,521,058,878,088,611,477,224,235,621,321,607 506,876,294,100,502,275,687
51 12,589,255,298,531,885,026,341,962,383,987,545,444,758,743 3,548,134,058,703,515,929,815
53 616,873,509,628,062,366,290,756,156,815,389,726,793,178,407 24,836,938,410,924,611,508,707
55 30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943 173,858,568,876,472,280,560,953
57 1,481,113,296,616,977,741,464,105,532,513,750,734,030,421,355,207 1,217,009,982,135,305,963,926,677
59 72,574,551,534,231,909,331,741,171,093,173,785,967,490,646,405,143 8,519,069,874,947,141,747,486,745
61 3,556,153,025,177,363,557,255,317,383,565,515,512,407,041,673,852,007 59,633,489,124,629,992,232,407,216
63 174,251,498,233,690,814,305,510,551,794,710,260,107,945,042,018,748,343 417,434,423,872,409,945,626,850,517
65 8,538,323,413,450,849,900,970,017,037,940,802,745,289,307,058,918,668,807 2,922,040,967,106,869,619,387,953,625
67 418,377,847,259,091,645,147,530,834,859,099,334,519,176,045,887,014,771,543 20,454,286,769,748,087,335,715,675,381
69 20,500,514,515,695,490,612,229,010,908,095,867,391,439,626,248,463,723,805,607 143,180,007,388,236,611,350,009,727,669
71 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 1,002,260,051,717,656,279,450,068,093,686
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>
=={{header|Swift}}==
Line 5,355 ⟶ 5,536:
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>
=={{Header|Tiny BASIC}}==
Tiny BASIC does not support string formatting or concatenation, and is limited to integer arithmetic on numbers no greater than 32,767. The isqrt of 0-65 and the first two odd powers of 7 are shown in column format. The algorithm itself (the interesting part) begins on line 100.
| |||