Problem:

W wybranym języku napisz najkrótszą funkcję zwracającą podstawę pierwiastka kwadratowego z niepodpisanej 64-bitowej liczby całkowitej.

Przypadki testowe:

Twoja funkcja musi działać poprawnie dla wszystkich danych wejściowych, ale oto kilka, które pomagają zilustrować ten pomysł:

               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

Zasady:

1. Możesz nazwać swoją funkcję dowolnie. (Funkcje bezimienne, anonimowe lub lambda są w porządku, o ile można je wywołać).
2. Liczba postaci jest najważniejsza w tym wyzwaniu, ale ważne jest również środowisko wykonawcze. Jestem pewien, że możesz iteracyjnie skanować w górę w poszukiwaniu odpowiedzi w czasie O (√n) przy bardzo małej liczbie znaków, ale czas O (log (n)) naprawdę byłby lepszy (to znaczy przy założeniu wartości wejściowej n, nie długość bitowa n).
3. Prawdopodobnie będziesz chciał zaimplementować tę funkcję, używając arytmetyki wyłącznie liczb całkowitych i / lub logicznych. Jeśli jednak naprawdę chcesz korzystać z obliczeń zmiennoprzecinkowych, to jest w porządku, o ile nie wywołujesz żadnych funkcji bibliotecznych. Zatem po prostu powiedzenie return (n>0)?(uint32_t)sqrtl(n):-1;w C jest poza limitem, nawet jeśli dałoby to prawidłowy wynik. Jeśli używasz arytmetyki zmiennoprzecinkowej, można użyć *, /, +, -oraz potęgowanie (np **lub ^jeśli jest wbudowany operatora w wybranym języku, ale tylko potęgowanie uprawnień nie mniej niż 1 ). To ograniczenie ma na celu zapobieganie „oszukiwaniu” przez sprawdzanie sqrt()lub wariant lub podnoszenie wartości do ½ potęgi.
4. Jeśli używasz operacji zmiennoprzecinkowych (patrz # 3), nie jest wymagane, aby typ zwracany był liczbą całkowitą; tylko, że zwracana wartość jest liczbą całkowitą, np. floor (sqrt (n)), i jest w stanie pomieścić dowolną 32-bitową wartość bez znaku.
5. Jeśli używasz C / C ++, można zakładać istnienie niepodpisane 64-bitowych i 32-bitowych typów całkowitych, np uint64_ti uint32_t, jak określono w stdint.h. W przeciwnym razie upewnij się, że Twój typ liczb całkowitych jest w stanie pomieścić dowolną 64-bitową liczbę całkowitą bez znaku.
6. Jeśli Twój język nie obsługuje 64-bitowych liczb całkowitych (na przykład, Brainfuck najwyraźniej obsługuje tylko 8-bitowe liczby całkowite), zrób to najlepiej i podaj ograniczenie w tytule odpowiedzi. To powiedziawszy, jeśli możesz dowiedzieć się, jak zakodować 64-bitową liczbę całkowitą i poprawnie uzyskać jej pierwiastek kwadratowy za pomocą 8-bitowej prymitywnej arytmetyki, to więcej mocy dla ciebie!
7. Baw się i bądź kreatywny!

CJam, 17 (lub 10) bajtów

{_1.5#\/i}

Wypróbuj online , weryfikując przypadki testowe:

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

Nie przejdzie ostatniego przypadku testowego z powodu problemów z zaokrąglaniem, ale ponieważ 18446744073709551615nie jest liczbą całkowitą w CJam (jest to duża liczba całkowita ), nadal jesteśmy dobrzy, prawda?

Jeśli nie, poniższy (i nieco dłuższy) kod naprawi te błędy:

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

Nie jest to już najkrótsze rozwiązanie, ale uczciwe .

Jak to działa

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

Uważam, że jest to najkrótsza pozycja z dowolnego języka, który nie został zaprojektowany do gry w golfa.

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

IT nazwy funkcji sz parametrem ai zwraca jeden minus pierwszego numeru, który jest większy niż kwadrat a. Działa niesamowicie wolno (może O (sqrt n)?).

Golfscript, 17 znaków

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

Mógłbym nazwać moją funkcję w dowolny sposób, ale postanowiłem nie nazywać jej wcale. Dodaj dwa znaki, aby go nazwać, dodaj trzy, aby nazwać go i nie pozostawiać go na stosie, odejmij jeden znak, jeśli podanie pełnego programu jest w porządku.

Ta obrzydliwość nie działa w czasie logarytmicznym w wartości wejściowej, a nie w czasie O (sqrt n), a uzyskanie wyniku zajmuje ogromną ilość czasu. Zajmuje również tyle miejsca. Absolutnie przerażające. Ale ... to jest golf golfowy.

Algorytm to:

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

Pyth , 14 znaków

DsbR;fgb*TTL'b

Zapewnia nazwaną funkcję s, która oblicza pierwiastek kwadratowy, filtrując listę od 0 do n dla kwadratu większego niż dane wejściowe, a następnie drukuje ostatnią taką liczbę. Nie używa potęgowania ani liczb zmiennoprzecinkowych.

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

Przykładowe użycie:

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 (niekonkurencyjna - język jest nowszy niż wyzwanie), 43

Podczas pracy nad tą odpowiedzią przyszło mi do głowy, że podobną metodę można zastosować do obliczenia całkowitych pierwiastków kwadratowych za pomocą siatkówki:

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

1+

Opiera się to na tym, że idealne kwadraty mogą być wyrażone jako 1+3+5+7+..., a następstwem tego jest to, że liczba wyrażeń w tym wyrażeniu jest pierwiastkiem kwadratowym.

Wypróbuj online. (Dodano pierwszy wiersz, aby umożliwić uruchomienie wielu przypadków testowych).

Oczywiście ze względu na konwersję dziesiętną na jednostkową będzie to działać tylko w przypadku stosunkowo niewielkich nakładów.

Perl, 133 znaki

Zdecydowanie nie najkrótszy, ale wykorzystuje algorytm cyfra po cyfrze do obsługi dowolnego rozmiaru wejściowego i działa w czasie O (log n). Swobodnie konwertuje między liczbami jako ciągami znaków i liczbami jako liczbami. Ponieważ największym możliwym produktem jest jak dotąd pierwiastek z kwadratem jednej cyfry, powinien być w stanie przyjąć pierwiastek kwadratowy z około 120-bitowych liczb w systemie 64-bitowym.

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}

Zdekompresowane, to znaczy:

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)

Oblicza pierwiastek kwadratowy za pomocą metody punktu stałego. Zbiega się w maksymalnie 36 krokach (dla 2 ^ 64-1 jako argument), a następnie sprawdza, czy jest to dolny z „możliwych” pierwiastków całkowitych. Ponieważ zawsze używa 36 iteracji, ma czas działania O (1) = P

Przyjmuje się, że argumentem jest 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

Oktawa:

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 znaków

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)

Naturalne podejście rekurencyjne. Zlicza potencjalne pierwiastki kwadratowe, aż ich kwadrat będzie zbyt wysoki, a następnie spadnie o 1. Użyj Python bez stosu, jeśli martwisz się przekroczeniem głębokości stosu.

Ten and/oridiom jest równoważny operatorowi potrójnemu jako

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

Edit: mogę zamiast dostać 25 znaków wykorzystując regułę „można użyć *, /, +, -, i potęgowanie (np **lub ^jeśli jest wbudowany operatora w wybranym języku, ale tylko potęgowanie uprawnień nie mniej niż 1). „ (Edycja: Najwyraźniej Dennis już znalazł i wykorzystał tę sztuczkę.)

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

Używam operatora dzielenia liczb całkowitych //w Pythonie 3 do zaokrąglania w dół. Niestety spędzam dużo znaków, aby skrzynka n=0nie dzieliła błędu przez 0. Gdyby nie to, mógłbym zrobić 18 znaków

lambda n:n**1.5//n 

Reguły również nie mówiły, że funkcja musi zostać nazwana (w zależności od tego, jak interpretujesz „Możesz nazwać swoją funkcję dowolnie.”), Ale jeśli tak, to dwa kolejne znaki.

C99 (58 znaków)

To przykład odpowiedzi, której nie uważałbym za dobrą, chociaż jest to dla mnie interesujące z punktu widzenia golfa kodowego, ponieważ jest tak przewrotne, i pomyślałem, że fajnie byłoby wrzucić do tego miksu:

Oryginał: 64 znaki

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

Powodem tego jest to, że działa on w czasie O (√n) zamiast w czasie O (log (n)). (Gdzie n jest wartością wejściową.)

Edycja: 63 znaków

Zmiana r-1do --ri łączące je do return:

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

Edycja: 62 znaki

Przeniesienie przyrostu pętli do wewnątrz warunkowej części pętli (uwaga: zachowanie to nie jest gwarantowane, ponieważ kolejność operacji względem operatora wstępnego przyrostu zależy od kompilatora):

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

Edycja: 60 znaków

Dodanie typedefdo ukrycia uint64_t( podziękowania dla technozaura użytkownika za tę sugestię).

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

Edycja: 58 znaków

Teraz wymaga podania drugiego parametru jako 0 w wywołaniu funkcji, np. r(n,0)Zamiast po prostu r(n). Ok, przez całe moje życie, w tym momencie nie widzę, jak to kompresować ... ktoś?

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

Golfscript - 14 znaków

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

Znajdź najmniejszą liczbę imniejszą niż wartość wejściowa, ndla której n < i*i. Return i - 1.

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

Wyjaśnienie dla tych, którzy nie znają również Golfscript, dla przykładowego wywołania z wejściem 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 128 bajtów

Nie jest to najkrótszy kod na świecie, ale działa w O (log n) i na liczbach o dowolnej wielkości:

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)

Wykonuje binarne wyszukiwanie zakresu [0..n] w celu znalezienia najlepszego niższego przybliżenia do sqrt (n). Oto wersja bez golfa:

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

Edycja: Zapisano dwa bajty, zastępując klauzule „w przeciwnym razie” „0 <1” jako krótszą wersją „True”, a kilka innych poprzez wstawienie g * g.

Ponadto, jeśli jesteś zadowolony z O (sqrt (n)), możesz po prostu to zrobić

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

na 35 znaków, ale co to za zabawa?

Edycja 2: Właśnie zdałem sobie sprawę, że ponieważ pary są sortowane według kolejności słownikowej, zamiast robić min2Cycle. map fst, mogę po prostu zrobić fst. min2Cycle. W kodzie golfowym oznacza to zamianę f $ map fst na fst $ f, co pozwala zaoszczędzić 4 bajty.

Edycja 3: Oszczędź sześć kolejnych bajtów dzięki dumnemu paskudnikowi!

JavaScript 91 88 86: Zoptymalizowany pod kątem szybkości

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: Niezoptymalizowany pod kątem szybkości

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

Oto JSFiddle: http://jsfiddle.net/rmadhuram/1Lnjuo4k/

C 95 97

Edytuj Typedef, sugerowany przez @Michaelangelo

Powinno to być mniej więcej prostą implementacją algorytmu Heron. Jedynym dziwactwem jest obliczenie średniego uniknięcia przepełnienia liczb całkowitych: a = (m + n) / 2 nie działa dla liczb dużych.

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

Ponieważ jest to gra w golfa kodowego (a ja jestem okropny z matematyki), a środowisko wykonawcze jest jedynie sugestią, zastosowałem naiwne podejście, które działa w czasie liniowym:

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

( test na dotnetfiddle )

Oczywiście jest to strasznie wolne dla większych nakładów.

Clojure - 51 lub 55 bajtów

Sprawdza wszystkie liczby od n do 0, podając pierwszą gdzie x^2 <= n. Czas działania jestO(n - sqrt n)

Anonimowy:

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

O imieniu:

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

Przykład:

(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 bajtów lub 38 znaków

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

Wypróbuj tutaj.

Kobra - 62

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

Partia - 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 znaków, O (log n)

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

to rozwiązanie implementuje metodę Newtona-Raphsona, chociaż przeszukuje liczby całkowite zamiast liczb zmiennoprzecinkowych. wiki: http://en.wikipedia.org/wiki/Newton%27s_method

złożoność wydaje się dotyczyć O (log n), ale czy jest na to dowód? proszę odpowiedzieć w komentarzach.

J (10)

Bardzo, bardzo, bardzo zainspirowany odpowiedzią @Dennis :

<.@%~^&1.5

I nieco dłużej, ale z lepszą wydajnością (podejrzewam):

<.@(-:&.^.)

floor(halve under log)

Aby wykonać, wprowadzane są wcięte części:

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

APL - 12 znaków, 19 bajtów

{⌊(⍵*1.5)÷⍵}

przykład użycia:

{⌊(⍵*1.5)÷⍵}17

zwraca 4

Wektor testowy

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

zwroty

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

Wypróbuj online

Ogromne podziękowania dla : użytkownika „ssdecontrol” za algorytm

C99 (108 znaków)

Oto moje własne rozwiązanie w C99, które zostało zaadaptowane z algorytmu w artykule na Wikipedii . Jestem pewien, że w innych językach musi być możliwe zrobienie tego znacznie lepiej.

Gra w golfa:

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

Częściowo grał w golfa:

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

Nie golfowany:

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 (w celu spełnienia wymagań liczb 64-bitowych)

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

Implementacja algorytmu Heron of Alexandria ...

Powershell (52) Ograniczony do Int32 (-2 147 483 648 do 2 147 483 647)

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

W tej chwili krzyczę na Powershell, próbując sprawić, by ostatni przypadek testowy zadziałał, ale bez względu na to, co zrobię, Powershell kończy się przy użyciu zmiennej $ _ jako Int32 i nie mogę teraz znaleźć sposobu na obejście tego.

Więc na razie ograniczę swoją odpowiedź. Jeśli znajdę lepszy sposób obsługi uint64s, dokonam edycji. (Nawiasem mówiąc, ostatni przypadek testowy jest zbyt duży dla normalnego typu Int64 Powershell!)

Oto kilka przypadków testowych (z odrobiną dodatkowej wydajności, której użyłem do śledzenia czasu)

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

Nie znam moich O (), ale wydaje się to dość dramatycznym skokiem.

Zastrzeżenie: od 2011 r. R nie miał wbudowanej obsługi 64-bitowych liczb całkowitych, tak jak zakładałem. Te odpowiedzi mogą być niepoprawne pod względem technicznym, ale z drugiej strony R bardzo się zmieniło w ciągu ostatnich 3 lat.

R 85

Za pomocą metody Newtona:

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

który zbiega się kwadratowo. +2 znaki, aby przypisać funkcję do zmiennej w celu przeprowadzenia testu porównawczego:

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

Brutalna siła:

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

I ta sama kontrola:

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

Tani / potęgowanie genialna sztuczka :

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

który również okazuje się być bardzo szybki (choć nie tak szybki jak wbudowany):

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

Tłumaczenie mojego przedłożenia. Powoli, ale poprawnie. O (√n). Testowany na OS X (64-bitowy).

dc, 50 bajtów

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

Rozłożył się i wyjaśnił:

               # 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 bajtów

Moja pierwsza próba gry w golfa kodowego. Wygląda na to, że jest najkrótszy w C, który pasuje do „wydajnego” wymagania w miarę działaniaO(log n) czasie, wykorzystując tylko dodawanie i przesuwanie bitów. Chociaż jestem pewien, że może być jeszcze krótszy ...

Powinno również działać dobrze w przypadku większych wartości całkowitych, o ile a=32część zostanie zmieniona na 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 bez globalnej)

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

Wykorzystuje zmienne globalne jako parametry i zwraca wartość, aby zaoszczędzić miejsce.

Brak wersji globalnej:

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