CODEWITHSUNDEEP
typesf#floating-pointintsqrt
eisterman
eisterman

Reputation: 554

F# Square Root on Int

I'm building a program in F# in which i need to do the Square Root of a Integer value. I've searched and found none function which allows to doing that without the use of a cast int -> float.

Is there a function that allows to make the square root of an integer without an unnecessary cast?

Upvotes: 2

Views: 2688

Answers (2)

Just another metaprogrammer
Just another metaprogrammer

Reputation: 11577

I have a hard time understanding why the limitation to int input but if that is important one could employ a divide & conquer algorithm. This is a lot slower than sqrt (float n) on any CPU architecture with hardware floats.

let isqrt n =
  let rec loop b e =
    let i = (b + e) >>> 1
    let i2 = i*i
    if i2 = n then
      i
    else
      let nb, ne =
        if i2 > n then
          b, i
        else
          i, e
      if nb = b && ne = e then
        // Check i - 1 and i + 1 to see if either is a better fit than i
        let imin  = i - 1
        let imax  = i + 1
        let i2min = imin*imin
        let i2max = imax*imax
        let d     = n - i2    |> abs
        let dmin  = n - i2min |> abs
        let dmax  = n - i2max |> abs
        if d < dmin && d < dmax then
          i
        elif dmin < dmax then
          imin
        else
          imax

      else
        loop nb ne
  loop 1 n

open FsCheck

let isqrtProperty n =
  n > 1 ==> fun () ->
    let r     = isqrt n
    let rmin  = r - 1
    let rmax  = r + 1

    let r2    = r*r
    let rmin2 = rmin*rmin
    let rmax2 = rmax*rmax

    let d     = n - r2     |> abs
    let dmin  = n - rmin2  |> abs
    let dmax  = n - rmax2  |> abs

    r >= 0 && d <= dmin && d <= dmax

[<EntryPoint>]
let main argv =
  let config = { Config.Quick with MaxTest = 10000; MaxFail = 100000 }
  Check.One ("isqrt property", config, isqrtProperty)
  0

Upvotes: 0

Tomas Petricek
Tomas Petricek

Reputation: 243106

If you just want a function that takes an integer and returns its square root as a floating point, then using a float function to convert the int to a floating point and then calling sqrt is the way to go:

sqrt (float n)

In principle, F# could allow this conversion implicitly, but I think it does not do it because it because it is not clear what square root of an integer should be (as discussed in the comments). In C#, you can write Math.Sqrt(n), but this works because C# allows implicit conversion from int to float anywhere in your program.

If you want a square root if integers that returns integers, then there is no standard way of doing that (as discussed in the comments), so it's up to you to implement the functionality you need.

Upvotes: 5

Related Questions