Leetcode Note: Go - Sqrt(x)

Sqrt(x) - LeetCode
https://leetcode.com/problems/sqrtx/

• Go 言語で取り組んだメモ

所感

• math ライブラリでなんとかなるのでは？

実装準備

func mySqrt(x int) int {
    return 0
}

func main() { 
    x := 4
    fmt.Println(mySqrt(x))
}

回答

func mySqrt(x int) int {
    return int(math.Sqrt(float64(x)))
}

• https://pkg.go.dev/math#Sqrt
  • https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/math/sqrt.go;l=104
• math.Sqrt は float64 を引き受けて float64 を return するので、それぞれを int にキャストしちゃえば良さそう
  • しかし、こんな簡単に通るか？ => 通っちゃった・・・
• いくつか upvote されている Discuss を見てみる
  • https://leetcode.com/problems/sqrtx/discuss/294674/Golang-O(1)-solution-using-Newtons-method-beats-100-percent-runtime
  • https://leetcode.com/problems/sqrtx/discuss/292190/Go-0-ms-double-100.00-(Binary-Search)
  • 当たり前だが math を使わず自前で実装
• まっとうにアプローチするなら、まず平方根の求め方をちゃんと調べて、それから実装に手を付けるべき
  • https://ja.wikipedia.org/wiki/%E5%B9%B3%E6%96%B9%E6%A0%B9
  • 開平法, extraction of square root というアルゴリズムが使われるのが一般的なようだ
    • https://ja.wikipedia.org/wiki/%E9%96%8B%E5%B9%B3%E6%B3%95
    • うーん数学筋が足りない・・・