Isqrt (integer square root) of X: Difference between revisions
→{{header|Modula-2}}
Line 3,040:
2651730845859653471779023381601
7015820362023593956150476655802</pre>
=={{header|Mercury}}==
{{trans|Prolog}}
{{works with|Mercury|20.06.1}}
<lang mercury>:- module isqrt_in_mercury.
:- interface.
:- import_module io.
:- pred main(io, io).
:- mode main(di, uo) is det.
:- implementation.
:- import_module char.
:- import_module exception.
:- import_module int.
:- import_module integer. % Integers of arbitrary size.
:- import_module list.
:- import_module string.
:- func four = integer.
four = integer(4).
:- func seven = integer.
seven = integer(7).
%% Find a power of 4 greater than X.
:- func pow4gtx(integer) = integer.
pow4gtx(X) = Q :- pow4gtx_(X, one, Q).
%% The tail recursion for pow4gtx.
:- pred pow4gtx_(integer, integer, integer).
:- mode pow4gtx_(in, in, out) is det.
pow4gtx_(X, A, Q) :- if (X < A) then (Q = A)
else (A1 = A * four,
pow4gtx_(X, A1, Q)).
%% Integer square root function.
:- func isqrt(integer) = integer.
isqrt(X) = Root :- isqrt(X, Root, _).
%% Integer square root and remainder.
:- pred isqrt(integer, integer, integer).
:- mode isqrt(in, out, out) is det.
isqrt(X, Root, Remainder) :-
Q = pow4gtx(X),
isqrt_(X, Q, zero, X, Root, Remainder).
%% The tail recursion for isqrt.
:- pred isqrt_(integer, integer, integer, integer, integer, integer).
:- mode isqrt_(in, in, in, in, out, out) is det.
isqrt_(X, Q, R0, Z0, R, Z) :-
if (X < zero) then throw("isqrt of a negative integer")
else if (Q = one) then (R = R0, Z = Z0)
else (Q1 = Q // four,
T = Z0 - R0 - Q1,
(if (T >= zero)
then (R1 = (R0 // two) + Q1,
isqrt_(X, Q1, R1, T, R, Z))
else (R1 is R0 // two,
isqrt_(X, Q1, R1, Z0, R, Z)))).
%% Insert a character, every three digits, into (what presumably is)
%% an integer numeral. (The name "commas" is not very good.)
:- func commas(string, char) = string.
commas(S, Comma) = T :-
RCL = to_rev_char_list(S),
commas_(RCL, Comma, 0, [], CL),
T = from_char_list(CL).
%% The tail recursion for commas.
:- pred commas_(list(char), char, int, list(char), list(char)).
:- mode commas_(in, in, in, in, out) is det.
commas_([], _, _, L, CL) :- L = CL.
commas_([C | Tail], Comma, I, L, CL) :-
if (I = 3) then commas_([C | Tail], Comma, 0, [Comma | L], CL)
else (I1 = I + 1,
commas_(Tail, Comma, I1, [C | L], CL)).
:- pred roots_m_to_n(integer, integer, io, io).
:- mode roots_m_to_n(in, in, di, uo) is det.
roots_m_to_n(M, N, !IO) :-
if (N < M) then true
else (write_string(to_string(isqrt(M)), !IO),
(if (M \= N) then write_string(" ", !IO)
else true),
M1 = M + one,
roots_m_to_n(M1, N, !IO)).
:- pred roots_of_odd_powers_of_7(integer, integer, io, io).
:- mode roots_of_odd_powers_of_7(in, in, di, uo) is det.
roots_of_odd_powers_of_7(M, N, !IO) :-
if (N < M) then true
else (Pow7 = pow(seven, M),
Isqrt = isqrt(Pow7),
format("%2s %84s %43s",
[s(commas(to_string(M), (','))),
s(commas(to_string(Pow7), (','))),
s(commas(to_string(Isqrt), (',')))],
!IO),
nl(!IO),
M1 = M + two,
roots_of_odd_powers_of_7(M1, N, !IO)).
main(!IO) :-
write_string("isqrt(i) for 0 <= i <= 65:", !IO),
nl(!IO), nl(!IO),
roots_m_to_n(zero, integer(65), !IO),
nl(!IO), nl(!IO), nl(!IO),
write_string("isqrt(7**i) for 1 <= i <= 73, i odd:", !IO),
nl(!IO), nl(!IO),
format("%2s %84s %43s", [s("i"), s("7**i"), s("isqrt(7**i)")], !IO),
nl(!IO),
write_string(duplicate_char(('-'), 131), !IO),
nl(!IO),
roots_of_odd_powers_of_7(one, integer(73), !IO).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Instructions for GNU Emacs--
%%% local variables:
%%% mode: mercury
%%% prolog-indent-width: 2
%%% end:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%</lang>
{{out}}
<pre>$ mmc --warn-non-tail-recursion=self-and-mutual -o isqrt isqrt_in_mercury.m && ./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
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|Modula-2}}==
| |||