How to compute square roots without dependency on Float arithmetics?

Learn
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