Esiste una serie di interi contiene almeno un quadrato perfetto?

https://stackoverflow.com/questions/3140562

01-10-2019
|

Domanda

Dati due interi a e b, c'è un modo efficiente per verificare se v'è un altro n intero tale che a ≤ n² < b?

Non ho bisogno di sapere n, solo se esiste o no almeno una di queste n, quindi spero di Evitare di calcolo radici quadrate di tutti i numeri nell'intervallo.

Anche se se un individuo intero è un quadrato perfetto è più veloce di calcolare la radice quadrata , la gamma può essere grande e vorrei anche preferire di evitare l'esecuzione di questo test per ogni numero all'interno della gamma.

Esempi:

intervalContainsSquare(2, 3) => false
intervalContainsSquare(5, 9) => false (nota: 9 è fuori di questo intervallo)
intervalContainsSquare(9, 9) => false (questo intervallo è vuoto)
intervalContainsSquare(4, 9) => true (4 è all'interno di questo intervallo)
intervalContainsSquare(5, 16) => true (9 è all'interno di questo intervallo)
intervalContainsSquare(1, 10) => true (1, 4 e 9 sono tutti all'interno di questo intervallo)

Soluzione

Computing se un numero è una piazza non è davvero più veloce di calcolare la sua radice quadrata in casi difficili, per quanto ne so. Ciò che è vero è che si può fare un precomputation per sapere che non è una piazza, che si potrebbe risparmiare tempo in media.

Anche per questo problema, si può fare un precomputation di determinare che -sqrt sqrt (b) (a)> = 1, che poi significa che a e b sono abbastanza lontani che ci deve essere un quadrato tra di loro. Con un po 'di algebra, questa disuguaglianza è equivalente alla condizione che (ba-1) ^ 2> = 4 * a, o se si vuole che in una forma più simmetrica, che (ab) ^ 2 + 1> = 2 * (un + b). Quindi questo precomputation può essere fatto senza radici quadrate, con un solo prodotto intero e alcune aggiunte e sottrazioni.

Se a e b sono quasi esattamente la stessa, allora è ancora possibile utilizzare il trucco di guardare ordine basso cifre binarie come precomputation sapere che non c'è una piazza tra di loro. Ma devono essere così vicini che questo precomputation potrebbe non valerne la pena.

Se queste precomputations sono inconcludenti, quindi non posso pensare a qualcosa di diverso da tutti gli altri la soluzione, un <= ceil (sqrt (a)) ^ 2

Dal momento che non era una questione di fare la giusta algebra:

sqrt(b)-sqrt(a) >= 1
sqrt(b) >= 1+sqrt(a)
b >= 1+2*sqrt(a)+a
b-a-1 >= 2*sqrt(a)
(b-a-1)^2 >= 4*a

Inoltre: Generalmente quando a è un numero elevato, si potrebbe calcolare sqrt (a) con il metodo di Newton, o con una tabella di ricerca seguita da fasi del metodo alcuni di Newton. E 'più veloce in linea di principio per calcolare ceil (sqrt (a)) che sqrt (a), perché l'aritmetica in virgola mobile può essere semplificata per intero aritmetica, e perché non hanno bisogno di fasi del metodo di molti Newton inchiodare alta precisione che si sta solo andando a buttare via. Ma in pratica, una funzione di libreria numerica può essere molto più veloce se si utilizza radici quadrate realizzate in microcodice. Se per qualsiasi motivo non è necessario che il microcodice per aiutarvi, allora potrebbe essere la pena di mano il codice ceil (sqrt (a)). Forse il caso più interessante sarebbe se a e b sono numeri interi illimitati (come, mille cifre). Ma per gli interi comuni di dimensioni in un computer non obsoleto ordinario, non si può battere la FPU.

Altri suggerimenti

Prendi la radice quadrata del numero più basso. Se questo è un numero intero, allora si è fatto. Altrimenti up rotondo e quadrato il numero. Se questo è minore di b, allora è vero.

Hai solo bisogno di calcolare una radice quadrata in questo modo.

Al fine di evitare un problema di quando A è uguale a B, si dovrebbe verificare che il primo. Poiché questo caso è sempre false.

Se si accetta il calcolo due radici quadrate, a causa della sua monotonia si dispone di questa diseguaglianza che equivale alla vostra partenza una:

sqrt(a) <= n < sqrt(b)

quindi, se floor(sqrt(a)) != floor(sqrt(b)), floor(sqrt(b)) - 1 è garantito per essere tale n.

ottenere la radice quadrata del numero inferiore e intorno ad esso fino
ottenere la radice quadrata del numero più alto e rotondo giù
se 1 è inferiore o uguale a 2, ci sarà un quadrato perfetto

Trova la parte integrante della sqrt (a) e sqrt (b), dire SA e SB.

Se sa ² = a, allora sì uscita.

Se sb ² = b e sa = sb-1, quindi l'uscita no.

Se sa

uscita Else no.

È possibile ottimizzare il sopra per sbarazzarsi di calcolo di sqrt (b) (simile alla risposta di JDunkerly).

O volevi evitare calcolo radici quadrate di A e B troppo?

Si può evitare di calcolo completamente radici quadrate utilizzando un metodo simile a ricerca binaria.

Si inizia con una congettura per n, n = 1 e calcolare N ²

Si consideri se un <= n

Se n

Questa sarà O (logb) tempo.

Oltre alla bella soluzione di JDunkerley (+1), ci potrebbe essere un possibile miglioramento che deve essere testato e usi intero radici quadrate per calcolare radici quadrate intero

Perché speri di evitare del tutto le radici quadrate? Anche prima di arrivare al il modo più efficace di risolvere questo, avete visto i metodi che invito a solo 2 le radici quadrate. Questo è fatto in O (1) tempo, quindi mi sembra che qualsiasi miglioramento si poteva sperare di fare sarebbe voluto più tempo per pensare a quello che avrebbe mai risparmiare tempo di calcolo. Mi sbaglio?

Un modo è quello di utilizzare il metodo di Newton per trovare la intero radice quadrata per b. Quindi è possibile controllare se quel numero è compreso nell'intervallo. Dubito che è più veloce che semplicemente chiamando la funzione radice quadrata, ma è certamente più interessante:

int main( int argc, char* argv[] )
{
    int a, b;
    double xk=0, xk1;
    int root;
    int iter=0;
    a = atoi( argv[1] );
    b = atoi( argv[2] );

    xk1 = b / 32 + 1;  // +1 to ensure > 0
    xk1 = b;
    while( fabs( xk1 - xk ) >= .5 ) {
        xk = xk1;
        xk1 = ( xk + b / xk ) / 2.;
        printf( "%d) xk = %f\n", ++iter, xk1 );
    }

    root = (int)xk1;

    // If b is a perfect square, then this finds that root, so it also
    // needs to check if (n-1)^2 falls in the range.
    // And this does a lot more multiplications than it needs
    if ( root*root >= a && root*root < b ||
         (root-1)*(root-1) >= a && (root-1)*(root-1) < b )
        printf( "Contains perfect square\n" );
    else
        printf( "Does not contain perfect square\n" );

    return 1;
}

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow