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

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)

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

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

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

вам придётся становиться все умнее, конечно, по мере того, как цифры будут расти.

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

>>> 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 принимает минимальное значение, сначала увеличивая значение с плавающей запятой на 0.5, это означает, что мы получим искомое значение, если находимся в диапазоне, где float все еще имеет достаточно хорошее разрешение для представления номера рядом с тем, который мы ищем.

Answer 4

import math

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

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

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

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

Answer 5

Если вам интересно, у меня есть чисто математический ответ на аналогичный вопрос в math stack exchange Exchange: «Обнаружение идеальных квадратов быстрее, чем путем извлечения квадратного корня» .

Моя собственная реализация 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 в очень быстром под-алгоритме, использующем битовые сдвиги и битовые логические операции. В конечном итоге мы не находим isSquare нашего исходного n, а k

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

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

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

Пятый блок кода проверяет некоторые из известных шаблонов совершенных квадратов. Числам, оканчивающимся на 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 - хотя будьте осторожны, поскольку арифметика с плавающей запятой приблизительна, что может отбросить этот подход. В принципе, вы можете получить ложный положительный результат из большого целого числа, которое на единицу больше идеального квадрата, например, из-за потери точности.