2022/06/18

Leetcode Note: Go - Valid Perfect Square

Valid Perfect Square - LeetCode
https://leetcode.com/problems/valid-perfect-square/

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

所感

  • 与えられた int 数値が perfect square であれば true を return する
    • perfect square は完全平方のこと
    • 他の整数の平方（二乗）になっている整数
      • 例: 1 (1^2), 4 (2^2), 9 (3^2), 16 (4^2), 25 (5^2), …
  • 標準ライブラリの sqrt 的なものは使わずに実装する

回答

[GO] Newton’s Method Solution - LeetCode Discuss
https://leetcode.com/problems/valid-perfect-square/discuss/559495/GO-Newton's-Method-Solution

func isPerfectSquare(num int) bool {
	if num < 2 {
		return true
	}

	x := num / 2
	for x*x > num {
		x = (x + num/x) / 2
	}

	return x*x == num
}
  • newton’s method という解法で完全平方を求める実装
  • x に num / 2 を初期値としてセット
  • x * x が num 以上の間ループ
    • x に (x + num/x) / 2 を代入
      • よくわからないので具体的な数値をシミュレーションして考えてみる
    • case num == 6:
      • x := 6 / 2
      • 3 * 3 > 6 == true なのでループ処理突入
        • x = (3 + 6 / 3) / 2 なので 3 / 2 で 1 が代入される
      • 1 * 1 > 6 == false なのでループ脱出
      • 1 * 1 == 6 は false なので完全平方では無い
    • case num == 16:
      • x := 16 / 2
      • 8 * 8 > 16 == false なのでループ入らず
      • 8 * 8 == 16 は true なので完全平方
    • シミュレーションしても良くわらないが成立している
      • 数学力よ・・・
  • x*x == num が成立するなら完全平方

標準ライブラリの Sqrt 調査

https://github.com/golang/go/blob/go1.18.3/src/math/sqrt.go

// Sqrt returns the square root of x.
//
// Special cases are:
//	Sqrt(+Inf) = +Inf
//	Sqrt(±0) = ±0
//	Sqrt(x < 0) = NaN
//	Sqrt(NaN) = NaN
func Sqrt(x float64) float64 {
	if haveArchSqrt {
		return archSqrt(x)
	}
	return sqrt(x)
}

// Note: Sqrt is implemented in assembly on some systems.
// Others have assembly stubs that jump to func sqrt below.
// On systems where Sqrt is a single instruction, the compiler
// may turn a direct call into a direct use of that instruction instead.

func sqrt(x float64) float64 {
	// special cases
	switch {
	case x == 0 || IsNaN(x) || IsInf(x, 1):
		return x
	case x < 0:
		return NaN()
	}
	ix := Float64bits(x)
	// normalize x
	exp := int((ix >> shift) & mask)
	if exp == 0 { // subnormal x
		for ix&(1<<shift) == 0 {
			ix <<= 1
			exp--
		}
		exp++
	}
	exp -= bias // unbias exponent
	ix &^= mask << shift
	ix |= 1 << shift
	if exp&1 == 1 { // odd exp, double x to make it even
		ix <<= 1
	}
	exp >>= 1 // exp = exp/2, exponent of square root
	// generate sqrt(x) bit by bit
	ix <<= 1
	var q, s uint64               // q = sqrt(x)
	r := uint64(1 << (shift + 1)) // r = moving bit from MSB to LSB
	for r != 0 {
		t := s + r
		if t <= ix {
			s = t + r
			ix -= t
			q += r
		}
		ix <<= 1
		r >>= 1
	}
	// final rounding
	if ix != 0 { // remainder, result not exact
		q += q & 1 // round according to extra bit
	}
	ix = q>>1 + uint64(exp-1+bias)<<shift // significand + biased exponent
	return Float64frombits(ix)
}

システム毎にアセンブリで実装しているらしい？

See Also