快速判断一个非负整数是否为完全平方数

时间:2022-12-29 05:11:14

定义:

若一个数能表示成某个自然数的平方的形式,则称这个数为完全平方数。

性质:
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写作函数,函数调用增加了些额外的时间。