F # Square Root on Int

Question

정수 값의 제곱근을 수행해야하는 F # 프로그램을 작성 중입니다. 캐스트를 사용하지 않고이 작업을 수행 할 수있는 기능이 검색되지 않았습니다. int -> float.

불필요한 캐스트없이 정수의 제곱근을 만들 수있는 함수가 있습니까?

Answer 1

당신은 길을 가야하는 것입니다 후 부동 소수점에 INT 변환하는 float 기능을 사용하여 다음 sqrt를 호출, 부동 소수점으로의 제곱근을 정수를 취하고 반환하는 함수하려면 다음

을

sqrt (float n) 

원칙적으로 F #은이 변환을 내재적으로 허용 할 수 있지만 정수의 제곱근이 (주석에 설명 된대로) 어떤 것이어야하는지 분명하지 않기 때문에이를 수행하지 않는다고 생각합니다. C#에서는 Math.Sqrt(n)으로 작성할 수 있지만, C#에서는 int에서 float으로 암시 적 변환을 허용하므로이 방법이 효과적입니다.

정수가 정수를 반환하는 경우 제곱근을 원한다면 주석의 설명처럼 표준 방법이 없으므로 필요한 기능을 구현할 수 있습니다.

Answer 2

입력이 int 인 이유를 이해하는 데 어려움이 있지만 중요한 경우 & 정복 알고리즘을 사용할 수 있습니다. 하드웨어 플로트가있는 CPU 아키텍처에서는 sqrt (float n)보다 훨씬 느립니다.

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