Problem:

Schreiben Sie in der von Ihnen gewählten Sprache die kürzeste Funktion, die den Grund der Quadratwurzel einer 64-Bit-Ganzzahl ohne Vorzeichen zurückgibt.

Testfälle:

Ihre Funktion muss für alle Eingaben korrekt funktionieren. Die folgenden Beispiele veranschaulichen die Idee:

               INPUT ⟶ OUTPUT

                   0 ⟶  0
                   1 ⟶  1
                   2 ⟶  1
                   3 ⟶  1
                   4 ⟶  2
                   8 ⟶  2
                   9 ⟶  3
                  15 ⟶  3
                  16 ⟶  4
               65535 ⟶ 255
               65536 ⟶ 256
18446744073709551615 ⟶ 4294967295

Regeln:

1. Sie können Ihre Funktion beliebig benennen. (Unbenannte, anonyme oder Lambda-Funktionen sind in Ordnung, sofern sie irgendwie aufrufbar sind.)
2. Die Anzahl der Zeichen ist das Wichtigste bei dieser Herausforderung, aber auch die Laufzeit ist wichtig. Ich bin sicher, Sie könnten iterativ nach der Antwort in O (√n) -Zeit mit einer sehr kleinen Zeichenanzahl suchen, aber die O (log (n)) -Zeit wäre wirklich besser (das heißt, wenn Sie einen Eingabewert von n annehmen würden). keine Bitlänge von n).
3. Möglicherweise möchten Sie die Funktion mit rein ganzzahliger und / oder boolescher Artithmetik implementieren. Wenn Sie jedoch wirklich Gleitkommaberechnungen verwenden möchten, ist dies in Ordnung, solange Sie keine Bibliotheksfunktionen aufrufen. Einfach return (n>0)?(uint32_t)sqrtl(n):-1;in C zu sagen ist also tabu, obwohl es das richtige Ergebnis liefern würde. Wenn Sie mit Fließkommaarithmetik, können Sie verwenden *, /, +, -, und Potenzierung (zB **oder ^wenn es eine eingebauter Operator in der Sprache Ihrer Wahl, sondern nur Potenzierung der Kräfte nicht weniger als 1 ). Diese Einschränkung soll das "Betrügen" verhindern, indem Sie sqrt()eine Variante aufrufen oder einen Wert auf die halbe Potenz erhöhen.
4. Wenn Sie Gleitkommaoperationen verwenden (siehe Nr. 3), ist es nicht erforderlich, dass der Rückgabetyp eine Ganzzahl ist. Nur, dass der Rückgabewert eine Ganzzahl ist, z. B. floor (sqrt (n)), und in der Lage ist, jeden vorzeichenlosen 32-Bit-Wert zu speichern.
5. Wenn Sie C / C ++ verwenden, können Sie davon ausgehen, dass 64-Bit- und 32-Bit-Integer-Typen ohne Vorzeichen vorhanden sind, z. B. uint64_tund uint32_twie in definiert stdint.h. Stellen Sie andernfalls sicher, dass Ihr Integer-Typ 64-Bit-Integer ohne Vorzeichen aufnehmen kann.
6. Wenn Ihre Sprache keine 64-Bit-Ganzzahlen unterstützt (z. B. hat Brainfuck anscheinend nur 8-Bit-Ganzzahlenunterstützung), tun Sie Ihr Bestes, und geben Sie die Einschränkung in Ihrem Antworttitel an. Das heißt, wenn Sie herausfinden können, wie Sie eine 64-Bit-Ganzzahl codieren und die Quadratwurzel mit einer primitiven 8-Bit-Arithmetik korrekt erhalten, dann haben Sie mehr Power!
7. Viel Spaß und kreativ werden!

CJam, 17 (oder 10) Bytes

{_1.5#\/i}

Probieren Sie es online aus, indem Sie die Testfälle überprüfen:

[0 1 2 3 4 8 9 15 16 65535 65536 18446744073709551615]{_1.5#\/i}%N*

Der letzte Testfall wird aufgrund von Rundungsproblemen nicht bestanden, aber da 18446744073709551615es in CJam keine Ganzzahl gibt (es ist eine große Ganzzahl ), sind wir immer noch gut, oder?

Wenn nicht, korrigiert der folgende (und etwas längere) Code diese Fehler:

{__1.5#\/i_2#@>-}

Nicht mehr die kürzeste Lösung, aber schnell .

Wie es funktioniert

__    " Duplicate the integer twice. ";
1.5#  " Raise to power 1.5. Note that, since 1.5 > 1, this doesn't break the rules. ";
\     " Swap the result with the original integer. ";
/     " Divide. ";
i     " Cast to integer. ";
_2#   " Push square of a copy. ";
@     " Rotate the orginal integer on top of the stack. ";
>-    " If the square root has been rounded up, subtract 1. ";

Haskell, 28 26

Ich glaube, dass dies der kürzeste Eintrag aus einer Sprache ist, die nicht zum Golfen gedacht ist.

s a=[x-1|x<-[0..],x*x>a]!!0

Es benennt eine Funktion smit einem Parameter aund gibt eins minus der ersten Zahl zurück, deren Quadrat größer als ist a. Läuft unglaublich langsam (O (sqrt n), vielleicht?).

Golfscript, 17 Zeichen

{).,{.*1$<},,\;(}

Ich konnte meine Funktion so benennen, wie ich wollte, aber ich beschloss, sie überhaupt nicht zu benennen. Fügen Sie zwei Zeichen hinzu, um es zu benennen, fügen Sie drei hinzu, um es zu benennen, und belassen Sie es nicht auf dem Stapel. Subtrahieren Sie ein Zeichen, wenn ein vollständiges Programm in Ordnung ist.

Diese Abscheulichkeit läuft nicht in logaritmischer Zeit im Wert der Eingabe, nicht in O (sqrt n) Zeit, es dauert eine lange lineare Zeit, um das Ergebnis zu erzeugen. Es braucht auch so viel Platz. Absolut schrecklich. Aber ... das ist Code-Golf.

Der Algorithmus ist:

n => [0..n].filter(x => x*x < n+1).length - 1

Pyth , 14 Zeichen

DsbR;fgb*TTL'b

Stellt eine benannte Funktion s bereit, die die Quadratwurzel berechnet, indem sie die Liste von 0 bis n filtert, damit das Quadrat größer als die Eingabe ist, und dann die letzte solche Zahl ausgibt. Verwendet keine Exponentiation oder Floats.

Dsb       def s(b):
R;        return last element of
f         filter(lambda T:
gb*TT                     b>=T*T,
L'b                       range(b+1))

Beispielverwendung:

python3 pyth.py <<< "DsbR;fgb*TTL'b       \msd[0 1 2 3 4 8 9 15 16 65535 65536"
[0, 1, 1, 1, 2, 2, 3, 3, 4, 255, 256]

Retina (nicht konkurrierend - Sprache ist neuer als die Herausforderung), 43

Bei der Arbeit an dieser Antwort ist mir aufgefallen, dass eine ähnliche Methode zum Berechnen ganzzahliger Quadratwurzeln mit der Netzhaut verwendet werden kann:

.+
$*
^
1:
+`(1+):(11\1)
1 $2:
1+:$|:1+

1+

Dies beruht auf der Tatsache, dass perfekte Quadrate wie 1+3+5+7+...folgt ausgedrückt werden können: Die Anzahl der Terme in diesem Ausdruck ist die Quadratwurzel.

Probieren Sie es online aus. (Erste Zeile hinzugefügt, damit mehrere Testfälle ausgeführt werden können.)

Offensichtlich funktioniert dies aufgrund der Umwandlung von Dezimalstellen in unäre Werte nur für relativ kleine Eingaben.

Perl, 133 Zeichen

Bei weitem nicht die kürzeste, verwendet jedoch einen ziffernweisen Algorithmus zur Verarbeitung von Eingaben beliebiger Größe und wird in O-Zeit (log n) ausgeführt. Konvertiert frei zwischen Zahlen als Zeichenfolgen und Zahlen als Zahlen. Da das größtmögliche Produkt die bisherige Wurzel mit dem Quadrat einer einzelnen Ziffer ist, sollte es in der Lage sein, die Quadratwurzel von etwa 120-Bit-Zahlen auf einem 64-Bit-System zu bilden.

sub{($_)=@_;$_="0$_"if(length)%2;$a=$r="";while(/(..)/g){
$a.=$1;$y=$d=0;$a<($z=$_*(20*$r+$_))or$y=$z,$d=$_ for 1..9;$r.=$d;$a-=$y}$r}

Dekomprimiert, das heißt:

sub {
  my ($n) = @_;
  $n = "0$n" if length($n) % 2; # Make an even number of digits
  my ($carry, $root);
  while ($n =~ /(..)/g) { # Take digits of $n two at a time
    $carry .= $1;         # Add them to the carry
    my ($product, $digit) = (0, 0);
    # Find the largest next digit that won't overflow, using the formula
    # (10x+y)^2 = 100x^2 + 20xy + y^2 or
    # (10x+y)^2 = 100x^2 + y(20x + y)
    for my $trial_digit (1..9) {
      my $trial_product = $trial_digit * (20 * $root + $trial_digit);
      if ($trial_product <= $carry) {
        ($product, $digit) = ($trial_product, $trial_digit);
      } 
    } 
    $root .= $digit;
    $carry -= $product;
  } 
  return $root;
}

Matlab (56) / Octave (55)

Es berechnet die Quadratwurzel mit einer Festpunktmethode. Es konvergiert in maximal 36 Schritten (für 2 ^ 64-1 als Argument) und prüft dann, ob es die niedrigere der 'möglichen' Ganzzahlwurzeln ist. Da es immer 36 Iterationen verwendet, hat es eine Laufzeit von O (1) = P

Als Argument wird uint64 angenommen.

Matlab:

function x=q(s)
x=1
for i = 1:36
    x = (x+s/x)/2
end
if x*x>s
    x=x-1
end

Oktave:

function x=q(s)
x=1
for i = 1:36
    x = (x+s/x)/2
end
if x*x>s
    x-=1
end

Ruby - 36 Zeichen

s=->n{g=n;g=(g+n/g)/2 while g*g>n;g}

Python (39)

f=lambda n,k=0:k*k>n and k-1or f(n,k+1)

Der natürliche rekursive Ansatz. Zählt mögliche Quadratwurzeln, bis ihr Quadrat zu hoch ist, und verringert sich dann um 1. Verwenden Sie Stackless Python, wenn Sie befürchten, die Stapeltiefe zu überschreiten.

Die and/orRedewendung entspricht dem ternären Operator as

f=lambda n,k=0:k-1 if k*k>n else f(n,k+1)

Edit: Ich kann stattdessen bekommen 25 Zeichen durch die Regel „Schöpfen Sie verwenden können *, /, +, -, und Potenzierung (zB **oder ^wenn es eine eingebauter Operator in der Sprache Ihrer Wahl, aber nur Potenzierung der Kräfte nicht weniger als 1). " (Edit: Anscheinend hat Dennis diesen Trick bereits gefunden und ausgenutzt.)

lambda n:n**1.5//max(n,1)

Ich verwende den Ganzzahlteilungsoperator //von Python 3, um abzurunden. Leider n=0gebe ich eine Menge Zeichen für den Fall aus , um keine Division durch 0 Fehler zu geben. Wenn es nicht so wäre, könnte ich 18 Zeichen machen

lambda n:n**1.5//n 

Die Regeln sahen auch nicht vor, dass die Funktion benannt werden muss (je nachdem, wie Sie "Sie können Ihre Funktion beliebig benennen" interpretieren), aber wenn ja, sind das zwei weitere Zeichen.

C99 (58 Zeichen)

Dies ist ein Beispiel für eine Antwort, die ich nicht für gut halte, obwohl sie aus Sicht des Code-Golfs für mich interessant ist, weil sie so pervers ist, und ich dachte nur, es würde Spaß machen, sie in die Mischung zu werfen:

Original: 64 Zeichen

uint64_t r(uint64_t n){uint64_t r=1;for(;n/r/r;r++);return r-1;}

Der Grund, warum dies schrecklich ist, ist, dass es eher in O (√n) als in O (log (n)) läuft. (Wobei n der Eingabewert ist.)

Bearbeiten: 63 Zeichen

Ändern r-1von --rund Anfügen an return:

uint64_t r(uint64_t n){uint64_t r=1;for(;n/r/r;r++);return--r;}

Bearbeiten: 62 Zeichen

Verschieben des Schleifeninkrements in den bedingten Teil der Schleife (Hinweis: Dieses Verhalten ist nicht garantiert, da die Reihenfolge der Operationen in Bezug auf den Operator vor dem Inkrementieren compilerspezifisch ist):

uint64_t r(uint64_t n){uint64_t r=0;for(;n/++r/r;);return--r;}

Bearbeiten: 60 Zeichen

Hinzufügen eines typedefzu verbergenden Elementsuint64_t (Gutschrift an den Technosaurus- Benutzer für diesen Vorschlag).

typedef uint64_t Z;Z r(Z n){Z r=0;for(;n/++r/r;);return--r;}

Bearbeiten: 58 Zeichen

Jetzt muss der zweite Parameter beim Aufruf der Funktion als 0 übergeben werden, z. B. r(n,0)statt nur r(n). Ok, für mein ganzes Leben kann ich jetzt nicht mehr sehen, wie ich das weiter komprimieren kann ... irgendjemand?

typedef uint64_t Z;Z r(Z n,Z r){for(;n/++r/r;);return--r;}

Golfscript - 14 Zeichen

{.,\{\.*<}+?(}

Suchen Sie die kleinste Zahl, die ikleiner ist als die Eingabe, nfür die n < i*i. Rückkehri - 1 .

Dh [0..n-1].first(i => n < i*i) - 1

Erklärung für diejenigen, die Golfscript nicht kennen, für einen Beispielaufruf mit Eingabe 5:

.        //Duplicate input.  Stack: 5 5
,        //Get array less than top of stack.  Stack: 5 [0 1 2 3 4]
\        //Switch top two elements of stack.  Stack: [0 1 2 3 4] 5
{\.*<}+  //Create a block (to be explained), and prepend the top of the stack.  
         //Stack: [0 1 2 3 4]{5\.*<}
?        //Find the first element of the array for which the block is true. 
         //So, find the first element of [0 1 2 3 4] for which {5\.*<} evaluates to true.
         //The inner block squares a number and returns true if it is greater than the input.
(        //Decrement by 1 

Haskell, 147 138 134 128 Bytes

Nicht der kürzeste Code der Welt, aber er wird in O (log n) und auf Zahlen beliebiger Größe ausgeführt:

h x=div(x+1)2
n%(g,s)|g*g<n=(g+s,h s)|g*g>n=(g-s,h s)|0<1=(g,0)
f(x:r@(y:z:w))|x==z=min x y|0<1=f r
s n=fst$f$iterate(n%)(n,h n)

Dies führt eine binäre Suche im Bereich [0..n] durch, um die beste untere Annäherung an sqrt (n) zu finden. Hier ist eine ungolfed Version:

-- Perform integer division by 2, rounding up
half x = x `div` 2 + x `rem` 2

-- Given a guess and step size, refine the guess by adding 
-- or subtracting the step as needed.  Return the new guess
-- and step size; if we found the square root exactly, set
-- the new step size to 0.
refineGuess n (guess, step)
    | square < n  =  (guess + step, half step)
    | square > n  =  (guess - step, half step)
    | otherwise   =  (guess, 0)
    where square = guess * guess     

-- Begin with the guess sqrt(n) = n and step size (half n),
-- then generate the infinite sequence of refined guesses.
-- 
-- NOTE: The sequence of guesses will do one of two things:
--         - If n has an integral square root m, the guess 
--           sequence will eventually be m,m,m,...
--         - If n does not have an exact integral square root,
--           the guess sequence will eventually alternate
--           L,U,L,U,.. between the integral lower and upper
--           bounds of the true square root.
--        In either case, the sequence will reach periodic
--        behavior in O(log n) iterations.
guesses n = map fst $ iterate (refineGuess n) (n, half n)

-- Find the limiting behavior of the guess sequence and pick out
-- the lower bound (either L or m in the comments above)
isqrt n = min2Cycle (guesses n)
    where min2Cycle (x0:rest@(x1:x2:xs))
            | x0 == x2    =   min x0 x1
            | otherwise   =   min2Cycle rest

Bearbeiten: Zwei Bytes wurden gespeichert, indem die "else" -Klauseln durch "0 <1" als kürzere Version von "True" und einige weitere durch Inlining von g * g ersetzt wurden.

Wenn Sie mit O (sqrt (n)) zufrieden sind, können Sie dies auch einfach tun

s n=(head$filter((>n).(^2))[0..])-1

für 35 Zeichen, aber was macht das für einen Spaß?

Bearbeiten 2: Ich habe gerade festgestellt, dass Paare nach Wörterbuchreihenfolge sortiert sind, anstatt min2Cycle auszuführen. map fst, ich kann einfach fst machen. min2Cycle. Im Code für Golf bedeutet dies, dass f $ map fst durch fst $ f ersetzt wird, wodurch 4 weitere Bytes eingespart werden.

Edit 3: Dank proudhaskeller sechs weitere Bytes gespeichert!

JavaScript 91 88 86: Optimiert für Geschwindigkeit

function s(n){var a=1,b=n;while(Math.abs(a-b)>1){b=n/a;a=(a+b)/2}return Math.floor(a)}

JavaScript 46: Nicht für Geschwindigkeit optimiert

function s(n){a=1;while(a*a<=n)a++;return a-1}

Hier ist eine JSFiddle: http://jsfiddle.net/rmadhuram/1Lnjuo4k/

C 95 97

Bearbeiten Typedef, vorgeschlagen von @Michaelangelo

Dies sollte mehr oder weniger eine einfache Implementierung des Heron-Algorithmus sein. Das einzige Manko ist die Berechnung des durchschnittlichen Vermeidungsüberlaufs von ganzen Zahlen: a = (m + n) / 2 funktioniert nicht für große Zahlen.

typedef uint64_t Z;
Z q(Z x)
{
   Z n=1,a=x,m=0;
   for(;a-m&&a-n;) n=a,m=x/n,a=m/2+n/2+(m&n&1);
   return a;
}

C # 64 62 55

Da dies ein Code-Golf ist (und ich bin schrecklich mit Mathematik) und die Laufzeit nur ein Vorschlag ist, habe ich den naiven Ansatz gewählt, der in linearer Zeit abläuft:

decimal f(ulong a){var i=0m;while(++i*i<=a);return--i;}

( Test auf dotnetfiddle )

Natürlich ist es für größere Eingänge furchtbar langsam.

Clojure - 51 oder 55 Bytes

Überprüft alle Zahlen von n bis 0 und gibt die erste Stelle an x^2 <= n. Laufzeit istO(n - sqrt n)

Unbenannt:

(fn[x](first(filter #(<=(* % %)x)(range x -1 -1))))

Genannt:

(defn f[x](first(filter #(<=(* % %)x)(range x -1 -1))))

Beispiel:

(map (fn[x](first(filter #(<=(* % %)x)(range x -1 -1)))) (range 50))
=> (0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7)

Befunge 93 - 48 Bytes oder 38 Zeichen

101p&02p>02g01g:*`#v_01g1-.@
        ^  p10+1g10<        

Probieren Sie es hier.

Cobra - 62

do(n as uint64)as uint64
    o=n-n
    while o*o<n,o+=1
    return o

Batch - 74

set a=0
:1
set /ab=%a%*%a%
if %b% LSS %1 set /aa=%a%+1&goto 1
echo %a%

Haskell, 53 50 49 Zeichen, O (log n)

s n=until((<=n).(^2))(\g->g-1-div(g^2-n-1)(2*g))n

Diese Lösung implementiert die Newton-Raphson-Methode, sucht jedoch nach ganzen Zahlen anstelle von Gleitkommazahlen. wiki: http://en.wikipedia.org/wiki/Newton%27s_method

Die Komplexität scheint bei O (log n) zu liegen, aber gibt es einen Beweis dafür? Bitte antworten Sie in den Kommentaren.

J (10)

Sehr, sehr, sehr inspiriert von der Antwort von @Dennis :

<.@%~^&1.5

Und ein bisschen länger, aber mit besserer Leistung (ich vermute):

<.@(-:&.^.)

floor(halve under log)

Zur Ausführung werden eingerückte Teile eingegeben:

   f=:<.@%~^&1.5
   f 0 8 12 16
0 2 3 4
   g=:<.@(-:&.^.)
   g 0 8 12 16
0 2 3 4

APL - 12 chars, 19 bytes

{⌊(⍵*1.5)÷⍵}

example use:

{⌊(⍵*1.5)÷⍵}17

returns 4

Test vector

{⌊(⍵*1.5)÷⍵}¨0 1 2 3 4 8 9 15 16 65535 65536 18446744073709551615

returns

1 1 1 1 2 2 3 3 4 255 256 4294967296

Try Online

Big thanks to: user "ssdecontrol" for algorithm

C99 (108 characters)

Here is my own solution in C99, which is adapted from an algorithm in an article on Wikipedia. I'm sure it must be possible to do much better than this in other languages.

Golfed:

uint64_t s(uint64_t n){uint64_t b=1,r=0;while(n/b/4)b*=4;for(;b;b/=4,r/=2)n>=r+b?r+=b,n-=r,r+=b:0;return r;}

Partially golfed:

uint64 uint64_sqrt(uint64 n)
{
  uint64 b = 1, r = 0;
  while (b <= n / 4)
    b *= 4;
  for (; b; b /= 4, r /= 2)
    if (n >= r + b)
      { r += b; n -= r; r+= b; }
  return r;
}

Ungolfed:

uint64_t uint64_sqrt(uint64_t const n)
{
  uint64_t a, b, r;

  for (b = 1; ((b << 2) != 0) && ((b << 2) <= n); b <<= 2)
    ;

  a = n;
  r = 0;
  for (; b != 0; b >>= 2)
  {
    if (a >= r + b)
    {
      a -= r + b;
      r = (r >> 1) + b;
    }
    else
    {
      r >>= 1;
    }
  }

  // Validate that r² <= n < (r+1)², being careful to avoid integer overflow,
  // which would occur in the case where n==2⁶⁴-1, r==2³²-1, and could also
  // occur in the event that r is incorrect.
  assert(n>0? r<=n/r : r==0);  // Safe way of saying r*r <= n
  assert(n/(r+1) < (r+1));     // Safe way of saying n < (r+1)*(r+1)

  return r;
}

JavaScript 73 81 (to comply with 64-bit numbers requirement)

n=prompt();g=n/3;do{G=g,g=(n/g+g)/2}while(1E-9<Math.abs(G-g))alert(Math.floor(g))

Implementing Heron of Alexandria's algorithm...

Powershell (52) Limited to Int32 (-2,147,483,648 to 2,147,483,647)

function f($n){($n/2)..0|%{if($_*$_-le$n){$_;exit}}}

I'm screaming at Powershell right now trying to make the last test case work but no matter what I do Powershell winds up using the pipeline variable $_ as an Int32, and I can't find a way around it right now.

So I'll just limit my answer for now. If I can find a better way to handle uint64s I will edit. (The last test case is too big for Powershell's normal Int64 type, by the way!)

Here are a few test cases (with a bit of extra output I used to track the time)

f 17
4
Elapsed Time: 0.0060006 seconds

f 65
8
Elapsed Time: 0.0050005 seconds

f 65540
256
Elapsed Time: 1.7931793 seconds

f 256554
506
Elapsed Time: 14.7395391 seconds

I don't know my O()s, but this seems like a pretty dramatic jump.

Caveat: as of 2011, R had no built-in support for 64 bit integers as I had assumed it did. These answers might be invalid on that technicality, but then again R has changed a lot in the last 3 years.

R, 85

Using Newton's method:

function(n){s=F
x=n
y=(1/2)*(x+n/x)
while(abs(x-y)>=1){x=y
y=(1/2)*(x+n/x)}
trunc(y)}

which converges quadratically. +2 characters to assign the function to a variable for benchmarking:

microbenchmark(q(113424534523616))
# Unit: microseconds
#                expr    min      lq median      uq    max neval
#  q(113424534523616) 24.489 25.9935 28.162 29.5755 46.192   100

R, 37

Brute force:

function(n){t=0
while(t^2<n) t=t+1
t}

And the same check:

microbenchmark::microbenchmark(q(113424534523616),times=1)
# Unit: seconds
#                 expr      min       lq   median       uq      max neval
#   q(113424534523616) 4.578494 4.578494 4.578494 4.578494 4.578494     1

R, 30

The cheap/brilliant exponentiation trick:

function(n) trunc(n^(1.5)/n)

which also happens to be very fast (although not as fast as the built-in):

microbenchmark(q(113424534523616),sqrt(113424534523616))
# Unit: nanoseconds
#                   expr min    lq median    uq  max neval
#     z(113424534523616) 468 622.5  676.5 714.5 4067   100
#  sqrt(113424534523616)  93 101.0  119.0 160.5 2863   100

C, 38

f(n){int m;while(++m*m<=n);return--m;}

Translation of my Forth submission. Slow but correct. O(√n). Tested on OS X (64 bit).

dc, 50 bytes

dc -e"?dsist[lt2/dstd*li<B]dsBx[lt1+dstd*li!<A]dsAxlt1-f"

Spaced out and explained:

               # The idea here is to start with the input and reduce it quickly until it is
               # less than what we want, then increment it until it's just right
?              # Take input from stdin
d si st        # Duplicate input, store in `i' and in `t'
[              # Begin macro definition (when I write in dc, "macro"=="function")
 lt            # Load t, our test term
 2/            # Divide t by two
 d st          # Store a copy of this new term in `t'
 d*            # Duplicate and multiply (square)
 li<B          # Load i; if i<(t^2), execute B
] d sB x       # Duplicate, store function as `B', and execute
               # Loop ends when t^2 is less than i
[              # Begin macro definition
 lt            # Load t, our test term
 1+            # Increment
 d st          # Store a copy of this new term in `t'
 d*            # Duplicate and multiply (square)
 li!<A         # Load i; if i>=(t^2), execute A
] d sA x       # Duplicate, store function as `A', and execute
               # Loop ends when t^2 == i+1
lt 1- f        # Load t, decrement, and dump stack

C, 139 137 136 bytes

My first try at code golf. It looks like it's the shortest in C that fits the "efficient" requirement, as it runs in O(log n) time, using only addition and bit shifts. Though I'm sure it could be shorter yet...

It should work just fine for larger integer values too as long as the a=32 part is changed to a=NUMBITS/2.

typedef uint64_t x;x f(x o){x a=32,t=0,r=0,y=0,z;for(;a--+1;){z=(x)3<<2*a;y*=2;t++<r?y++,r-=t++:t--;t*=2;r*=4;r+=(o&z)>>2*a;}return y;}

C - 50 (61 without global)

typedef uint64_t T;T n,i;f(){while(++i*i<=n);--i;}

It use global variables as parameter and return value to save space.

No global version :

typedef uint64_t T;T f(T n){T i=0;while(++i*i<=n);return--i;}

C++ 125

int main()
{
uint64_t y;cin>>y;
double x=y/2,d,z;
while((d=(x*x-y))>0.5)
{
d<0?x+=0.5:x-=0.5;
}
cout<<(uint64_t)x;
}