Isqrt (integer square root) of X: Difference between revisions

=={{header|J}}==

Three implementations given. The floating point method is best for small square roots, Newton's method is fastest for extended integers. isqrt adapted from the page preamble.

<lang J>

isqrt_float=: <.@:%:

isqrt_newton=: 9&$: :(x:@:<.@:-:@:(] + x:@:<.@:%)^:_&>~&:x:)

align=: (|.~ i.&' ')"1

comma=: (' ' -.~ [: }: [: , [: (|.) _3 (',' ,~ |.)\ |.)@":&>

While=: {{ u^:(0-.@:-:v)^:_ }}

isqrt=: 3 :0&>

y =. x: y

NB. q is a power of 4 that's greater than y. Append 0 0 under binary representation

q =. y (,&0 0x&.:#:@:])While>: 1x

z =. y NB. set z to the value of y.

r =. 0x NB. initialize r to zero.

while. 1 < q do. NB. perform while q > unity.

q =. _2&}.&.:#: q NB. integer divide by 4 (-2 drop under binary representation)

t =. (z - r) - q NB. compute value of t.

r =. }:&.:#: r NB. integer divide by two. (curtail under binary representation)

if. 0 <: t do.

z =. t NB. set z to value of t

r =. r + q NB. compute new value of r

end.

end.

NB. r is now the isqrt(y). (most recent value computed)

NB. Sidenote: Also, Z is now the remainder after square root

NB. ie. r^2 + z = y, so if z = 0 then x is a perfect square

NB. r , z

)

</lang>

<pre>

(,. isqrt_float) 7x ^ 20 21x

79792266297612001 282475249

558545864083284007 747359260

(,. isqrt_newton) 7x ^ 20 21x

79792266297612001 282475249

558545864083284007 747359260

align comma (,. isqrt) 7 ^&x: 1 2 p. i. 37

7

2

343

18

16,807

129

823,543

907

40,353,607

6,352

1,977,326,743

44,467

96,889,010,407

311,269

4,747,561,509,943

2,178,889

232,630,513,987,207

15,252,229

11,398,895,185,373,143

106,765,608

558,545,864,083,284,007

747,359,260

27,368,747,340,080,916,343

5,231,514,822

1,341,068,619,663,964,900,807

36,620,603,758

65,712,362,363,534,280,139,543

256,344,226,312

3,219,905,755,813,179,726,837,607

1,794,409,584,184

157,775,382,034,845,806,615,042,743

12,560,867,089,291

7,730,993,719,707,444,524,137,094,407

87,926,069,625,040

378,818,692,265,664,781,682,717,625,943

615,482,487,375,282

18,562,115,921,017,574,302,453,163,671,207

4,308,377,411,626,977

909,543,680,129,861,140,820,205,019,889,143

30,158,641,881,388,842

44,567,640,326,363,195,900,190,045,974,568,007

211,110,493,169,721,897

2,183,814,375,991,796,599,109,312,252,753,832,343

1,477,773,452,188,053,281

107,006,904,423,598,033,356,356,300,384,937,784,807

10,344,414,165,316,372,973

5,243,338,316,756,303,634,461,458,718,861,951,455,543

72,410,899,157,214,610,812

256,923,577,521,058,878,088,611,477,224,235,621,321,607

506,876,294,100,502,275,687

12,589,255,298,531,885,026,341,962,383,987,545,444,758,743

3,548,134,058,703,515,929,815

616,873,509,628,062,366,290,756,156,815,389,726,793,178,407

24,836,938,410,924,611,508,707

30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943

173,858,568,876,472,280,560,953

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

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

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

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

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

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

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

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

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

NB. Newton's method result matches isqrt

(isqrt_newton -: isqrt)7 ^&x: 1 2 p. i. 37

1

NB. An order of magnitude faster and one tenth the space, in j

timespacex 'isqrt_newton 7 ^&x: 1 2 p. i. 37'

0.038085 39552

timespacex 'isqrt 7 ^&x: 1 2 p. i. 37'

0.367744 319712

</pre>