Проверьте, является ли число идеальным квадратом

Question

Как я мог бы проверить, является ли число идеальным квадратом?

Скорость пока не имеет значения, просто работаю.

Answer 1

Проблема с опорой на любое вычисление с плавающей запятой (math.sqrt(x), или x**0.5) заключается в том, что вы не можете быть действительно уверены, что это точно (для достаточно больших целых чисел x, этого не будет, и может даже переполниться).К счастью (если кто-то не спешит;-) существует множество чисто целочисленных подходов, таких как следующий...:

def is_square(apositiveint):
  x = apositiveint // 2
  seen = set([x])
  while x * x != apositiveint:
    x = (x + (apositiveint // x)) // 2
    if x in seen: return False
    seen.add(x)
  return True

for i in range(110, 130):
   print i, is_square(i)

Подсказка:он основан на "вавилонском алгоритме" для получения квадратного корня, см. википедия.IT делает работайте с любым положительным числом, для которого у вас достаточно памяти для завершения вычислений;-).

Редактировать:давайте посмотрим на пример...

x = 12345678987654321234567 ** 2

for i in range(x, x+2):
   print i, is_square(i)

это печатает по желанию (и в разумные сроки тоже;-):

152415789666209426002111556165263283035677489 True
152415789666209426002111556165263283035677490 False

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

А затем попробуйте с x**7 и найдите умный способ обойти проблему, которую вы получите,

OverflowError: long int too large to convert to float

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

Если я был в спешке, конечно, я бы использовал неуклюжий -- но тогда, я явно предвзят;-).

>>> import gmpy
>>> gmpy.is_square(x**7)
1
>>> gmpy.is_square(x**7 + 1)
0

Да, я знаю, это так просто, что кажется мошенничеством (примерно так же я отношусь к Python в целом;-) - совсем никакого уменья, просто идеальная прямота и простота (и, в случае gmpy, абсолютная скорость;-)...

Answer 2

Используйте метод Ньютона, чтобы быстро обнулить ближайший целочисленный квадратный корень, затем возведите его в квадрат и посмотрите, ваше ли это число.Видишь isqrt ( искрт ).

Python ≥ 3.8 имеет math.isqrt.Если вы используете более старую версию Python, поищите "def isqrt(n)" реализация здесь.

import math

def is_square(i: int) -> bool:
    return i == math.isqrt(i) ** 2

Answer 3

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

import math

def is_square(integer):
    root = math.sqrt(integer)
    return integer == int(root + 0.5) ** 2

Представьте себе integer является 9. math.sqrt(9) могло бы быть 3.0, но это также может быть что - то вроде 2.99999 или 3.00001, так что возведение результата в квадрат сразу ненадежно.Зная , что int принимает значение floor, увеличивая значение float на 0.5 первое означает, что мы получим искомое значение, если мы находимся в диапазоне, где float по-прежнему имеет достаточно высокое разрешение, чтобы представлять числа рядом с тем, которое мы ищем.

Answer 4

import math

def is_square(n):
    sqrt = math.sqrt(n)
    return (sqrt - int(sqrt)) == 0

Идеальный квадрат - это число, которое может быть выражено как произведение двух равных целых чисел. math.sqrt(number) вернуть a float. int(math.sqrt(number)) приводит результат к int.

Если квадратный корень является целым числом, например, как 3, то math.sqrt(number) - int(math.sqrt(number)) будет равно 0, и if заявление будет False.Если квадратный корень был вещественным числом типа 3.2, то это будет True и выведите "это не идеальный квадрат".

Это терпит неудачу из-за большой неквадратный, такой как 152415789666209426002111556165263283035677490.

Answer 5

Если вам интересно, у меня есть чисто математический ответ на аналогичный вопрос в math stackexchange, "Обнаружение идеальных квадратов быстрее, чем путем извлечения квадратного корня".

Моя собственная реализация isSquare (n), возможно, не самая лучшая, но она мне нравится.Мне потребовалось несколько месяцев изучения теории математики, цифровых вычислений и программирования на python, сравнения себя с другими авторами и т.д., Чтобы этот метод действительно сработал.Однако мне нравится его простота и эффективность.Я не видел ничего лучше.Скажи мне, что ты думаешь.

def isSquare(n):
    ## Trivial checks
    if type(n) != int:  ## integer
        return False
    if n < 0:      ## positivity
        return False
    if n == 0:      ## 0 pass
        return True

    ## Reduction by powers of 4 with bit-logic
    while n&3 == 0:    
        n=n>>2

    ## Simple bit-logic test. All perfect squares, in binary,
    ## end in 001, when powers of 4 are factored out.
    if n&7 != 1:
        return False

    if n==1:
        return True  ## is power of 4, or even power of 2


    ## Simple modulo equivalency test
    c = n%10
    if c in {3, 7}:
        return False  ## Not 1,4,5,6,9 in mod 10
    if n % 7 in {3, 5, 6}:
        return False  ## Not 1,2,4 mod 7
    if n % 9 in {2,3,5,6,8}:
        return False  
    if n % 13 in {2,5,6,7,8,11}:
        return False  

    ## Other patterns
    if c == 5:  ## if it ends in a 5
        if (n//10)%10 != 2:
            return False    ## then it must end in 25
        if (n//100)%10 not in {0,2,6}: 
            return False    ## and in 025, 225, or 625
        if (n//100)%10 == 6:
            if (n//1000)%10 not in {0,5}:
                return False    ## that is, 0625 or 5625
    else:
        if (n//10)%4 != 0:
            return False    ## (4k)*10 + (1,9)


    ## Babylonian Algorithm. Finding the integer square root.
    ## Root extraction.
    s = (len(str(n))-1) // 2
    x = (10**s) * 4

    A = {x, n}
    while x * x != n:
        x = (x + (n // x)) >> 1
        if x in A:
            return False
        A.add(x)
    return True

Довольно прямолинейно.Сначала он проверяет, что у нас есть целое число, причем положительное.Иначе в этом нет никакого смысла.Это позволяет 0 проскользнуть как True (необходимо, иначе следующий блок будет бесконечным циклом).

Следующий блок кода систематически удаляет степени 4 в очень быстром подалгоритме, использующем битовый сдвиг и битовые логические операции.В конечном счете мы находим исходную площадь не нашего исходного n, а a kЭто уменьшает размер числа, с которым мы работаем, и действительно ускоряет вавилонский метод, но также ускоряет и другие проверки.

Третий блок кода выполняет простой булевский битово-логический тест.Наименее значащие три цифры в двоичном формате любого идеального квадрата равны 001.Всегда.Во всяком случае, за исключением начальных нулей, получающихся в результате степеней 4, которые уже были учтены.Если он не проходит тест, вы сразу понимаете, что это не квадрат.Если это пройдет, вы не можете быть уверены.

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

Как и в третьем блоке, четвертый проверяет значение, разделяемое единицами, в десятичной системе счисления, используя простой оператор модуля, и имеет тенденцию улавливать значения, которые проскальзывают через предыдущий тест.Также тест mod 7, mod 8, mod 9 и mod 13.

Пятый блок кода проверяет наличие некоторых хорошо известных шаблонов perfect square.Числам, оканчивающимся на 1 или 9, предшествует число, кратное четырем.А числа, оканчивающиеся на 5, должны заканчиваться на 5625, 0625, 225 или 025.Я включил другие, но понял, что они были избыточными или фактически никогда не использовались.

Наконец, шестой блок кода очень похож на ответ главного ответчика - Алекса Мартелли.В основном находит квадратный корень, используя древний вавилонский алгоритм, но ограничивает его целочисленными значениями, игнорируя плавающую точку.Сделано как для повышения скорости, так и для расширения значений, которые можно проверить.Я использовал наборы вместо списков, потому что это занимает гораздо меньше времени, я использовал битовые сдвиги вместо деления на два, и я разумно выбрал начальное начальное значение гораздо эффективнее.

Кстати, я проверил рекомендуемый номер теста Алекса Мартелли, а также несколько чисел на много порядков больше, таких как:

x=1000199838770766116385386300483414671297203029840113913153824086810909168246772838680374612768821282446322068401699727842499994541063844393713189701844134801239504543830737724442006577672181059194558045164589783791764790043104263404683317158624270845302200548606715007310112016456397357027095564872551184907513312382763025454118825703090010401842892088063527451562032322039937924274426211671442740679624285180817682659081248396873230975882215128049713559849427311798959652681930663843994067353808298002406164092996533923220683447265882968239141724624870704231013642255563984374257471112743917655991279898690480703935007493906644744151022265929975993911186879561257100479593516979735117799410600147341193819147290056586421994333004992422258618475766549646258761885662783430625 ** 2
for i in range(x, x+2):
    print(i, isSquare(i))

напечатал следующие результаты:

1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890625 True
1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890626 False

И он сделал это за 0,33 секунды.

На мой взгляд, мой алгоритм работает так же, как алгоритм Алекса Мартелли, со всеми его преимуществами, но имеет дополнительное преимущество - высокоэффективное отклонение простых тестов, которое экономит много времени, не говоря уже об уменьшении размера тестовых чисел на степени 4, что повышает скорость, эффективность, точность и размер тестируемых чисел.Вероятно, это особенно верно в реализациях, отличных от Python.

Примерно 99% всех целых чисел отклоняются как неквадратичные еще до того, как будет реализовано извлечение вавилонского корня, и за 2/3 времени, которое потребовалось бы вавилонянину, чтобы отклонить целое число.И хотя эти тесты не ускоряют процесс настолько значительно, уменьшение всех номеров тестов до нечетного путем деления всех степеней на 4 действительно ускоряет вавилонское испытание.

Я провел сравнительный тест по времени.Я последовательно протестировал все целые числа от 1 до 10 миллионов.Используя только вавилонский метод сам по себе (с моим специально разработанным первоначальным предположением), моему Surface 3 потребовалось в среднем 165 секунд (со 100% точностью).Используя только логические тесты в моем алгоритме (исключая вавилонский), это заняло 127 секунд, он отклонил 99% всех целых чисел как неквадратные, без ошибочного отклонения каких-либо идеальных квадратов.Из тех целых чисел, которые прошли, только 3% были идеальными квадратами (гораздо более высокая плотность).Используя полный алгоритм, описанный выше, который использует как логические тесты, так и извлечение вавилонского корня, мы получаем 100% точность и завершаем тест всего за 14 секунд.Проверка первых 100 миллионов целых чисел занимает примерно 2 минуты 45 секунд.

Редактировать:Мне удалось еще больше сократить время.Теперь я могу протестировать целые числа от 0 до 100 миллионов за 1 минуту 40 секунд.Много времени тратится впустую на проверку типа данных и их положительности.Исключите самые первые две проверки, и я сокращу эксперимент на минуту.Нужно предположить, что пользователь достаточно умен, чтобы знать, что негативы и плавающие значения не являются идеальными квадратами.

Answer 6

Это может быть решено с помощью в decimal модуль получить квадратные корни произвольной точности и легко проверить "точность":

import math
from decimal import localcontext, Context, Inexact

def is_perfect_square(x):
    # If you want to allow negative squares, then set x = abs(x) instead
    if x < 0:
        return False

    # Create localized, default context so flags and traps unset
    with localcontext(Context()) as ctx:
        # Set a precision sufficient to represent x exactly; `x or 1` avoids
        # math domain error for log10 when x is 0
        ctx.prec = math.ceil(math.log10(x or 1)) + 1  # Wrap ceil call in int() on Py2
        # Compute integer square root; don't even store result, just setting flags
        ctx.sqrt(x).to_integral_exact()
        # If previous line couldn't represent square root as exact int, sets Inexact flag
        return not ctx.flags[Inexact]

Для демонстрации с поистине огромными значениями:

# I just kept mashing the numpad for awhile :-)
>>> base = 100009991439393999999393939398348438492389402490289028439083249803434098349083490340934903498034098390834980349083490384903843908309390282930823940230932490340983098349032098324908324098339779438974879480379380439748093874970843479280329708324970832497804329783429874329873429870234987234978034297804329782349783249873249870234987034298703249780349783497832497823497823497803429780324
>>> sqr = base ** 2
>>> sqr ** 0.5  # Too large to use floating point math
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: int too large to convert to float

>>> is_perfect_power(sqr)
True
>>> is_perfect_power(sqr-1)
False
>>> is_perfect_power(sqr+1)
False

Если вы увеличиваете размер тестируемого значения, это в конечном итоге становится довольно медленным (занимает около секунды для квадрата в 200 000 бит), но для более умеренных чисел (скажем, 20 000 бит) это все равно быстрее, чем человек заметил бы для отдельных значений (~ 33 мс на моей машине).Но поскольку скорость не была вашей главной заботой, это хороший способ сделать это с помощью стандартных библиотек Python.

Конечно, это было бы намного быстрее использовать gmpy2 и просто протестируйте gmpy2.mpz(x).is_square(), но если вам не нравятся сторонние пакеты, то вышеприведенное работает довольно хорошо.

Answer 7

Я только что опубликовал небольшое изменение некоторых приведенных выше примеров в другой теме (Нахождение идеальных квадратов) и подумал, что я бы включил небольшое изменение того, что я опубликовал там здесь (используя nsqrt в качестве временной переменной), на случай, если это представляет интерес / польза:

import math

def is_square(n):
  if not (isinstance(n, int) and (n >= 0)):
    return False 
  else:
    nsqrt = math.sqrt(n)
    return nsqrt == math.trunc(nsqrt)

Это неверно для большого неквадратичного значения, такого как 152415789666209426002111556165263283035677490.

Answer 8

Мой ответ таков:

def is_square(x):
    return x**.5 % 1 == 0

В основном он извлекает квадратный корень, затем умножает по модулю на 1, чтобы удалить целую часть, и если результат равен 0, возвращает True в противном случае вернитесь False.В этом случае x может быть любым большим числом, просто не таким большим, как максимальное число с плавающей запятой, которое может обрабатывать python:1.7976931348623157e+308

Это неверно для большого неквадратичного значения, такого как 152415789666209426002111556165263283035677490.

Answer 9

Это мой метод:

def is_square(n) -> bool:
    return int(n**0.5)**2 == int(n)

Извлеките квадратный корень из числа.Преобразовать в целое число.Возьмите площадь.Если числа равны, то это идеальный квадрат, в противном случае нет.

Это неверно для большого квадрата, такого как 152415789666209426002111556165263283035677489.

Answer 10

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

Вероятно, вам лучше использовать ответ FogleBirds - хотя будьте осторожны, поскольку арифметика с плавающей запятой является приблизительной, что может отбросить этот подход.В принципе, вы могли бы получить ложноположительный результат от большого целого числа, которое на единицу больше, чем идеальный квадрат, например, из-за потери точности.

Answer 11

1. Решите, какой длины будет это число.
2. возьмем дельту 0.000000000000......000001
3. посмотрите, является ли (sqrt(x)) ^ 2 - x больше / равно / меньше дельты, и примите решение на основе ошибки дельты.

Answer 12

Этот ответ относится не к вашему заявленному вопросу, а к неявному вопросу, который я вижу в опубликованном вами коде, т. Е. "как проверить, является ли что-то целым числом?"

Первый ответ, который вы обычно получаете на этот вопрос, - "Не надо!" И это правда, что в Python проверка типов обычно не является правильным решением.

Однако для этих редких исключений вместо поиска десятичной точки в строковом представлении числа, что нужно сделать, это использовать isinstance - это момент функция:

>>> isinstance(5,int)
True
>>> isinstance(5.0,int)
False

Конечно, это относится к переменной, а не к значению.Если бы я хотел определить, является ли значение было целым числом, я бы сделал это:

>>> x=5.0
>>> round(x) == x
True

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

Answer 13

Если вы хотите выполнить цикл по диапазону и сделать что-то для каждого числа, которое НЕ является идеальным квадратом, вы могли бы сделать что-то вроде этого:

def non_squares(upper):
    next_square = 0
    diff = 1
    for i in range(0, upper):
        if i == next_square:
            next_square += diff
            diff += 2
            continue
        yield i

Если вы хотите что-то сделать для каждого числа, являющегося идеальным квадратом, генератор еще проще:

(n * n for n in range(upper))

Answer 14

Я думаю, что это работает и очень просто:

import math

def is_square(num):
    sqrt = math.sqrt(num)
    return sqrt == int(sqrt)

Это неверно для большого неквадратичного значения, такого как 152415789666209426002111556165263283035677490.

Answer 15

import math

def is_square(n):
    sqrt = math.sqrt(n)
    return sqrt == int(sqrt)

Это терпит неудачу из-за большой неквадратный, такой как 152415789666209426002111556165263283035677490.