Isqrt (integer square root) of X: Difference between revisions
→{{header|Ol}}
Line 3,611:
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|OCaml}}==
{{trans|Scheme}}
{{libheader|Zarith}}
<lang OCaml>(* The Rosetta Code integer square root task, in OCaml, using Zarith
for large integers.
Compile with, for example:
ocamlfind ocamlc -package zarith -linkpkg -o isqrt isqrt.ml
Translated from the Scheme. *)
let find_a_power_of_4_greater_than_x x =
let open Z in
let rec loop q =
if x < q then q else loop (q lsl 2)
in
loop one
let isqrt x =
let open Z in
let rec loop q z r =
if q = one then
r
else
let q = q asr 2 in
let t = z - r - q in
let r = r asr 1 in
if t < zero then
loop q z r
else
loop q t (r + q)
in
let q0 = find_a_power_of_4_greater_than_x x in
let z0 = x in
let r0 = zero in
loop q0 z0 r0
let insert_separators s sep =
let rec loop revchars i newchars =
match revchars with
| [] -> newchars
| revchars when i = 3 -> loop revchars 0 (sep :: newchars)
| c :: tail -> loop tail (i + 1) (c :: newchars)
in
let revchars = List.rev (List.of_seq (String.to_seq s)) in
String.of_seq (List.to_seq (loop revchars 0 []))
let commas s = insert_separators s ','
let main () =
Printf.printf "isqrt(i) for 0 <= i <= 65:\n\n";
for i = 0 to 64 do
Printf.printf "%s " Z.(to_string (isqrt (of_int i)))
done;
Printf.printf "%s\n" Z.(to_string (isqrt (of_int 65)));
Printf.printf "\n\n";
Printf.printf "isqrt(7**i) for 1 <= i <= 73, i odd:\n\n";
Printf.printf "%2s %84s %43s\n" "i" "7**i" "isqrt(7**i)";
for i = 1 to 131 do Printf.printf "-" done;
Printf.printf "\n";
for j = 0 to 36 do
let i = j + j + 1 in
let power = Z.(of_int 7 ** i) in
let root = isqrt power in
Printf.printf "%2d %84s %43s\n"
i (commas (Z.to_string power)) (commas (Z.to_string root))
done
;;
main ()</lang>
{{out}}
<pre>$ ocamlfind ocamlc -package zarith -linkpkg -o isqrt isqrt.ml && ./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 isqrt(7**i)
-----------------------------------------------------------------------------------------------------------------------------------
1 7 2
| |||