Gibt es eine Reihe von ganzen Zahlen mindestens ein perfektes Quadrat enthalten?

Question

Bei zwei ganzen Zahlen a und b, ist es eine effiziente Art und Weise zu testen, ob es eine andere ganze Zahl n so dass a ≤ n2 < b?

Ich brauche nicht n zu wissen, ob nur mindestens eine solche n existieren oder nicht, so dass ich zu hoffen Vermeiden Berechnung von Quadratwurzeln von irgendwelchen Zahlen im Intervall.

Obwohl testen, ob eine individuelle integer ist ein perfektes Quadrat ist schneller als die Quadratwurzel Berechnung der Bereich groß sein kann und ich würde auch im Bereich für jede Zahl zu vermeiden, bevorzuge diesen Test durchführen.

Beispiele:

• intervalContainsSquare(2, 3) => false
• intervalContainsSquare(5, 9) => false (Anmerkung: 9 außerhalb dieses Intervalls ist)
• intervalContainsSquare(9, 9) => false (dieses Intervall ist leer)
• intervalContainsSquare(4, 9) => true (4 innerhalb dieses Intervalls ist)
• intervalContainsSquare(5, 16) => true (9 innerhalb dieses Intervalls ist)
• intervalContainsSquare(1, 10) => true (1, 4 und 9 sind alle innerhalb dieses Intervalls)

Answer 1

Computing, ob eine Zahl ein Quadrat ist nicht wirklich schneller als in harten Fällen seine Quadratwurzel Berechnung, soweit ich weiß. Was stimmt, ist, dass Sie eine precomputation tun können zu wissen, dass es nicht ein Quadrat ist, die Sie im Durchschnitt sparen könnte.

Das gleiche gilt für dieses Problem können Sie eine Vorausberechnungs tun, dass sqrt (b) -sqrt zu bestimmen (a)> = 1, was dann bedeutet, dass a und b weit genug voneinander entfernt sind, dass es einen Platz zwischen ihnen sein. Mit etwas Algebra ist diese Ungleichheit der Bedingung äquivalent, dass (ba-1) ^ 2> = 4 * a, oder wenn Sie es in einer symmetrischen Form wollen, dass (ab) ^ 2 + 1> = 2 * (a + b). Also das precomputation kann ohne Quadratwurzeln getan wird, nur mit einem Integer-Produkt und einigen Additionen und Subtraktionen.

Wenn a und b fast genau gleich sind, dann können Sie immer noch den Trick als precomputation bei niederwertigen Binärstellen der Suche verwenden zu wissen, dass es nicht ein Platz zwischen ihnen. Aber sie haben so nah beieinander sein, dass diese precomputation nicht wert sein könnte es.

Wenn diese Vorberechnung nicht schlüssig sind, dann kann ich mir nichts anderes als die aller anderen Lösung, a <= ceil (sqrt (a)) ^ 2

---

Da es war eine Frage, die Algebra Recht zu tun:

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

---

Auch: Im Allgemeinen, wenn eine große Zahl ist, würden Sie berechnen sqrt (a) mit dem Newton-Verfahren, oder mit einer Lookup-Tabelle durch ein paar Newtons Verfahrensschritte folgen. Es ist schneller im Prinzip berechnet ceil (sqrt (a)) als sqrt (a), weil die Gleitkomma-Arithmetik zu Integer-Arithmetik vereinfacht werden kann, und weil man nicht so viele Newtons Verfahrensschritte zu hohe Präzision benötigte, dass Sie gehen weg zu werfen gerade. Aber in der Praxis kann eine numerische Library-Funktion viel schneller sein, wenn es Quadratwurzeln in Mikrocode implementiert verwendet. Wenn Sie aus irgendeinem Grunde nicht, dass das Mikro müssen Ihnen helfen, dann könnte es wert, es zu hand Code ceil (sqrt (a)) sein. Vielleicht wäre der interessanteste Fall, wenn a und b ganze Zahlen sind unbegrenzt (wie tausend Stellen). Aber für gewöhnliche große Zahlen auf einem gewöhnlichen nicht veralteten Computer, Sie können nicht die FPU schlagen.

Answer 2

Erhalten Sie die Quadratwurzel aus der geringeren Zahl. Wenn dies eine ganze Zahl ist dann sind Sie fertig. Ansonsten Runde und Platz der Nummer. Wenn dieser weniger als b, dann ist es wahr.

Sie benötigen nur eine Quadratwurzel diese Art und Weise zu berechnen.

Um ein Problem zu vermeiden, wenn a gleich b, sollten Sie, dass zuerst überprüfen. Da dieser Fall ist immer falsch.

Answer 3

Wenn Sie akzeptieren zwei Quadratwurzeln berechnen, wegen seiner Monotonie Sie diese Ungleichheit haben, die zu Ihrem Ausgang einer äquivalent ist:

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

Wenn also floor(sqrt(a)) != floor(sqrt(b)), floor(sqrt(b)) - 1 garantiert eine solche n sein.

Answer 4

1. erhält die Quadratwurzel aus der geringeren Anzahl und um es nach oben
2. erhält die Quadratwurzel aus der höheren Zahl und um sie herum nach unten
3. , wenn 1 niedriger oder gleich 2, wird es ein perfektes Quadrat sein

Answer 5

Hier finden Sie den integralen Bestandteil der sqrt (a) und sqrt (b), sagt sa und sb.

Wenn sa ² = a, dann Ausgang ja.

Wenn sb ² = b und sa = sb-1, dann Ausgabe Nr.

Wenn sa

Else Ausgabe Nr.

Sie können die oben optimieren die Berechnung von sqrt loszuwerden (b) (ähnlich JDunkerly Antwort).

Oder wollen Sie Quadratwurzeln a und b vermeiden Berechnung?

---

können Sie vermeiden Quadratwurzeln Berechnung vollständig durch ein ähnliches Verfahren wie binäre Suche verwendet wird.

Sie mit einer Vermutung für n starten, n = 1 und Compute n ²

Überlegen Sie, ob a <= n

Wenn n

Dies wird O (logb) Zeit.

Answer 6

Neben JDunkerley der schönen Lösung (+1), könnte es eine mögliche Verbesserung sein, dass Bedarf getestet und verwendet wird integer Quadratwurzeln zu berechnen integer Quadratwurzeln

Answer 7

Warum hoffen Sie ganz Quadratwurzeln zu vermeiden? Noch bevor Sie diese zu lösen, um die effizienteste Art und Weise zu erhalten, haben Sie Methoden für nur 2 Quadratwurzeln dieses Anruf gesehen. Das ist in O (1) Zeit getan, so scheint es mir, dass jede Verbesserung, die Sie zu machen hoffen könnten, wäre mehr Zeit, um darüber nachzudenken eingenommen hat, als es jemals sparen Sie Zeit zu berechnen. Bin ich falsch?

Answer 8

Eine Möglichkeit ist die Newton-Methode zu verwenden, um die integer Quadratwurzel für b zu finden. Dann können Sie überprüfen, ob diese Zahl in den Bereich fällt. Ich bezweifle, dass es schneller ist, als nur die Quadratwurzel-Funktion aufrufen, aber es ist sicherlich interessanter:

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