Controllare se un numero è un quadrato perfetto
https://stackoverflow.com/questions/2489435
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Come potrei controllare se un numero è un quadrato perfetto?
La velocità non è di alcuna preoccupazione, per ora, solo di lavoro.
Soluzione
Il problema con il fare affidamento su di calcolo in virgola mobile (math.sqrt(x), o x**0.5) è che non si può davvero essere sicuro che sia esatto (per sufficientemente grande interi x, non essere, e potrebbe anche overflow).Fortunatamente (se uno non ha fretta;-) ci sono molti puro intero approcci, come la seguente...:
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)
Suggerimento:esso si basa sul "Babilonese algoritmo" per la radice quadrata, vedere wikipedia.Si non lavoro per un qualsiasi numero positivo per il quale si dispone di memoria sufficiente per il calcolo di procedere al completamento;-).
Modifica:vediamo un esempio...
x = 12345678987654321234567 ** 2
for i in range(x, x+2):
print i, is_square(i)
questa stampa, come desiderato (e in un ragionevole lasso di tempo, troppo;-):
152415789666209426002111556165263283035677489 True
152415789666209426002111556165263283035677490 False
Per favore, prima di proporre soluzioni basate su floating point risultati intermedi, assicurarsi che funzionino correttamente su questo semplice esempio-non è che rigido (hai solo bisogno di un paio di controlli supplementari nel caso in cui il sqrt calcolato è un po 'fuori), appena prende un po' di attenzione.
E poi provare con x**7 e trovare un modo intelligente per risolvere il problema che si otterrà
OverflowError: long int too large to convert to float
dovrete ottenere di più e più intelligente come il numero continua a crescere, naturalmente.
Se Ho era in fretta, naturalmente, mi piacerebbe usare gmpy - ma poi, io sono chiaramente di parte;-).
>>> import gmpy
>>> gmpy.is_square(x**7)
1
>>> gmpy.is_square(x**7 + 1)
0
Sì, lo so, è così facile, ci si sente come barare (un po ' il mio modo di sentire verso Python in generale;-) -- nessuna bravura, ma semplicemente perfetto immediatezza e semplicità (e, nel caso di gmpy, velocità pura;-)...
Altri suggerimenti
Usare il metodo di Newton a zero rapidamente sul numero intero radice quadrata più vicino, poi piazza e vedere se è il tuo numero. Vedere isqrt .
Python ≥ 3.8 ha math.isqrt . Se si utilizza una versione precedente di Python, cercare l'attuazione "def isqrt(n)" qui .
import math
def is_square(i: int) -> bool:
return i == math.isqrt(i) ** 2
Poiché non si può mai dipendere confronto esatto quando si tratta di calcoli in virgola mobile (come questi modi per calcolare la radice quadrata), un meno soggetto a errori attuazione sarebbe
import math
def is_square(integer):
root = math.sqrt(integer)
return integer == int(root + 0.5) ** 2
Immaginate integer è 9. math.sqrt(9) potrebbe essere 3.0, ma potrebbe anche essere qualcosa come 2.99999 o 3.00001, quindi la quadratura del risultato giusto fuori non è affidabile. Sapendo che int assume il valore piano, aumentando il valore float da 0.5 significa prima otterremo il valore che stiamo cercando, se siamo in un intervallo in cui float ha ancora una risoluzione abbastanza bene per rappresentare i numeri vicino a quello per il quale siamo alla ricerca.
import math
def is_square(n):
sqrt = math.sqrt(n)
return (sqrt - int(sqrt)) == 0
Un quadrato perfetto è un numero che può essere espresso come il prodotto di due interi uguali. math.sqrt(number) restituire un float. int(math.sqrt(number)) getta il risultato di int.
Se la radice quadrata è un numero intero, come 3, per esempio, allora math.sqrt(number) - int(math.sqrt(number)) sarà 0, e l'istruzione if verrà False. Se la radice quadrata era un numero reale come 3.2, allora sarà True e la stampa "non è un quadrato perfetto".
Non riesce per un grande non-piazza, come 152415789666209426002111556165263283035677490.
Se siete interessati, ho una risposta pura, matematica per una domanda simile a matematica StackExchange, "Rilevamento quadrati perfetti più velocemente di quanto estraendo radice quadrata" .
La mia propria implementazione di isSquare (n) non può essere il migliore, ma mi piace. Mi ha portato diversi mesi di studio in teoria matematica, calcolo digitale e di programmazione Python, io rispetto ad altri collaboratori, ecc, per fare clic in realtà con questo metodo. Mi piace la sua semplicità ed efficienza però. Io ho mai visto di meglio. Ditemi cosa ne pensate.
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
piuttosto semplice. In primo luogo si verifica che abbiamo un intero, e uno positivo a questo. In caso contrario, non v'è alcun punto. Permette 0 scivolare attraverso come True (necessario o altro blocco successivo è loop infinito).
Il prossimo blocco di codice rimuove sistematicamente i poteri di 4 in modo molto veloce sub-algoritmo utilizzando le funzioni di spostamento bit e di logica bit. Siamo alla fine non trovando l'isSquare del nostro n originale, ma di un k Il terzo blocco di codice esegue un semplice test di bit logica booleana. Meno significativi tre cifre, in binario, di ogni quadrato perfetto sono 001. Sempre. Salva per zeri iniziali derivanti da competenze di 4, in ogni caso, che è stata già eseguita. Se fallisce il test, si sa subito si mangia un quadrato. Se passa, non potete essere sicuri. Inoltre, se si finisce con un 1 per un valore di test allora il numero di test era originariamente una potenza di 4, compreso forse 1 stesso. Come il terzo blocco, la quarta verifica il valore quelli posto in decimale utilizzando semplici operatore modulo, e tende a catturare valori che scivolano attraverso la prova precedente. Anche un mod 7, 8 mod, mod 9, e 13 mod prova. Il quinto blocco di codice controlla per alcuni dei ben noti modelli quadrato perfetto. Numeri che terminano 1 o 9 sono preceduti da un multiplo di quattro. E i numeri che terminano con 5 devono terminare nel 5625, 0625, 225, o 025. avevo incluso altri ma resi conto che erano ridondanti o mai effettivamente utilizzato. Infine, il sesto blocco di codice somiglia molto quello che la parte superiore risposto - Alex Martelli - risposta è. trova fondamentalmente la radice quadrata con l'antica algoritmo babilonese, ma limitandola a intero valori ignorando virgola mobile. Fatto sia per la velocità e l'estensione delle grandezze dei valori che sono testabili. Ho usato set al posto di liste, perché ci vuole molto meno tempo, ho usato turni bit invece di divisione per due, e ho scelto intelligentemente un valore avvio iniziale molto più efficiente. A proposito, ho fatto il numero di test raccomandato di prova di Alex Martelli, così come un paio di numeri di molti ordini di grandezza più grandi, come ad esempio: stampati i seguenti risultati: E lo ha fatto presente in 0,33 secondi. A mio parere, il mio algoritmo funziona lo stesso Alex Martelli di, con tutti i vantaggi della stessa, ma ha il vantaggio respingimenti semplice-test ad alta efficienza che fanno risparmiare un sacco di tempo, per non parlare della riduzione delle dimensioni di numeri di prova per potenze di 4, che migliora la velocità, l'efficienza, l'accuratezza e la dimensione dei numeri che sono testabili. Probabilmente vero soprattutto nelle implementazioni non Python. Circa il 99% di tutti gli interi vengono respinte come non-Square prima estrazione radice babilonese è ancora implementata, e in 2/3 del tempo necessario babilonese di respingere l'intero. E anche se questi test dont accelerare il processo che in modo significativo, la riduzione in tutti i numeri di prova per una strana dividendo fuori tutti i poteri di 4 davvero accelera il test di Babilonia. Ho fatto un test di confronto tempo. Ho provato tutti i numeri interi da 1 a 10 milioni di dollari in successione. Utilizzando solo il metodo di Babilonia da solo (con la mia ipotesi iniziale appositamente studiata) ha preso la mia superficie 3 una media di 165 secondi (con il 100% di precisione). Usando solo i test logici nel mio algoritmo (esclusa babilonese), ci sono voluti 127 secondi, ha respinto il 99% di tutti gli interi come non quadrati senza rifiutare erroneamente alcun quadrati perfetti. Di quei numeri interi che hanno superato, solo il 3% erano quadrati perfetti (una densità molto più alta). Utilizzando l'intero algoritmo di cui sopra che impiega entrambi i test logici e l'estrazione radice babilonese, abbiamo precisione del 100%, e il completamento di prova in soli 14 secondi. I primi 100 milioni di numeri interi dura circa 2 minuti e 45 secondi di prova. EDIT: Sono stato in grado di abbattere il tempo ulteriormente. Ora posso testare i numeri interi da 0 a 100 milioni in 1 minuto 40 secondi. Un sacco di tempo è sprecato il controllo del tipo di dati e la positività. Eliminare i primi due assegni e ho tagliato l'esperimento giù da un minuto. Si deve presumere che l'utente è abbastanza intelligente per sapere che negativi e carri non sono quadrati perfetti. x=1000199838770766116385386300483414671297203029840113913153824086810909168246772838680374612768821282446322068401699727842499994541063844393713189701844134801239504543830737724442006577672181059194558045164589783791764790043104263404683317158624270845302200548606715007310112016456397357027095564872551184907513312382763025454118825703090010401842892088063527451562032322039937924274426211671442740679624285180817682659081248396873230975882215128049713559849427311798959652681930663843994067353808298002406164092996533923220683447265882968239141724624870704231013642255563984374257471112743917655991279898690480703935007493906644744151022265929975993911186879561257100479593516979735117799410600147341193819147290056586421994333004992422258618475766549646258761885662783430625 ** 2
for i in range(x, x+2):
print(i, isSquare(i))
1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890625 True
1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890626 False
Questo può essere risolto utilizzando modulo decimal ottenere precisione arbitraria radici quadrate e facile verifica la presenza di "precisione":
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]
Per la dimostrazione con i valori veramente enormi:
# 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
Se si aumenta la dimensione del valore in fase di test, questo alla fine diventa piuttosto lento (prende vicino ad un secondo per una piazza 200.000 bit), ma per i numeri più moderati (diciamo, 20.000 bit), è ancora più veloce di un essere umano avrebbe notato per i valori individuali (~ 33 ms sulla mia macchina). Ma dal momento che la velocità non era la vostra preoccupazione principale, questo è un buon modo per farlo con le librerie standard di Python.
Naturalmente, sarebbe molto più veloce da usare gmpy2 solo gmpy2.mpz(x).is_square() prova e, ma se pacchetti di terze parti non sono la vostra passione, le opere di cui sopra abbastanza bene.
Ho appena pubblicato una leggera variazione su alcuni degli esempi di cui sopra su un altro thread ( Trovare quadrati perfetti ) e ho pensato di includere una leggera variazione di quello che ho postato qui c'è (utilizzando nsqrt come una variabile temporanea), in caso è di interesse / uso:
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)
È corretto per un grande non quadrata come 152415789666209426002111556165263283035677490.
La mia risposta è:
def is_square(x):
return x**.5 % 1 == 0
Si fa fondamentalmente una radice quadrata, poi con modulo da 1 a striscia la parte intera e se il risultato è 0 ritorno True altrimenti restituisce False. In questo caso, x può essere un numero considerevole, ma non così grande come il numero massimo float che pitone può gestire: 1.7976931348623157e + 308
È corretto per un grande non quadrata come 152415789666209426002111556165263283035677490.
Questo è il mio metodo:
def is_square(n) -> bool:
return int(n**0.5)**2 == int(n)
Prendere radice quadrata del numero. Convertire a intero. Prendere la piazza. Se i numeri sono uguali, allora è un quadrato perfetto altrimenti no.
Non è corretto per una grande piazza come 152415789666209426002111556165263283035677489.
Si potrebbe binario di ricerca per la radice quadrata arrotondata. Quadrare il risultato per vedere se corrisponde al valore originale.
Sei probabilmente meglio con FogleBirds rispondere - anche se state attenti, come aritmetica in virgola mobile è approssimativo, che può gettare questo approccio off. in linea di principio si potrebbe ottenere un falso positivo da un grande numero intero che è uno più di un quadrato perfetto, per esempio, a causa di precisione perso.
- Decidere per quanto tempo il numero sarà.
- prendere una delta 0.000000000000.......000001
- vedere se l' (sqrt(x))^2 - x è maggiore / uguale /minore di delta e decidere in base al delta di errore.
Questa risposta non riguarda la tua domanda dichiarato, ma a una domanda implicita che vedo nel codice che hai postato, vale a dire, "come verificare se qualcosa è un intero?"
La prima risposta si ottiene in generale a questa domanda è "No!" Ed è vero che in Python, typechecking di solito non è la cosa giusta da fare.
Per quelle rare eccezioni, però, invece di cercare un punto decimale nella rappresentazione stringa del numero, la cosa da fare è utilizzare il isinstance funzione:
>>> isinstance(5,int)
True
>>> isinstance(5.0,int)
False
Naturalmente questo vale per la variabile piuttosto che un valore. Se avessi voluto determinare se il Valore è un numero intero, mi piacerebbe fare questo:
>>> x=5.0
>>> round(x) == x
True
Ma, come tutti gli altri ha coperto in dettaglio, ci sono problemi in virgola mobile da considerare nella maggior parte degli esempi non giocattolo di questo genere di cose.
Se si desidera ciclo in un intervallo e fare qualcosa per ogni numero che non è un quadrato perfetto, si potrebbe fare qualcosa di simile:
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
Se si vuole fare qualcosa per ogni numero che è un quadrato perfetto, il generatore è ancora più facile:
(n * n for n in range(upper))
Credo che questo funziona ed è molto semplice:
import math
def is_square(num):
sqrt = math.sqrt(num)
return sqrt == int(sqrt)
È corretto per un grande non quadrata come 152415789666209426002111556165263283035677490.
import math
def is_square(n):
sqrt = math.sqrt(n)
return sqrt == int(sqrt)
Non riesce per un grande non-piazza, come 152415789666209426002111556165263283035677490.
