Square Root (Integer)

Q: Qual è la complessità temporale della radice quadrata tramite ricerca binaria?

Tempo O(log x) e spazio O(1) . A ogni passaggio l’intervallo dei candidati si dimezza, quindi x = 2^31 - 1 richiede 31 passaggi. Contare a partire da 0 richiede O(√x) passaggi, 46340 per lo stesso x : qui va bene, ma il numero cresce rapidamente con gli input a 64 bit.

Q: In che modo il metodo di Newton calcola una radice quadrata intera?

Inizia con r = x . Mentre r × r > x , sostituisci r con (r + x / r) / 2 usando la divisione intera. Ogni passaggio avvicina r alla radice senza superarla, e il ciclo si ferma al valore intero inferiore della radice quadrata. Per x = 2^31 - 1 servono 19 passaggi, e il numero di cifre corrette all’incirca raddoppia a ogni passaggio quando il valore si avvicina.

FacileRicerca binaria Matematica e simulazione

+10

La tua funzione riceve un intero non negativo x e restituisce la sua radice quadrata intera: il più grande intero r tale che r × r ≤ x. In altre parole, la radice quadrata arrotondata per difetto: se un numero non è un quadrato perfetto, si ottiene la radice del quadrato perfetto immediatamente inferiore. Calcolala tu, senza usare una funzione integrata per la radice quadrata o una funzione di potenza.

Funzione

mySqrt(x: integer) → integer

xinteger: l'intero non negativo di cui calcolare la radice quadrata
Restituisceinteger: la radice quadrata di x arrotondata per difetto a un numero intero

Vincoli

0 ≤ x ≤ 2³¹ - 1
Non chiamare una funzione integrata per la radice quadrata, la potenza o l’esponenziale.

Esempi

Input: x = 17
Output: 4
Spiegazione: 4 × 4 = 16 è al massimo 17, ma 5 × 5 = 25 è maggiore, quindi la radice di 17 si arrotonda per difetto a 4.

Input: x = 49
Output: 7
Spiegazione: 49 è un quadrato perfetto, 7 × 7 = 49, quindi non viene arrotondato nulla e la risposta è esattamente 7.

+17 test nascosti all’invio

Per approfondire

Come troveresti invece la radice cubica intera, il più grande r tale che r × r × r ≤ x, se x potesse anche essere negativo?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Contare a partire da 0 finché il quadrato successivo non supera x dà la risposta corretta, ma richiede un passaggio per ogni unità della radice, circa 46000 passaggi vicino al limite superiore dell’intervallo. I quadrati 0, 1, 4, 9, 16 e così via sono ordinati, quindi puoi cercare con la ricerca binaria l’ultimo candidato il cui quadrato è al massimo x e terminare in circa 31 passaggi. In entrambi i casi, la trappola è l’overflow: il quadrato di un candidato non sempre entra in 32 bit.

Conta a partire da zero

Intuizione

La radice è il più grande r tale che r × r ≤ x. Parti da r = 0, il cui quadrato è sempre minore o uguale a x, e continua a incrementare di uno, passando a r + 1, finché il quadrato del numero successivo è ancora minore o uguale a x. Il ciclo si ferma al primo r il cui successore è troppo grande: è proprio la radice. Per x = 17 i quadrati 1, 4, 9 e 16 sono minori o uguali a x, mentre 25 non lo è, quindi il ciclo si ferma a 4.

Il ciclo viene eseguito una volta per ogni unità del risultato. Qui il risultato massimo è 46340, quindi al massimo 46340 passaggi, che si completano rapidamente. Il costo è però O(√x) e cresce con l’input: un x a 64 bit potrebbe richiedere circa 3 × 10^9 passaggi.

Fai attenzione all’ultimo controllo. Per x = 2^31 - 1 il ciclo calcola il quadrato di 46341 per verificare che sia troppo grande, ma 46341 × 46341 = 2147488281 non è rappresentabile in un intero a 32 bit. Calcola il quadrato usando 64 bit.

Algoritmo

Imposta root = 0.
Mentre (root + 1) × (root + 1) ≤ x, incrementa root di 1.
Restituisci root.

def mySqrt(x):
    root = 0
    while (root + 1) * (root + 1) <= x:
        root += 1
    return root

Ricerca binaria sulla risposta

Intuizione

Metti in fila i candidati 0, 1, 2, fino a x, e poni a ciascuno la stessa domanda: il suo quadrato è al massimo x? Le risposte sono sì, sì, sì, poi no per ogni candidato dopo la radice, perché i quadrati aumentano soltanto. La radice è l’ultimo sì. Una sequenza ordinata di sì seguiti da no è proprio ciò per cui è progettata la ricerca binaria.

Mantieni l’intervallo da lo a hi dei candidati non ancora decisi, iniziando da 0 a x, e una variabile best per il più grande sì trovato finora. Verifica il valore centrale mid. Se mid × mid ≤ x, la radice è mid o maggiore: salvalo in best e sposta lo a mid + 1. Altrimenti la radice è minore: sposta hi a mid - 1. Quando l’intervallo è vuoto, best è la radice.

Seguiamo x = 17. L’intervallo da 0 a 17 verifica 8 (64, troppo grande), poi da 0 a 7 verifica 3 (9, va bene, best = 3), poi da 4 a 7 verifica 5 (25, troppo grande), poi da 4 a 4 verifica 4 (16, va bene, best = 4). L’intervallo è vuoto e la risposta è 4. A ogni passaggio l’intervallo si dimezza, quindi x = 2^31 - 1 richiede 31 passaggi. Esegui il quadrato usando 64 bit: il primo mid in questo caso è 1073741823.

Algoritmo

Imposta lo = 0, hi = x e best = 0.
Mentre lo ≤ hi, calcola mid, il punto medio dell’intervallo.
Se mid × mid ≤ x (su 64 bit), imposta best = mid e lo = mid + 1.
Altrimenti imposta hi = mid - 1.
Restituisci best.

def mySqrt(x):
    lo, hi = 0, x
    best = 0  # largest candidate seen so far whose square fits
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= x:
            best = mid  # mid fits, so try a larger root
            lo = mid + 1
        else:
            hi = mid - 1  # mid is too big
    return best

Trappole e casi limite

La ricerca in sé è breve; i bug si nascondono nell’aritmetica e nei casi limite.

Elevare al quadrato usando 32 bit. Per x = 2147483647, il primo candidato centrale è 1073741823 e il suo quadrato è circa 1.15 × 10^18. In un int a 32 bit, il valore va in overflow e diventa errato; può persino sembrare abbastanza piccolo da rientrare nei limiti. Esegui la moltiplicazione a 64 bit oppure confronta m ≤ x / m.
Elevare al quadrato il candidato successivo usando 32 bit nel ciclo di conteggio. La radice di 2^31 - 1 è 46340 e l’ultimo controllo del ciclo eleva al quadrato 46341, ottenendo 2147488281, un valore superiore al limite a 32 bit.
Portare l’intervallo oltre i 32 bit. Per il valore massimo di x, il limite esclusivo hi = x + 1 è 2147483648, un valore oltre il limite a 32 bit. Con il limite inclusivo hi = x, lo + hi raggiunge esattamente 2147483647 al primo passaggio, quindi rientra nei limiti, ma senza margine. Usa indici a 64 bit oppure lo + (hi - lo) / 2.
Restituire l’ultimo mid esaminato invece dell’ultimo che rientrava nei limiti. Per x = 17, la ricerca termina dopo aver esaminato 5, che è troppo grande; la risposta è il 4 memorizzato.
Rendere errati i casi semplici. Una ricerca che inizia da lo = 1 non considera x = 0, e il controllo tramite divisione m ≤ x / m divide per zero quando m = 0. Verifica separatamente 0 e 1.

Domande frequenti4

Come si trova una radice quadrata senza una funzione integrata?

Per calcolare la radice quadrata intera, cerca la risposta con la ricerca binaria. I candidati da 0 a x si dividono in una sequenza i cui quadrati sono minori o uguali a x e una sequenza i cui quadrati sono maggiori; la ricerca binaria individua l’ultimo candidato della prima sequenza. L’altro metodo comune è il metodo di Newton: affina una stima r con (r + x / r) / 2 finché il quadrato non rientra nell’intervallo.

Qual è la complessità temporale della radice quadrata tramite ricerca binaria?

Tempo O(log x) e spazio O(1). A ogni passaggio l’intervallo dei candidati si dimezza, quindi x = 2^31 - 1 richiede 31 passaggi. Contare a partire da 0 richiede O(√x) passaggi, 46340 per lo stesso x: qui va bene, ma il numero cresce rapidamente con gli input a 64 bit.

In che modo il metodo di Newton calcola una radice quadrata intera?

Inizia con r = x. Mentre r × r > x, sostituisci r con (r + x / r) / 2 usando la divisione intera. Ogni passaggio avvicina r alla radice senza superarla, e il ciclo si ferma al valore intero inferiore della radice quadrata. Per x = 2^31 - 1 servono 19 passaggi, e il numero di cifre corrette all’incirca raddoppia a ogni passaggio quando il valore si avvicina.

Perché la soluzione ha bisogno di interi a 64 bit quando la risposta rientra in 32 bit?

La risposta è al massimo 46340, ma i candidati che testi non lo sono. La ricerca binaria tra 0 e x prova per prima cosa un candidato vicino a 10^9, il cui quadrato è vicino a 10^18, ben oltre il limite a 32 bit di circa 2.1 × 10^9. Elevare al quadrato usando 64 bit mantiene esatto il confronto. Confrontare m ≤ x / m evita del tutto il prodotto grande.

Python

def mySqrt(x):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Input

x = 17

Atteso