This tests a random 100000-bits number in 4 seconds on my PC. And a one-million-bits number in about 400 seconds.

```
def isPerfectSquare(self, num):
x = xSquared = 0
for i in range(num.bit_length() >> 1, -1, -1):
tmp = xSquared + (x << (i+1)) + (1 << i+i)
if tmp <= num:
xSquared = tmp
x += 1 << i
return xSquared == num
```

Note that **(x + 2 ^{i})^{2} = x^{2} + 2^{i+1}x + 2^{2i}**. So if I keep track of both x and x

^{2}, I can compute x + 2

^{i}as well as its square with just addition and shifts. This is good for really big numbers, where multiplication can't be seen as an O(1) time operation anymore but takes O(log(m)

*****log(n)) for multiplying numbers m and n, while adding them only takes O(log(m)

**+**log(n)) and shifts are fast, too.

I start with x=0 and then test adding decreasing powers of 2. For example with num=100, I try adding 8, 4, 2 and 1 to x. I leave out 4 and 1, as adding them would make x^{2} too large. So I end up with x=8+2=10 and xSquared=100.