# How to compute square roots without dependency on Float arithmetics?

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
``````

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?

Why without Float? What do you expect?

You could use Newton’s method using only integer division:

``````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
``````
5 Likes

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.

2 Likes

By avoiding floating point operations for this function, I expect to:

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.

7 Likes

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`).

1 Like

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:

``````    if n < 0 || 0xFFFFFFFF <= n then
``````

to the following:

``````    if n < 0 || 0xFFFFFFFF < n then
``````

to allow the use of this number.

1 Like

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.