Как я могу проверить, является ли число идеальным квадратом?
Скорость не имеет значения, пока просто работает.
python
math
perfect-square
Acumenus
источник
источник
Ответы:
Проблема с использованием любых вычислений с плавающей запятой (
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)
Подсказка: он основан на «вавилонском алгоритме» извлечения квадратного корня, см. Википедию . Это делает работу для любого положительного числа , для которых у вас есть достаточно памяти для вычисления , чтобы перейти к завершению ;-).
Изменить : давайте посмотрим на пример ...
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, чистая скорость ; -) ...
источник
set([x])
={x}
set
ovekill? Разве вавилонский не сводится к томуint(sqrt(x))
, что нам просто нужно проверитьprev != next
?Используйте метод Ньютона, чтобы быстро найти ближайший квадратный корень целого числа, затем возвести его в квадрат и посмотреть, является ли это вашим числом. См. Isqrt .
Python ≥ 3.8 имеет
math.isqrt
. При использовании более старой версии Python, обратите внимание на «def isqrt(n)
» реализации здесь .import math def is_square(i: int) -> bool: return i == math.isqrt(i) ** 2
источник
Поскольку вы никогда не можете полагаться на точные сравнения при вычислениях с плавающей запятой (например, эти способы вычисления квадратного корня), менее подверженная ошибкам реализация будет
import math def is_square(integer): root = math.sqrt(integer) return integer == int(root + 0.5) ** 2
Представьте
integer
IS9
.math.sqrt(9)
может быть3.0
, но это также может быть что-то вроде2.99999
или3.00001
, поэтому немедленное возведение результата в квадрат ненадежно. Зная, что этоint
принимает минимальное значение, увеличение значения с плавающей запятой0.5
сначала означает, что мы получим значение, которое ищем, если мы находимся в диапазоне, гдеfloat
все еще есть достаточно высокое разрешение, чтобы представлять числа, близкие к тому, которое мы ищем. .источник
if int(root + 0.5) ** 2 == integer:
если быint
действовали какfloor
числа, которые нам небезразличны.math.sqrt(9)
реально ли может быть2.99999
? Pythonfloat
сопоставляется с Cdouble
, но я думаю, что даже 16-битный тип FP имеет большую точность, чем это, может быть, если бы у вас был компилятор C, который использовал 8-битный FP («minifloats») в качестве своегоdouble
типа? Я полагаю, что это технически возможно, но мне кажется маловероятным, что это так на любом компьютере, на котором сегодня работает Python.math.sqrt(9)
это вернется2.99999
к какой-либо конкретной системе, но фактический результат зависит от системы и не может быть точным.Если вам интересно, у меня есть чисто математический ответ на аналогичный вопрос на 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 в очень быстром подалгоритме с использованием битового сдвига и битовых логических операций. В конечном итоге мы находим isSquare не нашего исходного n, а k <n, которое было уменьшено до 4, если это возможно. Это уменьшает размер числа, с которым мы работаем, и действительно ускоряет вавилонский метод, но также ускоряет другие проверки.
Третий блок кода выполняет простой тест на основе логической битовой логики. Три младшие значащие цифры в двоичном формате любого полного квадрата равны 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 секунд. Уходит много времени на проверку типа данных и положительности. Убрав самые первые две проверки, я сократил эксперимент на минуту. Следует предположить, что пользователь достаточно умен, чтобы знать, что негативы и числа с плавающей точкой - не идеальные квадраты.
источник
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.
источник
if (math.sqrt(number)-int(math.sqrt(number))):
вa=math.sqrt(number)
то другую линию для:if a-int(a):
. Это потому, что ему нужно вычислить квадратный корень только один раз, что для больших n важноМой ответ:
def is_square(x): return x**.5 % 1 == 0
Он в основном делает квадратный корень, затем по модулю 1, чтобы удалить целую часть, и если результат равен 0, верните, в
True
противном случае вернитеFalse
. В этом случае x может быть любым большим числом, но не таким большим, как максимальное число с плавающей запятой, которое может обрабатывать python: 1.7976931348623157e + 308Это неверно для большого неквадрата, такого как 152415789666209426002111556165263283035677490.
источник
Эту проблему можно решить с помощью
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
Если вы увеличиваете размер тестируемого значения, это в конечном итоге становится довольно медленным (занимает около секунды для квадрата 200000 бит), но для более умеренных чисел (скажем, 20000 бит) это все равно быстрее, чем человек заметил бы для индивидуальные значения (~ 33 мс на моей машине). Но поскольку скорость не была вашей главной заботой, это хороший способ сделать это с помощью стандартных библиотек Python.
Конечно, было бы намного быстрее использовать
gmpy2
и просто тестироватьgmpy2.mpz(x).is_square()
, но если сторонние пакеты вам не нравятся, вышеперечисленное работает довольно хорошо.источник
Я только что опубликовал небольшое изменение некоторых из приведенных выше примеров в другом потоке ( Поиск идеальных квадратов ) и подумал, что включу небольшое изменение того, что я опубликовал здесь (используя 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.
источник
Это мой метод:
def is_square(n) -> bool: return int(n**0.5)**2 == int(n)
Извлеките квадратный корень из числа. Преобразовать в целое число. Возьми площадь. Если числа равны, то это полный квадрат, иначе нет.
Это неверно для большого квадрата, например 152415789666209426002111556165263283035677489.
источник
Вы можете выполнить двоичный поиск округленного квадратного корня. Возведите результат в квадрат, чтобы увидеть, соответствует ли он исходному значению.
Вероятно, вам будет лучше с ответом FogleBirds - хотя будьте осторожны, поскольку арифметика с плавающей запятой является приблизительной, что может отбросить этот подход. В принципе, вы можете получить ложное срабатывание от большого целого числа, которое на единицу больше, чем полный квадрат, например, из-за потери точности.
источник
Если модуль (остаток), оставшийся от деления на квадратный корень, равен 0, то это полный квадрат.
def is_square(num: int) -> bool: return num % math.sqrt(num) == 0
Я проверил это по списку идеальных квадратов, доходящему до 1000.
источник
источник
Этот ответ не относится к заданному вами вопросу, а относится к неявному вопросу, который я вижу в опубликованном вами коде, то есть «как проверить, является ли что-то целым числом?»
Первый ответ, который вы обычно получите на этот вопрос, - «Не надо!» И это правда, что в Python проверка типов обычно не является правильным занятием.
Однако для этих редких исключений вместо поиска десятичной точки в строковом представлении числа нужно использовать функцию isinstance :
>>> isinstance(5,int) True >>> isinstance(5.0,int) False
Конечно, это относится скорее к переменной, чем к значению. Если бы я хотел определить, является ли значение целым числом, я бы сделал следующее:
>>> x=5.0 >>> round(x) == x True
Но, как подробно рассказали все остальные, существуют проблемы с плавающей запятой, которые следует учитывать в большинстве примеров такого рода, не связанных с игрушками.
источник
Если вы хотите перебрать диапазон и сделать что-то для каждого числа, которое НЕ является идеальным квадратом, вы можете сделать что-то вроде этого:
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))
источник
Я думаю, что это работает и очень просто:
import math def is_square(num): sqrt = math.sqrt(num) return sqrt == int(sqrt)
Это неверно для большого неквадрата, такого как 152415789666209426002111556165263283035677490.
источник
Вариант решения @Alex Martelli без
set
Когда
x in seen
этоTrue
:x
последовательность 511, 256, 129, 68, 41, 32, 31 , 31 ;Следовательно, достаточно остановиться, как только ток
x
станет больше или равен предыдущему:def is_square(n): assert n > 1 previous = n x = n // 2 while x * x != n: x = (x + (n // x)) // 2 if x >= previous: return False previous = x return True x = 12345678987654321234567 ** 2 assert not is_square(x-1) assert is_square(x) assert not is_square(x+1)
Эквивалентность оригинальному алгоритму проверена для 1 <n <10 ** 7. На том же интервале этот чуть более простой вариант примерно в 1,4 раза быстрее.
источник
a=int(input('enter any number')) flag=0 for i in range(1,a): if a==i*i: print(a,'is perfect square number') flag=1 break if flag==1: pass else: print(a,'is not perfect square number')
источник
Идея состоит в том, чтобы запустить цикл от i = 1 до этажа (sqrt (n)), а затем проверить, получается ли при возведении в квадрат n.
bool isPerfectSquare(int n) { for (int i = 1; i * i <= n; i++) { // If (i * i = n) if ((n % i == 0) && (n / i == i)) { return true; } } return false; }
источник
import math def is_square(n): sqrt = math.sqrt(n) return sqrt == int(sqrt)
Это не подходит для большого неквадрата, такого как 152415789666209426002111556165263283035677490.
источник