Какой самый быстрый способ решить, является ли число квадратным числом в Python 3

Question

Я пытаюсь вернуть вывод True / False, основываясь на том, являются ли числа в списке квадратными числами или нет.

Список необходимо проверить несколько раз, и список может быть любым положительным целым числом , что означает, что целое число может быть очень большим , фактически слишком большим дляиспользование других решений, включающих функции math.sqrt (), которые вызывают ошибку переполнения, показанную здесь:

userList = [1*10**1000]
print ([x for x in userList if math.sqrt(x).is_integer()])

>>>Traceback (most recent call last):
print ([x for x in userList if math.sqrt(x).is_integer()])
OverflowError: int too large to convert to float

Вот мой * метод:

def squares():
    for i in userList:
        if i in squares: #the list in which all the square numbers are stored
            return True
        else:
            return False

* Моя текущая идея - предварительно подготовить квадратные числа в отдельный список, чтобы сравнить их, но я ищу, возможно, альтернативный более быстрый метод, так как список пользователей может стать очень большим.

Я хочу сохранить возвращенный вывод в отдельном списке следующим образом:

out = []
for i in userList:
    out.append(squares())

print(out)
>>>[False,True...]

Как вы можете видеть, это займет много времени при работе со многими числами, и именно поэтому я и требуюболее быстрый метод.

Answer 1

Простой способ - написать функцию целочисленный квадратный корень .Вот неоптимальный (но все же достаточно быстрый) способ, основанный на бинарном поиске:

def is_sqrt(m,n):
    return m**2 <= n < (m+1)**2

def isqrt(n):
    low = 0
    high = n
    m = (low + high)//2

    while not is_sqrt(m,n):
        if m**2 < n: #too small! must be in [m+1,high]
            low = m+1
        else: #too big! must be in [low, m-1]
            high = m - 1
        m = (low + high) // 2
    return m

def is_square(n):
    return n == (isqrt(n))**2

Тогда почти мгновенно следующее:

>>> is_square(77**200)
True
>>> is_square(77**200 + 1)
False