Jak mogę sprawdzić, czy liczba jest idealnym kwadratem?

Na razie prędkość nie ma znaczenia, po prostu działa.

Problem z poleganiem na dowolnym obliczeniu zmiennoprzecinkowym ( math.sqrt(x)lub x**0.5) polega na tym, że nie można być naprawdę pewnym, że jest dokładny (dla wystarczająco dużych liczb całkowitych xnie 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**7i znajdź sprytny sposób na obejście problemu,

OverflowError: long int too large to convert to float

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ść ; -) ...

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, poszukaj def isqrt(n)implementacji " " tutaj .

import math

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

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 integerjest 9. math.sqrt(9)może być 3.0, ale może to być coś w rodzaju 2.99999lub 3.00001, więc natychmiastowe podniesienie wyniku do kwadratu nie jest wiarygodne. Wiedząc, że intprzyjmuje wartość minimalną, zwiększając wartość zmiennoprzecinkową, 0.5najpierw otrzymamy wartość, której szukamy, jeśli znajdujemy się w zakresie, w którym floatnadal ma wystarczająco dobrą rozdzielczość, aby przedstawić liczby zbliżone do tej, której szukamy .

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.

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 a float. int(math.sqrt(number))rzutuje wynik do int.

Jeśli pierwiastek kwadratowy jest liczbą całkowitą, na przykład 3, to math.sqrt(number) - int(math.sqrt(number))będzie 0, a ifinstrukcja będzie False. Jeśli pierwiastek kwadratowy byłby liczbą rzeczywistą, taką jak 3,2, to będzie Truei wypisuje "to nie jest idealny kwadrat".

Błąd w przypadku dużego elementu innego niż kwadrat, takiego jak 152415789666209426002111556165263283035677490.

Moja 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 Trueprzeciwnym 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 + 308

Jest to niepoprawne w przypadku dużego obiektu innego niż kwadrat, takiego jak 152415789666209426002111556165263283035677490.

Można to rozwiązać za pomocą decimalmoduł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 gmpy2i po prostu testowaniu gmpy2.mpz(x).is_square(), ale jeśli pakiety innych firm nie są twoją rzeczą, powyższe działa całkiem dobrze.

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.

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.

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.

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.

1. Zdecyduj, jak długo będzie to numer.
2. weź deltę 0,000000000000 ....... 000001
3. sprawdź, czy (sqrt (x)) ^ 2 - x jest większe / równe / mniejsze niż delta i zdecyduj na podstawie błędu delta.

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.

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))

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.

Wariant rozwiązania @Alex Martelli bez set

Kiedy x in seenjest True:

• W większości przypadków jest to ostatnia dodana, np. 1022 daje xsekwencję 511, 256, 129, 68, 41, 32, 31 , 31 ;
• W niektórych przypadkach (np. Dla poprzedników doskonałych kwadratów) jest to przedostatni dodany, np. 1023 daje 511, 256, 129, 68, 41, 32 , 31, 32 .

Dlatego wystarczy zatrzymać się, gdy tylko prąd xbę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.

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')

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; 
} 

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.