(Approximate) integer square root

Quoting Wikipedia article: In number theory, the integer square root (intSqrt) of a positive integer is the positive integer which is the greatest integer less than or equal to the square root of ,

How to compute it in Haskell? The Wikipedia article mentions Newton’s method, but doesn’t discuss how to make the initial guess.

In base-4.8 (GHC-7.10) we got countLeadingZeros function, which can be used to get good initial guess.

Recall that finite machine integers look like

n = 0b0......01.....
      ^^^^^^^^       -- @countLeadingZeros n@ bits
              ^^^^^^ -- @b = finiteBitSize n - countLeadingZeros n@ bits 

We have an efficient way to get ``significant bits” count , which can be used to approximate the number.

It is also easy to approximate the square root of numbers like :

We can use this approximation as the initial guess, and write simple implementation of intSqrt:

module IntSqrt where

import Data.Bits

intSqrt :: Int -> Int
intSqrt 0 = 0
intSqrt 1 = 1
intSqrt n = case compare n 0 of
    LT -> 0           -- whatever :)
    EQ -> 0
    GT -> iter guess  -- only single iteration
  where
    iter :: Int -> Int
    iter 0 = 0
    iter x = shiftR (x + n `div` x) 1 -- shifting is dividing

    guess :: Int
    guess = shiftL 1 (shiftR (finiteBitSize n - countLeadingZeros n) 1)

Note, I do only single iteration¹. Is it enough? My need is to calculate square roots of small numbers. We can test quite a large range exhaustively. Lets define a correctness predicate:

correct :: Int -> Int -> Bool
correct n x = sq x <= n && n < sq (x + 1) where sq y = y * y

Out of hundred numbers

correct100 = length
    [ (n,x) | n <- [ 0..99 ], let x = intSqrt n, correct n x ]

the computed intSqrt is correct for 89! Which are the incorrect ones?

incorrect100 =
    [ (8,3)
    , (24,5)
    , (32,6), (33,6), (34,6), (35,6)
    , (48,7)
    , (80,9)
    , (96,10), (97,10), (98,10), (99,10)
    ]

The numbers which are close to perfect square (, , …) are over estimated.

If we take bigger range, say 0...99999 then with single iteration 23860 numbers are correct, with two iterations 96659.

For my usecase (mangling the size of QuickCheck generators) this is good enough, small deviations are very well acceptable. Bit fiddling FTW!

• 2024-06-24 – hashable arch native
• 2024-05-28 – cabal fields
• 2024-04-21 – A note about coercions
• 2024-04-18 – What makes a good compiler warning?
• 2024-04-12 – Core Inspection

twitter github email linkedin stackoverflow