I am looking for a function to compute the square root of an integer, without any dependency on functions which use the Float type.

The best candidate I found so far is this:

{-| The greatest integer less than or equal to the square root of n.
-}
squareRoot : Int -> Maybe Int
squareRoot n =
List.range 0 n
|> List.filter (\candidate -> candidate * candidate <= n)
|> List.reverse
|> List.head

I see integrating this method causes long delays in my app, but I have not yet found an implementation which better optimizes for runtime performance.
What functions do you use to compute square roots?

module Newton exposing (sqrt)
sqrt : Int -> Maybe Int
sqrt n =
if n < 0 then
Nothing
else
Just (sqrtHelp n n)
sqrtHelp : Int -> Int -> Int
sqrtHelp n x =
let
nextX =
(x + n // x) // 2
in
if abs (nextX - x) < 1 then
nextX
else if nextX == x + 1 then
x
else
sqrtHelp n nextX

Wow! Thank you very much @dmy for this solution. This fixes the CPU load problem I was seeing. I had thought of implementing a binary search as a next step, but you beat me to it.

Even better than Newtonâ€™s method as posted by @dmy is the following recursive polynomial approximation, which avoids doing the recursive division operations (computationally expensive) in the following code which only uses bit shifts and not divisions:

module Intsqrt exposing (intsqrt)
import Bitwise exposing (shiftLeftBy, shiftRightBy)
intsqrt : Int -> Int
intsqrt n =
intsqrtHelper (rdcrHelper n 0x40000000) n 0
rdcrHelper : Int -> Int -> Int
rdcrHelper n v =
if v > n then
rdcrHelper n (shiftRightBy 2 v)
else
v
intsqrtHelper : Int -> Int -> Int -> Int
intsqrtHelper plc rmndr root =
if plc <= 0 then
root
else if rmndr - root - plc < 0 then
intsqrtHelper (shiftRightBy 2 plc) rmndr (shiftRightBy 1 root)
else
intsqrtHelper (shiftRightBy 2 plc) (rmndr - root - plc) (shiftRightBy 1 root + plc)

You can try it out (with the code actually running in your machine) on this Ellie where by switching between â€śsqrtâ€ť (the Newton method) and â€śintsqrtâ€ť (this code) in the â€śtestâ€ť function, you can compare the times to find this code is about five times faster than the Newton code.

On a side note, (//) in Elm is implemented as (a / b) | 0 in javascript, so it works only if (a / b) fits in a 32 bits integers. truncate is similar.

Bitwise operations have the same limitation, so none of the sqrt implementations above can work on integers larger than 32 bits (actually Newtonâ€™s one fails after 2^32-2 and the recursive polynomial one after 2^32-1).

Thank you, Gordon, I did not see that coming. I can reproduce the difference in computing time here, so I switched my application to your implementation.

Thank you for pointing out this limitation @dmy. I was not aware of it and can see how that might have led to some severe head-scratching when the function returns numbers greater than 0 but wrong. Before reading your post, I assumed that integer operations work up to around 52 bit when using the popular route (standard Elm compiler plus common web browser) to execution.

To avoid bad surprises like this, I updated the implementation to reject such large numbers so that this limitation is easier to see for consumers:

import Bitwise exposing (shiftLeftBy, shiftRightBy)
{-| Returns the greatest integer less than or equal to the square root of n.
This function only supports inputs up to (2 ^ 32 - 2), to reflect limitations with popular methods of executing Elm code, as pointed out by dmy at <https://discourse.elm-lang.org/t/how-to-compute-square-roots-without-dependency-on-float-arithmetics/4324/7?u=viir>
Credits to:
- dmy for his solution at <https://discourse.elm-lang.org/t/how-to-compute-square-roots-without-dependency-on-float-arithmetics/4324/3?u=viir>
- W Gordon Goodsman for his solution at <https://discourse.elm-lang.org/t/how-to-compute-square-roots-without-dependency-on-float-arithmetics/4324/6?u=viir>
-}
squareRoot : Int -> Maybe Int
squareRoot n =
if n < 0 || 0xFFFFFFFF <= n then
Nothing
else
Just (squareRootHelper (squareRootRdcrHelper n 0x40000000) n 0)
squareRootRdcrHelper : Int -> Int -> Int
squareRootRdcrHelper n v =
if v > n then
squareRootRdcrHelper n (shiftRightBy 2 v)
else
v
squareRootHelper : Int -> Int -> Int -> Int
squareRootHelper plc rmndr root =
if plc <= 0 then
root
else if rmndr - root - plc < 0 then
squareRootHelper (shiftRightBy 2 plc) rmndr (shiftRightBy 1 root)
else
squareRootHelper (shiftRightBy 2 plc) (rmndr - root - plc) (shiftRightBy 1 root + plc)

I updated the implementation to reject such large numbersâ€¦

Just a (very) minor quibble in that you rejected one too many large numbers in 0xFFFFFFFF as that one can actually be used in the recursive polynomial algorithm (as noted by @dmy); you should change the following code snippet: