Jak mogę sprawdzić, czy liczba jest idealnym kwadratem?
Na razie prędkość nie ma znaczenia, po prostu działa.
python
math
perfect-square
Acumenus
źródło
źródło
Odpowiedzi:
Problem z poleganiem na dowolnym obliczeniu zmiennoprzecinkowym (
math.sqrt(x)
lubx**0.5
) polega na tym, że nie można być naprawdę pewnym, że jest dokładny (dla wystarczająco dużych liczb całkowitychx
nie będzie, a może nawet przepełnienie). Na szczęście (jeśli się nie spieszy ;-) istnieje wiele podejść czystych liczb całkowitych, takich jak następujące ...: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)
Wskazówka: jest oparty na „algorytmie babilońskim” dla pierwiastka kwadratowego, patrz wikipedia . To robi pracy w dowolnym liczbę dodatnią, dla których masz wystarczająco dużo pamięci do obliczeń, aby przejść do końca ;-).
Edycja : zobaczmy przykład ...
x = 12345678987654321234567 ** 2 for i in range(x, x+2): print i, is_square(i)
to drukuje zgodnie z życzeniem (i też w rozsądnym czasie ;-):
152415789666209426002111556165263283035677489 True 152415789666209426002111556165263283035677490 False
Proszę, zanim zaproponujesz rozwiązania oparte na pośrednich wynikach zmiennoprzecinkowych, upewnij się, że działają one poprawnie na tym prostym przykładzie - nie jest to takie trudne (potrzebujesz tylko kilku dodatkowych kontroli na wypadek, gdyby obliczony sqrt był trochę wyłączony), po prostu bierze trochę troski.
A potem spróbuj
x**7
i znajdź sprytny sposób na obejście problemu,oczywiście będziesz musiał stawać się coraz bardziej sprytny w miarę wzrostu liczby.
Gdybym był w pośpiechu, oczywiście, będę używać gmpy - ale potem, jestem wyraźnie tendencyjne ;-).
>>> import gmpy >>> gmpy.is_square(x**7) 1 >>> gmpy.is_square(x**7 + 1) 0
Tak, wiem, to po prostu takie proste, że czuję się jak oszukiwanie (trochę tak, jak ogólnie czuję do Pythona ;-) - w ogóle nie ma sprytu, po prostu idealna bezpośredniość i prostota (aw przypadku gmpy, czysta szybkość ; -) ...
źródło
set([x])
={x}
set
zabójstwo? Czy język babiloński nie zbiega się po prostu do tegoint(sqrt(x))
, gdzie musimy tylko sprawdzić, czyprev != next
?Użyj metody Newtona, aby szybko wyzerować najbliższy pierwiastek kwadratowy z liczby całkowitej, a następnie podnieść go do kwadratu i sprawdzić, czy to twoja liczba. Zobacz isqrt .
Python ≥ 3,8 ma
math.isqrt
. Jeśli używasz starszej wersji Pythona, poszukajdef isqrt(n)
implementacji " " tutaj .import math def is_square(i: int) -> bool: return i == math.isqrt(i) ** 2
źródło
Ponieważ nigdy nie możesz polegać na dokładnych porównaniach, gdy mamy do czynienia z obliczeniami zmiennoprzecinkowymi (takimi jak te sposoby obliczania pierwiastka kwadratowego), implementacja mniej podatna na błędy byłaby
import math def is_square(integer): root = math.sqrt(integer) return integer == int(root + 0.5) ** 2
Wyobraź sobie, że
integer
jest9
.math.sqrt(9)
może być3.0
, ale może to być coś w rodzaju2.99999
lub3.00001
, więc natychmiastowe podniesienie wyniku do kwadratu nie jest wiarygodne. Wiedząc, żeint
przyjmuje wartość minimalną, zwiększając wartość zmiennoprzecinkową,0.5
najpierw otrzymamy wartość, której szukamy, jeśli znajdujemy się w zakresie, w którymfloat
nadal ma wystarczająco dobrą rozdzielczość, aby przedstawić liczby zbliżone do tej, której szukamy .źródło
if int(root + 0.5) ** 2 == integer:
gdybyint
działał tak, jakfloor
w przypadku liczb, na których nam zależy.math.sqrt(9)
naprawdę może być kiedykolwiek2.99999
? Pythonfloat
odwzorowuje na Cdouble
, ale myślę, że nawet 16-bitowy typ FP ma większą precyzję, więc może gdybyś miał kompilator C, który używał 8-bitowego FP („minifloats”) jako swojegodouble
typu? Przypuszczam, że jest to technicznie możliwe, ale wydaje mi się mało prawdopodobne, aby tak było na każdym komputerze z Pythonem.math.sqrt(9)
powróci2.99999
w jakimkolwiek konkretnym systemie, ale rzeczywisty wynik jest zależny od systemu i nie można oczekiwać, że będzie dokładny.Jeśli jesteś zainteresowany, mam czysto matematyczną odpowiedź na podobne pytanie w matematycznej wymianie stosów: „Wykrywanie doskonałych kwadratów szybciej niż przez wyodrębnianie pierwiastka kwadratowego” .
Moja własna implementacja isSquare (n) może nie być najlepsza, ale mi się podoba. Zajęło mi kilka miesięcy nauki teorii matematyki, obliczeń cyfrowych i programowania w Pythonie, porównywanie się z innymi autorami itp., Aby naprawdę kliknąć tę metodę. Podoba mi się jednak jego prostota i skuteczność. Nie widziałem lepszego. Powiedz mi co myślisz.
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
Całkiem proste. Najpierw sprawdza, czy mamy liczbę całkowitą, a do tego dodatnią. W przeciwnym razie nie ma sensu. Pozwala 0 prześlizgnąć się jako True (konieczny lub następny blok to nieskończona pętla).
Następny blok kodu systematycznie usuwa potęgi 4 w bardzo szybkim pod-algorytmie wykorzystującym przesunięcie bitów i operacje logiki bitowej. Ostatecznie nie znajdujemy isSquare naszego pierwotnego n, ale k <n, który został przeskalowany potęgami 4, jeśli to możliwe. Zmniejsza to rozmiar liczby, z którą pracujemy i naprawdę przyspiesza metodę babilońską, ale także przyspiesza inne kontrole.
Trzeci blok kodu wykonuje prosty test logiki bitowej. Dwójkowo najmniej znaczące cyfry dowolnego doskonałego kwadratu to 001. Zawsze. Poza zerami wiodącymi wynikającymi zresztą z potęg 4, które zostały już uwzględnione. Jeśli nie przejdzie testu, od razu wiesz, że to nie jest kwadrat. Jeśli to minie, nie możesz być pewien.
Ponadto, jeśli otrzymamy 1 dla wartości testowej, wtedy liczba testowa była pierwotnie potęgą 4, w tym być może 1.
Podobnie jak trzeci blok, czwarty testuje wartość jednomiejscową w systemie dziesiętnym przy użyciu prostego operatora modułu i ma tendencję do wychwytywania wartości, które prześlizgnęły się przez poprzedni test. Również test mod 7, mod 8, mod 9 i mod 13.
Piąty blok kodu sprawdza niektóre z dobrze znanych doskonałych wzorców kwadratowych. Liczby kończące się na 1 lub 9 są poprzedzone wielokrotnością czterech. A liczby kończące się na 5 muszą kończyć się na 5625, 0625, 225 lub 025. Dodałem inne, ale zdałem sobie sprawę, że są one zbędne lub nigdy nie zostały użyte.
Wreszcie, szósty blok kodu bardzo przypomina to, co odpowiada najpopularniejszy odpowiadający - Alex Martelli -. Zasadniczo znajduje pierwiastek kwadratowy za pomocą starożytnego algorytmu babilońskiego, ale ogranicza go do wartości całkowitych, ignorując zmiennoprzecinkowe. Sporządzono zarówno ze względu na szybkość, jak i rozszerzenie wielkości wartości, które można testować. Użyłem zestawów zamiast list, ponieważ zajmuje to znacznie mniej czasu, użyłem przesunięć bitowych zamiast dzielenia przez dwa i sprytnie wybrałem początkową wartość początkową znacznie wydajniej.
Nawiasem mówiąc, przetestowałem zalecany numer testu Alexa Martellego, a także kilka liczb o wiele rzędów wielkości większych, takich jak:
x=1000199838770766116385386300483414671297203029840113913153824086810909168246772838680374612768821282446322068401699727842499994541063844393713189701844134801239504543830737724442006577672181059194558045164589783791764790043104263404683317158624270845302200548606715007310112016456397357027095564872551184907513312382763025454118825703090010401842892088063527451562032322039937924274426211671442740679624285180817682659081248396873230975882215128049713559849427311798959652681930663843994067353808298002406164092996533923220683447265882968239141724624870704231013642255563984374257471112743917655991279898690480703935007493906644744151022265929975993911186879561257100479593516979735117799410600147341193819147290056586421994333004992422258618475766549646258761885662783430625 ** 2 for i in range(x, x+2): print(i, isSquare(i))
wydrukował następujące wyniki:
1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890625 True 1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890626 False
I zrobiło to w 0,33 sekundy.
Moim zdaniem mój algorytm działa tak samo jak algorytm Alexa Martellego, ze wszystkimi jego zaletami, ale ma dodatkową zaletę wysoce wydajnych odrzutów prostych testów, które oszczędzają dużo czasu, nie wspominając o zmniejszeniu rozmiaru liczb testowych o potęgi 4, co poprawia szybkość, wydajność, dokładność i rozmiar liczb, które można testować. Prawdopodobnie szczególnie prawdziwe w implementacjach innych niż Python.
Około 99% wszystkich liczb całkowitych jest odrzucanych jako niekwadratowe, zanim babilońskie wyodrębnianie pierwiastków zostanie wdrożone, a za 2/3 czasu babilońskiemu zajęłoby odrzucenie liczby całkowitej. I chociaż testy te nie przyspieszają znacząco procesu, to redukcja wszystkich liczb testowych do nieparzystej liczby przez podzielenie wszystkich potęg 4 naprawdę przyspiesza test babiloński.
Zrobiłem test porównania czasu. Przetestowałem kolejno wszystkie liczby całkowite od 1 do 10 milionów. Używając samej metody babilońskiej (z moim specjalnie dostosowanym początkowym przypuszczeniem), Surface 3 zajęło mi średnio 165 sekund (ze 100% dokładnością). Używając tylko testów logicznych w moim algorytmie (z wyjątkiem babilońskiego), zajęło to 127 sekund, odrzucił 99% wszystkich liczb całkowitych jako niekwadratowe, nie odrzucając przez pomyłkę żadnych doskonałych kwadratów. Spośród tych liczb całkowitych, które przeszły, tylko 3% było idealnymi kwadratami (znacznie większa gęstość). Używając powyższego pełnego algorytmu, który wykorzystuje zarówno testy logiczne, jak i ekstrakcję korzeni babilońskich, mamy 100% dokładność i zakończenie testu w zaledwie 14 sekund. Testowanie pierwszych 100 milionów liczb całkowitych zajmuje około 2 minut i 45 sekund.
EDYCJA: Udało mi się skrócić czas dalej. Mogę teraz przetestować liczby całkowite od 0 do 100 milionów w ciągu 1 minuty i 40 sekund. Dużo czasu jest marnowane na sprawdzanie typu danych i ich pozytywności. Wyeliminuj pierwsze dwie kontrole i skrócę eksperyment o minutę. Należy założyć, że użytkownik jest wystarczająco inteligentny, aby wiedzieć, że negatywy i elementy pływające nie są idealnymi kwadratami.
źródło
import math def is_square(n): sqrt = math.sqrt(n) return (sqrt - int(sqrt)) == 0
Idealny kwadrat to liczba, którą można wyrazić jako iloczyn dwóch równych liczb całkowitych.
math.sqrt(number)
powrót afloat
.int(math.sqrt(number))
rzutuje wynik doint
.Jeśli pierwiastek kwadratowy jest liczbą całkowitą, na przykład 3, to
math.sqrt(number) - int(math.sqrt(number))
będzie 0, aif
instrukcja będzieFalse
. Jeśli pierwiastek kwadratowy byłby liczbą rzeczywistą, taką jak 3,2, to będzieTrue
i wypisuje "to nie jest idealny kwadrat".Błąd w przypadku dużego elementu innego niż kwadrat, takiego jak 152415789666209426002111556165263283035677490.
źródło
if (math.sqrt(number)-int(math.sqrt(number))):
doa=math.sqrt(number)
ówczesnego inną linię dla:if a-int(a):
. Dzieje się tak, ponieważ wystarczy tylko raz obliczyć pierwiastek kwadratowy, który imo dla dużego n jest znaczącyMoja odpowiedź brzmi:
def is_square(x): return x**.5 % 1 == 0
Zasadniczo wykonuje pierwiastek kwadratowy, a następnie modulo o 1, aby usunąć część całkowitą, a jeśli wynik jest równy 0, w
True
przeciwnym razie zwróćFalse
. W tym przypadku x może być dowolną dużą liczbą, tylko nie tak dużą, jak maksymalna liczba zmiennoprzecinkowa obsługiwana przez Pythona: 1.7976931348623157e + 308Jest to niepoprawne w przypadku dużego obiektu innego niż kwadrat, takiego jak 152415789666209426002111556165263283035677490.
źródło
Można to rozwiązać za pomocą
decimal
modułu, aby uzyskać dowolną dokładność pierwiastków kwadratowych i łatwo sprawdzić „dokładność”: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]
Do demonstracji z naprawdę dużymi wartościami:
# 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
Jeśli zwiększysz rozmiar testowanej wartości, w końcu stanie się to raczej powolne (zajmuje blisko sekundy w przypadku kwadratu 200 000 bitów), ale w przypadku bardziej umiarkowanych liczb (powiedzmy 200 000 bitów) jest to nadal szybsze niż człowiek zauważył indywidualne wartości (~ 33 ms na moim komputerze). Ale ponieważ szybkość nie była Twoim głównym zmartwieniem, jest to dobry sposób na zrobienie tego ze standardowymi bibliotekami Pythona.
Oczywiście byłoby znacznie szybciej w użyciu
gmpy2
i po prostu testowaniugmpy2.mpz(x).is_square()
, ale jeśli pakiety innych firm nie są twoją rzeczą, powyższe działa całkiem dobrze.źródło
Właśnie opublikowałem niewielką zmianę niektórych z powyższych przykładów w innym wątku ( Znajdowanie idealnych kwadratów ) i pomyślałem, że uwzględnię niewielką zmianę tego, co tutaj zamieściłem (używając nsqrt jako zmiennej tymczasowej), na wypadek, gdyby było to interesujące / posługiwać się:
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)
Jest to niepoprawne w przypadku dużego obiektu innego niż kwadrat, takiego jak 152415789666209426002111556165263283035677490.
źródło
To jest moja metoda:
def is_square(n) -> bool: return int(n**0.5)**2 == int(n)
Weź pierwiastek kwadratowy z liczby. Konwertuj na liczbę całkowitą. Weź kwadrat. Jeśli liczby są równe, w przeciwnym razie jest to doskonały kwadrat.
Jest to nieprawidłowe w przypadku dużego kwadratu, takiego jak 152415789666209426002111556165263283035677489.
źródło
Możesz wyszukiwać binarnie za zaokrąglony pierwiastek kwadratowy. Wyrównaj wynik do kwadratu, aby sprawdzić, czy pasuje do oryginalnej wartości.
Prawdopodobnie lepiej ci będzie z odpowiedzią FogleBirds - choć uważaj, ponieważ arytmetyka zmiennoprzecinkowa jest przybliżona, co może zrzucić to podejście. Zasadniczo można uzyskać fałszywie dodatni wynik z dużej liczby całkowitej, która jest na przykład o jeden większa niż doskonały kwadrat, z powodu utraty precyzji.
źródło
Jeśli moduł (reszta) pozostałość po podzieleniu przez pierwiastek kwadratowy wynosi 0, to jest to kwadrat doskonały.
def is_square(num: int) -> bool: return num % math.sqrt(num) == 0
Sprawdziłem to na liście doskonałych kwadratów dochodzących do 1000.
źródło
źródło
Ta odpowiedź nie odnosi się do zadanego pytania, ale do niejawnego pytania, które widzę w opublikowanym przez Ciebie kodzie, tj. „Jak sprawdzić, czy coś jest liczbą całkowitą?”
Pierwsza odpowiedź na to pytanie brzmi: „Nie!” I prawdą jest, że w Pythonie sprawdzanie typów zwykle nie jest właściwe.
Jednak w przypadku tych rzadkich wyjątków zamiast szukać kropki dziesiętnej w ciągu reprezentującym liczbę, wystarczy użyć funkcji isinstance :
>>> isinstance(5,int) True >>> isinstance(5.0,int) False
Oczywiście dotyczy to raczej zmiennej niż wartości. Gdybym chciał ustalić, czy wartość jest liczbą całkowitą, zrobiłbym to:
>>> x=5.0 >>> round(x) == x True
Ale jak wszyscy szczegółowo omówili, istnieją kwestie zmiennoprzecinkowe, które należy wziąć pod uwagę w większości przykładów tego rodzaju rzeczy niebędących zabawkami.
źródło
Jeśli chcesz zapętlić zakres i zrobić coś dla każdej liczby, która NIE jest idealnym kwadratem, możesz zrobić coś takiego:
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
Jeśli chcesz zrobić coś dla każdej liczby, która JEST idealnym kwadratem, generator jest jeszcze łatwiejszy:
(n * n for n in range(upper))
źródło
Myślę, że to działa i jest bardzo proste:
import math def is_square(num): sqrt = math.sqrt(num) return sqrt == int(sqrt)
Jest to niepoprawne w przypadku dużego obiektu innego niż kwadrat, takiego jak 152415789666209426002111556165263283035677490.
źródło
Wariant rozwiązania @Alex Martelli bez
set
Kiedy
x in seen
jestTrue
:x
sekwencję 511, 256, 129, 68, 41, 32, 31 , 31 ;Dlatego wystarczy zatrzymać się, gdy tylko prąd
x
będzie większy lub równy poprzedniemu: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)
Równoważność z oryginalnym algorytmem testowanym dla 1 <n <10 ** 7. W tym samym przedziale ten nieco prostszy wariant jest około 1,4 razy szybszy.
źródło
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')
źródło
Chodzi o to, aby uruchomić pętlę od i = 1 do floor (sqrt (n)), a następnie sprawdzić, czy podniesienie do kwadratu daje 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; }
źródło
import math def is_square(n): sqrt = math.sqrt(n) return sqrt == int(sqrt)
Błąd w przypadku dużego elementu innego niż kwadrat, takiego jak 152415789666209426002111556165263283035677490.
źródło