-
Notifications
You must be signed in to change notification settings - Fork 1
/
sqrt.go
58 lines (51 loc) · 810 Bytes
/
sqrt.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package imath
func Sqrt2(n int) int {
// set the highest bit
c := 1 << 31
g := 1 << 31
for {
if g*g > n {
g ^= c
}
c >>= 1
if c == 0 {
return g
}
g |= c
}
}
func Sqrt(x int) (root int) {
op := x
root = 0
// "one" starts at the highest power of four <= than the argument.
one := 1 << 30 // second-to-top bit set
for one > op {
one >>= 2
}
for one != 0 {
if op >= root+one {
op -= root + one
root += one << 1 // 2 * one
}
root >>= 1
one >>= 2
}
return
}
func Sqrt3(n int) (root int) {
remainder := n
place := 0x40000000
root = 0
for place > remainder {
place = place >> 2
}
for place != 0 {
if remainder >= root+place {
remainder = remainder - root - place
root = root + (place << 1)
}
root = root >> 1
place = place >> 2
}
return
}