Isqrt (integer square root) of X: Difference between revisions
J: include some efficiency and correctness notes
(Isqrt (integer square root) of X in yABASIC) |
(J: include some efficiency and correctness notes) |
||
Line 2,471:
=={{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. Note that the "floating point method" is exact when arbitrary precision integers or rational numbers are used.
<lang J>
isqrt_float=: <.@:%:
Line 2,503:
</lang>
The first line here shows that the simplest approach (the "floating point square root") is treated specially by J.
<pre> <.@%: 1000000000000000000000000000000000000000000000000x
1000000000000000000000000
(,. isqrt_float) 7x ^ 20 21x
79792266297612001 282475249
Line 2,622 ⟶ 2,626:
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. isqrt_float is exact for large integers
align comma (,.isqrt_float),7^73x
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
Line 2,636 ⟶ 2,645:
timespacex 'isqrt 7 ^&x: 1 2 p. i. 37'
0.367744 319712
NB. but not as fast as isqrt_float, nor as space efficient
timespacex 'isqrt_float 7 ^&x: 1 2 p. i. 37'
0.0005145 152192</pre>
=={{header|Java}}==
| |||