定义：
若一个数能表示成某个自然数的平方的形式，则称这个数为完全平方数。性质：
1. 完全平方数是非负整数。
2. 十进制的完全平方数的末位数只能是0, 1, 4, 5, 6, 9; 十六进制的完全平方数的末位数只能是0, 1, 4, 9。
3. 除0以外的完全平方数是从1开始的连续的奇数的和，例如: 1 = 1, 4 = 1 + 3, 9 = 1 + 3 + 5, 16 = 1 + 3 + 5 + 7。
判断思路：
1. 利用定义，即对输入的非负整数开根，得到浮点数，再四舍五入到整数（即最接近的整数），看该整数的平方是否与输入的非负整数相同。
2. 利用性质3，首先判断输入的非负整数是否为0，再判断是否为从1开始的连续的奇数的和（即依次减去1, 3, 5...，直到出现等于0或小于0的结果，等于0则是完全平方数，小于0则不是）
优化思路：
利用性质2，通过输入的非负整数的末尾数字来过滤不可能是完全平方数的数。在十进制表示下，完全平方数的末位数只能是0, 1, 4, 5, 6, 9，这是比较好理解的（即枚举1到9的平方的末尾数）。同理，在十六进制表示下，我们只需要枚举1到15的平方的末尾数即可，为0，1，4，9，如下所示。
0x0 * 0x0 % 0x10 = 0x0 0x1 * 0x1 % 0x10 = 0x1 0x2 * 0x2 % 0x10 = 0x4 0x3 * 0x3 % 0x10 = 0x9 0x4 * 0x4 % 0x10 = 0x0 0x5 * 0x5 % 0x10 = 0x9 0x6 * 0x6 % 0x10 = 0x4 0x7 * 0x7 % 0x10 = 0x1 0x8 * 0x8 % 0x10 = 0x0 0x9 * 0x9 % 0x10 = 0x1 0xa * 0xa % 0x10 = 0x4 0xb * 0xb % 0x10 = 0x9 0xc * 0xc % 0x10 = 0x0 0xd * 0xd % 0x10 = 0x9 0xe * 0xe % 0x10 = 0x4 0xf * 0xf % 0x10 = 0x1这里有人会问了， 为什么取十六进制表示下的末尾数呢？这里我做如下解释：
1. 我们都知道，计算机以二进制来表示数字，位运算速度是最快的，十六进制表示下的末尾数就是二进制下的末4位数，只需要将输入的非负整数与0xF做按位与（&）运算，就可以得到十六进制下的末尾数。因而，得到十六进制下的末尾数比得到十进制下的末尾数要快。
2. 此外，十进制末尾数的过滤比例为1-(5/10)=1/2；十六进制末尾数的过滤比例则为1-(4/16)=3/4；十六进制比十进制能够过滤掉更多的数。
3. 再多说一句，取2^n进制（比如八进制、六十四进制）都是可以的，n越大，过滤掉的数的比例就越高。
代码：
import math, timeit
import matplotlib.pyplot as plt
import numpy as np
def is_perfect_square_sqrt(n):
root = int(math.sqrt(n) + 0.5)
return root ** 2 == n
# Filter hexadecimal number whose last digit in not in [0, 1, 4, 9]
def hex_filter(n):
digit = n & 0xf
if digit not in [0, 1, 4, 9]:
return False
else:
return True
def show_last_digit():
print 'If a number is a perfect square, \
then the last digit of the number in hexadecimal notation must be 0, 1, 4 or 9.'
for i in range(16):
print "%s * %s %% %s = %s" % (hex(i), hex(i), hex(16), hex((i ** 2) % 16))
# All perfect squares are sums of consecutive odd numbers:
# 1 = 1
# 4 = 1 + 3
# 9 = 1 + 3 + 5
# 16 = 1 + 3 + 5 + 7
def is_perfect_square_sub(n):
i = 1;
while True:
if n < 0:
return False
elif n == 0:
return True
else:
n -= i
i += 2
if __name__ == '__main__':
# Show the possible last digit of the hexadecimal perfect square number
# show_last_digit()
# Check if the results of the four methods are the same
'''
sqrt = []
sqrt_filter = []
sub = []
sub_filter = []
for i in range(100000):
if is_perfect_square_sqrt(i):
sqrt.append(i)
if is_perfect_square_sub(i):
sub.append(i)
if hex_filter(i) and is_perfect_square_sqrt(i):
sqrt_filter.append(i)
if hex_filter(i) and is_perfect_square_sub(i):
sub_filter.append(i)
print sqrt == sqrt_filter
print sub == sub_filter
print sqrt == sub
print sqrt_filter == sub_filter
print sqrt
'''
t = []
t.append(timeit.timeit(stmt="for i in range(100000): is_perfect_square_sqrt(i)",
setup="from __main__ import is_perfect_square_sqrt",
number=1000))
t.append(timeit.timeit(stmt="for i in range(100000): is_perfect_square_sub(i)",
setup="from __main__ import is_perfect_square_sub",
number=1000))
t.append(timeit.timeit(stmt="for i in range(100000): hex_filter(i) and is_perfect_square_sqrt(i)",
setup="from __main__ import is_perfect_square_sqrt, hex_filter",
number=1000))
t.append(timeit.timeit(stmt="for i in range(100000): hex_filter(i) and is_perfect_square_sub(i)",
setup="from __main__ import is_perfect_square_sub, hex_filter",
number=1000))
dic = dict(zip(['sqrt', 'sub', 'sqrt_filter', 'sub_filter'], t))
#print dic
for i, key in enumerate(dic):
plt.bar(i, dic[key]) # i indicates the i-th bar
plt.xticks(np.arange(len(dic)) + 0.4, dic.keys())
plt.yticks(dic.values())
plt.xlabel('Method')
plt.ylabel('Running time')
plt.show()
运行时间比较：
我们通过循环1000次，每次循环判断从0到99999每个数是否为完全平方数，来比较代码中4种算法的性能。运行时间见下图：
由于sqrt_filter和sqrt运行时间较接近，所以y轴的运行时间重叠看不清，分别是33.23355389和41.42628694。
从结果来看，hex_filter优化的时间并没有我想的那么多，可能是因为将hex_filter写作函数，函数调用增加了些额外的时间。