Isqrt (integer square root) of X: Difference between revisions
Content added Content deleted
(Isqrt (integer square root) of X in yABASIC) |
(J: include some efficiency and correctness notes) |
||
Line 2,471: | Line 2,471: | ||
=={{header|J}}== |
=={{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. |
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> |
<lang J> |
||
isqrt_float=: <.@:%: |
isqrt_float=: <.@:%: |
||
Line 2,503: | Line 2,503: | ||
</lang> |
</lang> |
||
The first line here shows that the simplest approach (the "floating point square root") is treated specially by J. |
|||
<pre> |
|||
<pre> <.@%: 1000000000000000000000000000000000000000000000000x |
|||
1000000000000000000000000 |
|||
(,. isqrt_float) 7x ^ 20 21x |
(,. isqrt_float) 7x ^ 20 21x |
||
79792266297612001 282475249 |
79792266297612001 282475249 |
||
Line 2,622: | Line 2,626: | ||
1,002,260,051,717,656,279,450,068,093,686 |
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 |
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 |
7,015,820,362,023,593,956,150,476,655,802 |
||
Line 2,636: | Line 2,645: | ||
timespacex 'isqrt 7 ^&x: 1 2 p. i. 37' |
timespacex 'isqrt 7 ^&x: 1 2 p. i. 37' |
||
0.367744 319712 |
0.367744 319712 |
||
</pre> |
|||
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}}== |
=={{header|Java}}== |