How to compute square roots without dependency on Float arithmetics?

Learn
1

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?

2

Why without Float? What do you expect?

3

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
4

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
5

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

6

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
7

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
8

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.

9

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)
10

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
11

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