Masalah:

Dalam pilihan bahasa Anda, tulis fungsi terpendek yang mengembalikan lantai akar kuadrat dari integer 64-bit yang tidak ditandatangani.

Kasus uji:

Fungsi Anda harus bekerja dengan benar untuk semua input, tetapi di sini ada beberapa yang membantu mengilustrasikan ide tersebut:

               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

Aturan:

1. Anda dapat memberi nama fungsi apa pun yang Anda suka. (Fungsi yang tidak disebutkan namanya, anonim, atau lambda baik-baik saja, asalkan fungsi tersebut dapat dipanggil.)
2. Hitungan karakter adalah yang terpenting dalam tantangan ini, tetapi runtime juga penting. Saya yakin Anda dapat memindai ke atas secara iteratif untuk jawaban dalam waktu O (√n) dengan jumlah karakter yang sangat kecil, tetapi waktu O (log (n)) akan benar-benar lebih baik (yaitu, dengan asumsi nilai input n, tidak sedikit-panjang n).
3. Anda mungkin ingin mengimplementasikan fungsi menggunakan integer murni dan / atau artitmetika boolean. Namun, jika Anda benar-benar ingin menggunakan perhitungan floating-point, maka itu tidak masalah selama Anda memanggil fungsi pustaka. Jadi, hanya mengatakan return (n>0)?(uint32_t)sqrtl(n):-1;dalam C adalah terlarang meskipun itu akan menghasilkan hasil yang benar. Jika Anda menggunakan aritmatika floating-point, Anda dapat menggunakan *, /, +, -, dan eksponensial (misalnya, **atau ^jika itu built-in operator dalam bahasa pilihan Anda, tetapi eksponensial hanya kekuasaan tidak kurang dari 1 ). Pembatasan ini untuk mencegah "kecurangan" dengan memanggil sqrt()atau varian atau meningkatkan nilai ke kekuatan ½.
4. Jika Anda menggunakan operasi floating-point (lihat # 3), Anda tidak diharuskan untuk mengembalikan tipe integer; hanya bahwa nilai kembali adalah bilangan bulat, mis. lantai (sqrt (n)), dan dapat menampung nilai 32-bit yang tidak ditandatangani.
5. Jika Anda menggunakan C / C ++, Anda dapat mengasumsikan keberadaan tipe integer 64-bit dan 32-bit yang tidak ditandatangani, misalnya, uint64_tdan uint32_tseperti yang didefinisikan dalam stdint.h. Jika tidak, pastikan saja tipe integer Anda mampu menahan integer 64-bit yang tidak ditandatangani.
6. Jika bahasa Anda tidak mendukung bilangan bulat 64-bit (misalnya, Brainfuck tampaknya hanya memiliki dukungan bilangan bulat 8-bit), maka lakukan yang terbaik dengan itu dan nyatakan batasan dalam judul jawaban Anda. Yang mengatakan, jika Anda dapat mengetahui cara mengkodekan integer 64-bit dan mendapatkan akar kuadrat dengan benar menggunakan aritmatika primitif 8-bit, maka lebih banyak kekuatan untuk Anda!
7. Bersenang-senang dan menjadi kreatif!

CJam, 17 (atau 10) byte

{_1.5#\/i}

Cobalah online dengan memverifikasi kasus uji:

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

Itu tidak akan lulus ujian terakhir karena masalah pembulatan, tetapi karena 18446744073709551615bukan Integer di CJam (ini adalah Integer Besar ), kami masih bagus, kan?

Jika tidak, kode berikut (dan sedikit lebih lama) akan memperbaiki kesalahan tersebut:

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

Bukan solusi terpendek lagi, tapi faaast .

Bagaimana itu bekerja

__    " 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

Saya percaya bahwa ini adalah entri terpendek dari bahasa apa pun yang tidak dirancang untuk bermain golf.

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

Ini nama fungsi sdengan parameter adan mengembalikan satu minus angka pertama yang kuadratnya lebih besar dari a. Berjalan sangat lambat (O (sqrt n), mungkin?).

Golfscript, 17 karakter

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

Saya bisa memberi nama fungsi saya dengan cara apa pun yang saya suka, tetapi saya memutuskan untuk tidak menyebutkannya sama sekali. Tambahkan dua karakter untuk nama itu, tambahkan tiga untuk nama itu dan tidak meninggalkannya di tumpukan, kurangi satu karakter jika menyediakan program lengkap tidak masalah.

Kekejian ini berjalan tidak dalam waktu logaritmik dalam nilai input, bukan dalam waktu O (sqrt n), dibutuhkan jumlah waktu rejan linear untuk menghasilkan hasilnya. Itu juga membutuhkan banyak ruang. Benar-benar menghebohkan. Tapi ... ini kode-golf.

Algoritme adalah:

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

Pyth , 14 karakter

DsbR;fgb*TTL'b

Menyediakan fungsi bernama, s, yang menghitung akar kuadrat dengan memfilter daftar dari 0 ke n untuk kuadrat yang lebih besar dari input, lalu mencetak angka tersebut. Tidak menggunakan eksponensial atau mengapung.

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

Contoh penggunaan:

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 (non-bersaing - Bahasa lebih baru daripada tantangan), 43

Saat mengerjakan jawaban ini , terpikir oleh saya bahwa metode yang sama dapat digunakan untuk menghitung akar kuadrat integer menggunakan retina:

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

1+

Ini bergantung pada fakta bahwa kuadrat sempurna dapat dinyatakan sebagai 1+3+5+7+..., dan secara wajar bahwa jumlah istilah dalam ungkapan ini adalah akar kuadrat.

Cobalah online. (Baris pertama ditambahkan untuk memungkinkan beberapa testcase dijalankan.)

Jelas karena konversi desimal ke unary, ini hanya akan bekerja untuk input yang relatif kecil.

Perl, 133 karakter

Bukan yang terpendek sejauh ini, tetapi menggunakan algoritma digit-per-digit untuk menangani input ukuran apa pun, dan berjalan dalam waktu O (log n). Mengubah secara bebas antara angka-sebagai-string dan angka-sebagai-angka. Karena produk terbesar yang mungkin adalah root-sejauh ini dengan kuadrat dari satu digit, ia harus mampu mengambil akar kuadrat hingga 120-bit atau lebih pada sistem 64-bit.

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}

Didekompresi, yaitu:

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) / Oktaf (55)

Ini berhasil akar kuadrat dengan menggunakan metode titik tetap. Itu konvergen dalam maksimal 36 langkah (untuk 2 ^ 64-1 sebagai argumen) dan kemudian memeriksa apakah itu yang lebih rendah dari akar integer 'mungkin'. Karena selalu menggunakan 36 iterasi, ia memiliki runtime O (1) = P

Argumennya dianggap uint64.

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

Oktaf:

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 karakter

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)

Pendekatan rekursif alami. Menghitung akar kuadrat potensial hingga kuadratnya terlalu tinggi, lalu turun dengan 1. Gunakan Stackless Python jika Anda khawatir melebihi kedalaman tumpukan.

The and/oridiom setara dengan operator ternary sebagai

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

Edit: Aku bisa malah mendapatkan 25 karakter dengan memanfaatkan aturan "Anda dapat menggunakan *, /, +, -, dan eksponensial (misalnya, **atau ^jika itu adalah eksponensial built-in operator dalam bahasa pilihan Anda, tetapi hanya kekuasaan tidak kurang dari 1). " (Sunting: Rupanya Dennis sudah menemukan dan mengeksploitasi trik ini.)

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

Saya menggunakan operator divisi integer //dari Python 3 untuk membulatkan ke bawah. Sayangnya, saya menghabiskan banyak karakter agar case n=0tidak memberikan pembagian dengan kesalahan 0. Jika bukan karena itu, saya bisa melakukan 18 karakter

lambda n:n**1.5//n 

Aturan juga tidak mengatakan fungsi harus dinamai (tergantung bagaimana Anda mengartikan "Anda dapat memberi nama fungsi apa pun yang Anda suka."), Tetapi jika ya, itu adalah dua karakter lagi.

C99 (58 karakter)

Ini adalah contoh jawaban yang saya tidak akan menganggapnya sebagai jawaban yang baik, meskipun menarik dari sudut pandang kode golf karena sangat tidak sopan, dan saya pikir akan menyenangkan untuk memasukkannya ke dalam campuran:

Asli: 64 karakter

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

Alasan yang satu ini mengerikan adalah karena ia berjalan dalam waktu O (√n) daripada waktu O (log (n)). (Di mana n adalah nilai input.)

Edit: 63 karakter

Mengubah r-1to --rdan berbatasan dengan return:

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

Edit: 62 karakter

Memindahkan kenaikan loop ke dalam bagian kondisional loop (catatan: ini memiliki perilaku tidak dijamin karena urutan operasi sehubungan dengan operator preincrement adalah khusus-kompiler):

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

Edit: 60 karakter

Menambahkan typedefuntuk disembunyikan uint64_t(kredit ke pengguna technosaurus untuk saran ini)

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

Edit: 58 karakter

Sekarang membutuhkan parameter kedua dilewatkan sebagai 0 dalam doa fungsi, misalnya, r(n,0)bukan hanya r(n). Ok, untuk kehidupan saya, pada titik ini saya tidak bisa melihat bagaimana mengompres ini lebih jauh ... siapa pun?

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

Golfscript - 14 karakter

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

Temukan nomor terkecil ilebih sedikit dari pada input nyang mana n < i*i. Kembali i - 1.

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

Penjelasan untuk mereka yang tidak tahu Golfscript juga, untuk panggilan sampel dengan input 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 byte

Bukan kode terpendek di dunia, tetapi itu berjalan di O (log n), dan pada nomor berukuran sewenang-wenang:

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)

Ini melakukan pencarian biner dari rentang [0..n] untuk menemukan perkiraan lebih rendah terbaik ke sqrt (n). Ini adalah versi yang tidak dikoleksi:

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

Sunting: Menyimpan dua byte dengan mengganti klausa "jika tidak" dengan "0 <1" sebagai versi yang lebih pendek dari "True", dan beberapa lainnya dengan menggarisbawahi g * g.

Juga, jika Anda senang dengan O (sqrt (n)) Anda bisa melakukannya

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

untuk 35 karakter, tapi apa yang menyenangkan itu?

Sunting 2: Saya baru menyadari bahwa karena pasangan diurutkan berdasarkan urutan kamus, alih-alih melakukan min2Cycle. map fst, saya bisa melakukan fst. min2Cycle. Dalam kode golf, yang artinya mengganti f $ map pertama dengan fst pertama, menghemat 4 byte lebih banyak.

Sunting 3: Disimpan enam byte lagi berkat banggahaskeller!

JavaScript 91 88 86: Dioptimalkan untuk kecepatan

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: Tidak dioptimalkan untuk kecepatan

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

Berikut ini adalah JSFiddle: http://jsfiddle.net/rmadhuram/1Lnjuo4k/

C 95 97

Edit Typedef, disarankan oleh @Michaelangelo

Ini harus lebih atau kurang merupakan implementasi langsung dari algoritma Heron. Satu-satunya kekhasan adalah dalam menghitung rata-rata menghindari integer overflow: a = (m + n) / 2 tidak bekerja untuk angka biiiig.

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

Karena ini adalah kode-golf (dan saya buruk dengan matematika), dan runtime hanyalah saran, saya telah melakukan pendekatan naif yang berjalan dalam waktu linier:

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

( tes pada dotnetfiddle )

Tentu saja, ini sangat lambat untuk input yang lebih besar.

Clojure - 51 atau 55 byte

Memeriksa semua angka dari n hingga 0, memberikan yang pertama di mana x^2 <= n. Runtime adalahO(n - sqrt n)

Tanpa nama:

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

Bernama:

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

Contoh:

(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 atau 38 Karakter

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

Cobalah di sini.

Cobra - 62

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

Angkatan - 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 karakter, O (log n)

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

solusi ini mengimplementasikan metode newton-raphson, meskipun mencari bilangan bulat bukan mengapung. wiki: http://en.wikipedia.org/wiki/Newton%27s_method

kerumitan tampaknya tentang O (log n), tetapi apakah ada buktinya? tolong jawab di komentar.

J (10)

Sangat, sangat, sangat terinspirasi oleh jawaban @ Dennis :

<.@%~^&1.5

Dan sedikit lebih lama, tetapi dengan kinerja yang lebih baik (saya curiga):

<.@(-:&.^.)

floor(halve under log)

Untuk mengeksekusi, bagian indentasi adalah input:

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

APL - 12 karakter, 19 byte

{⌊(⍵*1.5)÷⍵}

contoh gunakan:

{⌊(⍵*1.5)÷⍵}17

mengembalikan 4

Tes vektor

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

kembali

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

Coba Online

Terima kasih banyak kepada : pengguna "ssdecontrol" untuk algoritme

C99 (108 karakter)

Ini adalah solusi saya sendiri di C99, yang diadaptasi dari suatu algoritma dalam sebuah artikel di Wikipedia . Saya yakin ini harus dilakukan jauh lebih baik daripada ini dalam bahasa lain.

Golf:

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

Golf sebagian:

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

Tidak Disatukan:

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 (untuk memenuhi persyaratan angka 64-bit)

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

Menerapkan algoritma Heron of Alexandria ...

Powershell (52) Terbatas untuk Int32 (-2.147.483.648 hingga 2.147.483.647)

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

Saya berteriak pada Powershell sekarang mencoba untuk membuat test case terakhir bekerja tetapi tidak peduli apa yang saya lakukan Powershell akhirnya menggunakan variabel pipa $ _ sebagai Int32, dan saya tidak dapat menemukan cara mengatasinya sekarang.

Jadi saya akan membatasi jawaban saya untuk saat ini. Jika saya dapat menemukan cara yang lebih baik untuk menangani uint64, saya akan mengedit. (Omong kosong terakhir terlalu besar untuk tipe Int64 normal Powershell!)

Berikut adalah beberapa test case (dengan sedikit output tambahan yang saya gunakan untuk melacak waktu)

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

Saya tidak tahu O () saya, tapi ini sepertinya lompatan yang cukup dramatis.

Peringatan: pada 2011, R tidak memiliki dukungan bawaan untuk integer 64 bit seperti yang saya asumsikan. Jawaban-jawaban ini mungkin tidak valid dalam hal teknis, tetapi sekali lagi R telah banyak berubah dalam 3 tahun terakhir.

R, 85

Menggunakan metode Newton:

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

yang menyatu secara kuadrat. +2 karakter untuk menetapkan fungsi ke variabel untuk pembandingan:

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

Paksaan:

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

Dan cek yang sama:

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 murah / brilian eksponensial trik :

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

yang juga terjadi sangat cepat (walaupun tidak secepat 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;}

Terjemahan dari kiriman Keempat saya. Lambat tapi benar. O (√n). Diuji pada OS X (64 bit).

dc, 50 byte

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

Ditata dan dijelaskan:

               # 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 byte

Percobaan pertama saya di kode golf. Sepertinya ini adalah yang terpendek dalam C yang sesuai dengan persyaratan "efisien", karena berjalan dalam O(log n)waktu, hanya menggunakan penambahan dan pergeseran bit. Meskipun saya yakin itu bisa lebih pendek lagi ...

Seharusnya berfungsi dengan baik untuk nilai integer yang lebih besar juga asalkan a=32bagian tersebut diubah 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 tanpa global)

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

Ini menggunakan variabel global sebagai parameter dan nilai kembali untuk menghemat ruang.

Tidak ada versi global:

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