Problema:

Na sua escolha de idioma, escreva a função mais curta que retorna o piso da raiz quadrada de um número inteiro de 64 bits não assinado.

Casos de teste:

Sua função deve funcionar corretamente para todas as entradas, mas aqui estão algumas que ajudam a ilustrar a idéia:

               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

Regras:

1. Você pode nomear sua função como quiser. (As funções sem nome, anônima ou lambda são boas, desde que sejam de alguma forma chamadas.)
2. A contagem de caracteres é o que mais importa nesse desafio, mas o tempo de execução também é importante. Tenho certeza de que você poderia procurar iterativamente para cima a resposta em tempo O (√n) com uma contagem de caracteres muito pequena, mas o tempo O (log (n)) seria realmente melhor (ou seja, assumindo um valor de entrada n, não um comprimento de bit de n).
3. Você provavelmente desejará implementar a função usando puramente inteiro e / ou aritmética booleana. No entanto, se você realmente deseja usar cálculos de ponto flutuante, tudo bem, desde que você não chame nenhuma função de biblioteca. Portanto, simplesmente dizer return (n>0)?(uint32_t)sqrtl(n):-1;em C está fora dos limites, mesmo que produza o resultado correto. Se você estiver usando aritmética de ponto flutuante, você pode usar *, /, +, -, e exponenciação (por exemplo, **ou ^se é um built-in operador no idioma de sua escolha, mas a exponenciação única de poderes não inferior a 1 ). Essa restrição é para evitar "trapaça" chamando sqrt()ou uma variante ou aumentando um valor para a ½ potência.
4. Se você estiver usando operações de ponto flutuante (consulte # 3), não será necessário que o tipo de retorno seja inteiro; apenas que o valor de retorno seja um número inteiro, por exemplo, floor (sqrt (n)), e seja capaz de manter qualquer valor de 32 bits não assinado.
5. Se você estiver usando C / C ++, poderá assumir a existência de tipos inteiros de 64 e 32 bits não assinados, por exemplo, uint64_te uint32_tconforme definido em stdint.h. Caso contrário, verifique se o tipo inteiro é capaz de conter qualquer número inteiro não assinado de 64 bits.
6. Se o seu idioma não suportar números inteiros de 64 bits (por exemplo, o Brainfuck aparentemente possui apenas o número inteiro de 8 bits), faça o seu melhor com isso e indique a limitação no título da resposta. Dito isso, se você puder descobrir como codificar um número inteiro de 64 bits e obter corretamente a raiz quadrada usando aritmética primitiva de 8 bits, terá mais poder para você!
7. Divirta-se e seja criativo!

CJam, 17 (ou 10) bytes

{_1.5#\/i}

Experimente online verificando os casos de teste:

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

Ele não passará no último caso de teste devido a problemas de arredondamento, mas como 18446744073709551615não é um número inteiro no CJam (é um número inteiro grande ), ainda somos bons, certo?

Caso contrário, o código a seguir (e um pouco mais longo) corrigirá esses erros:

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

Não é mais a solução mais curta, mas é uma faaast .

Como funciona

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

Acredito que esta é a entrada mais curta de qualquer idioma que não foi projetado para jogar golfe.

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

Nomeia uma função scom parâmetro ae retorna um menos o primeiro número cujo quadrado é maior que a. Corre incrivelmente devagar (O (sqrt n), talvez?).

Golfscript, 17 caracteres

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

Eu poderia nomear minha função da maneira que quisesse, mas decidi não nomeá-la. Adicione dois caracteres para nomear, adicione três para nomear e não deixe na pilha; subtraia um caractere se o fornecimento de um programa completo estiver OK.

Essa abominação não é executada no tempo logarítmico no valor da entrada, e não no tempo O (sqrt n), leva uma quantidade linear de tempo para produzir o resultado. Também ocupa muito espaço. Absolutamente horrendo. Mas ... isso é código-golfe.

O algoritmo é:

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

Pitão , 14 caracteres

DsbR;fgb*TTL'b

Fornece uma função nomeada, s, que calcula a raiz quadrada filtrando a lista de 0 a n para o quadrado ser maior que a entrada e, em seguida, imprime o último número desse tipo. Não usa exponenciação ou flutua.

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

Exemplo de uso:

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 (não concorrente - O idioma é mais novo que o desafio), 43

Enquanto trabalhava nessa resposta , ocorreu-me que um método semelhante pode ser usado para calcular raízes quadradas inteiras usando retina:

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

1+

Isso se baseia no fato de que quadrados perfeitos podem ser expressos como 1+3+5+7+...e pelo corolário que o número de termos nessa expressão é a raiz quadrada.

Experimente online. (Primeira linha adicionada para permitir a execução de vários casos de teste.)

Obviamente, devido à conversão decimal em unária, isso funcionará apenas para entradas relativamente pequenas.

Perl, 133 caracteres

Não é o menor de longe, mas usa um algoritmo dígito por dígito para lidar com qualquer entrada de tamanho e é executado no tempo O (log n). Converte livremente entre números como seqüências de caracteres e números como números. Como o maior produto possível é a raiz até agora com o quadrado de um único dígito, ele deve conseguir a raiz quadrada de até 120 ou mais números em um sistema de 64 bits.

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}

Descomprimido, ou seja:

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

Ele elabora a raiz quadrada usando um método de ponto fixo. Ele converge no máximo 36 etapas (para 2 ^ 64-1 como argumento) e depois verifica se é a mais baixa das raízes inteiras 'possíveis'. Como sempre usa 36 iterações, possui um tempo de execução de O (1) = P

O argumento é assumido como 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

Oitava:

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 caracteres

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)

A abordagem recursiva natural. Conta as raízes quadradas em potencial até o quadrado ficar muito alto e diminui em 1. Use o Stackless Python se você estiver preocupado em exceder a profundidade da pilha.

O and/oridioma é equivalente ao operador ternário como

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

Edit: eu posso em vez de obter 25 caracteres , explorando a regra ", você pode usar *, /, +, -, e exponenciação (por exemplo, **ou ^se é uma exponenciação built-in operador no idioma de sua escolha, mas apenas de poderes não inferior a 1). " (Editar: Aparentemente, Dennis já encontrou e explorou esse truque.)

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

Eu uso o operador //de divisão inteira do Python 3 para arredondar para baixo. Infelizmente, gasto muitos caracteres para que o caso n=0não dê uma divisão por 0 erro. Se não fosse por isso, eu poderia fazer 18 caracteres

lambda n:n**1.5//n 

As regras também não diziam que a função tinha que ser nomeada (dependendo de como você interpreta "Você pode nomear sua função como quiser"), mas, se o fizer, serão mais dois caracteres.

C99 (58 caracteres)

Este é um exemplo de resposta que eu não consideraria uma boa, embora seja interessante para mim do ponto de vista do código de golfe, porque é muito perversa, e eu apenas pensei que seria divertido jogar na mistura:

Original: 64 caracteres

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

A razão pela qual este é terrível é que ele é executado no tempo O (√n) em vez do tempo O (log (n)). (Onde n é o valor de entrada.)

Editar: 63 caracteres

Alterando o r-1para --re confinando-o para return:

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

Editar: 62 caracteres

Movendo o incremento do loop para dentro da parte condicional do loop (nota: isso tem um comportamento não garantido, porque a ordem das operações com relação ao operador de pré-incremento é específica do compilador):

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

Editar: 60 caracteres

Adicionando a typedefpara ocultar uint64_t(crédito ao usuário technosaurus por esta sugestão).

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

Editar: 58 caracteres

Agora exigindo que o segundo parâmetro seja passado como 0 na invocação da função, por exemplo, em r(n,0)vez de apenas r(n). Ok, para a minha vida, neste momento não consigo ver como comprimir isso mais ... alguém?

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

Golfscript - 14 caracteres

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

Encontre o menor número imenor que a entrada npara a qual n < i*i. Retorno i - 1.

Ou seja, [0..n-1].first(i => n < i*i) - 1

Explicação para aqueles que também não conhecem o Golfscript, para exemplo de chamada com entrada 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

Não é o código mais curto do mundo, mas é executado em O (log n) e em números de tamanho arbitrário:

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)

Isso faz uma pesquisa binária do intervalo [0..n] para encontrar a melhor aproximação mais baixa ao sqrt (n). Aqui está uma versão não destruída:

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

Editar: salvou dois bytes substituindo as cláusulas "caso contrário" por "0 <1" como uma versão mais curta de "True" e mais algumas inserindo g * g.

Além disso, se você está feliz com O (sqrt (n)), você pode simplesmente fazer

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

para 35 caracteres, mas que graça é essa?

Edit 2: Acabei de perceber que, uma vez que os pares são classificados por ordem do dicionário, em vez de fazer min2Cycle. mapear fst, eu posso apenas fazer fst. min2Cycle. No código golfed, isso significa substituir f $ map fst por fst $ f, economizando mais 4 bytes.

Editar 3: economizou mais seis bytes graças ao proudhaskeller!

JavaScript 91 88 86: Otimizado para velocidade

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: não otimizado para velocidade

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

Aqui está um JSFiddle: http://jsfiddle.net/rmadhuram/1Lnjuo4k/

C 95 97

Editar Typedef, sugerido por @Michaelangelo

Isso deve ser mais ou menos uma implementação direta do algoritmo Heron. O único problema é calcular a média evitando o excesso de números inteiros: a = (m + n) / 2 não funciona para números 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

Como esse é um código-golfe (e eu sou péssimo em matemática), e o tempo de execução é apenas uma sugestão, eu fiz a abordagem ingênua que é executada em tempo linear:

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

( teste no dotnetfiddle )

Obviamente, é terrivelmente lento para entradas maiores.

Clojure - 51 ou 55 bytes

Verifica todos os números de n a 0, dando o primeiro onde x^2 <= n. O tempo de execução éO(n - sqrt n)

Sem nome:

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

Nomeado:

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

Exemplo:

(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 ou 38 caracteres

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

Experimente aqui.

Cobra - 62

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

Lote - 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 caracteres, O (log n)

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

esta solução implementa o método newton-raphson, embora ele procure números inteiros em vez de números flutuantes. wiki: http://en.wikipedia.org/wiki/Newton%27s_method

a complexidade parece ser sobre O (log n), mas há uma prova disso? por favor responda nos comentários.

J (10)

Muito, muito, muito inspirado pela resposta de @Dennis :

<.@%~^&1.5

E um pouco mais, mas com melhor desempenho (suspeito):

<.@(-:&.^.)

floor(halve under log)

Para executar, são inseridas peças recuadas:

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

APL - 12 caracteres, 19 bytes

{⌊(⍵*1.5)÷⍵}

exemplo de uso:

{⌊(⍵*1.5)÷⍵}17

retorna 4

Vetor de teste

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

retorna

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

Experimente on-line

Muito obrigado a : usuário "ssdecontrol" do algoritmo

C99 (108 caracteres)

Aqui está minha própria solução no C99, que é adaptada de um algoritmo em um artigo na Wikipedia . Tenho certeza de que deve ser possível fazer muito melhor que isso em outros idiomas.

Golfe:

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

Parcialmente jogado:

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 (para atender aos requisitos de números de 64 bits)

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

Implementando o algoritmo de Heron de Alexandria ...

Powershell (52) Limitado ao Int32 (-2.147.483.648 a 2.147.483.647)

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

Estou gritando com o Powershell agora, tentando fazer com que o último caso de teste funcione, mas não importa o que eu faça, o Powershell acaba usando a variável de pipeline $ _ como um Int32, e não consigo encontrar uma maneira de contornar isso agora.

Então, vou limitar minha resposta por enquanto. Se eu conseguir encontrar uma maneira melhor de lidar com o uint64s, editarei. (O último caso de teste é muito grande para o tipo Int64 normal do Powershell, a propósito!)

Aqui estão alguns casos de teste (com um pouco de saída extra que eu costumava acompanhar o tempo)

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

Não conheço meus O (), mas isso parece um salto bastante dramático.

Advertência: a partir de 2011, o R não tinha suporte interno para números inteiros de 64 bits, como eu supunha. Essas respostas podem ser inválidas nesse aspecto técnico, mas, novamente, o R mudou muito nos últimos 3 anos.

R, 85

Usando o método de 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)}

que converge quadraticamente. +2 caracteres para atribuir a função a uma variável para 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

Força bruta:

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

E a mesma verificação:

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

O truque barato / brilhante de exponenciação :

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

que também é muito rápido (embora não tão rápido quanto o interno):

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

Tradução da minha quarta submissão. Lento, mas correto. O (√n). Testado no OS X (64 bits).

dc, 50 bytes

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

Espaçados e explicados:

               # 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

Minha primeira tentativa no código de golfe. Parece que é o menor em C que se encaixa no requisito "eficiente", pois é executado no O(log n)tempo, usando apenas mudanças de adição e de bits. Embora eu tenha certeza que poderia ser mais curto ainda ...

Deve funcionar muito bem para valores inteiros maiores também, desde que a a=32peça seja alterada para 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 sem global)

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

Ele usa variáveis ​​globais como parâmetro e retorna valor para economizar espaço.

Nenhuma versão 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;
}