Problème:

Dans votre choix de langue, écrivez la fonction la plus courte qui renvoie le plancher de la racine carrée d'un entier 64 bits non signé.

Cas de test:

Votre fonction doit fonctionner correctement pour toutes les entrées, mais voici quelques-unes qui aident à illustrer l'idée:

               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

Règles:

1. Vous pouvez nommer votre fonction comme bon vous semble. (Les fonctions sans nom, anonymes ou lambda sont correctes, du moment qu'elles sont en quelque sorte appelables.)
2. Le nombre de caractères est ce qui compte le plus dans ce défi, mais l'exécution est également importante. Je suis sûr que vous pourriez numériser vers le haut de manière itérative pour la réponse en temps O (√n) avec un très petit nombre de caractères, mais le temps O (log (n)) serait vraiment meilleur (c'est-à-dire, en supposant une valeur d'entrée de n, pas un bit de n).
3. Vous voudrez probablement implémenter la fonction en utilisant une arithmétique purement entière et / ou booléenne. Cependant, si vous voulez vraiment utiliser des calculs à virgule flottante, c'est bien tant que vous n'appelez aucune fonction de bibliothèque. Donc, dire simplement return (n>0)?(uint32_t)sqrtl(n):-1;en C est hors limites même si cela produirait le résultat correct. Si vous utilisez l' arithmétique à virgule flottante, vous pouvez utiliser *, /, +, -et exponentiation (par exemple, **ou ^si elle est un opérateur intégré dans votre langue de choix, mais seulement exponentiation des pouvoirs au moins 1 ). Cette restriction vise à empêcher la "tricherie" en appelant sqrt()ou une variante ou en élevant une valeur à la ½ puissance.
4. Si vous utilisez des opérations à virgule flottante (voir # 3), vous n'êtes pas obligé que le type de retour soit entier; seulement que la valeur de retour est un entier, par exemple, floor (sqrt (n)), et pouvoir contenir n'importe quelle valeur 32 bits non signée.
5. Si vous utilisez C / C ++, vous pouvez supposer l'existence de types entiers 64 bits et 32 ​​bits non signés, par exemple, uint64_tet uint32_tcomme défini dans stdint.h. Sinon, assurez-vous simplement que votre type entier est capable de contenir n'importe quel entier non signé 64 bits.
6. Si votre jauge ne prend pas en charge les entiers 64 bits (par exemple, Brainfuck n'a apparemment que la prise en charge des entiers 8 bits), faites de votre mieux avec cela et indiquez la limitation dans le titre de votre réponse. Cela dit, si vous pouvez comprendre comment coder un entier 64 bits et en obtenir correctement la racine carrée en utilisant l'arithmétique primitive 8 bits, alors plus de puissance pour vous!
7. Amusez-vous et soyez créatif!

CJam, 17 (ou 10) octets

{_1.5#\/i}

Essayez-le en ligne en vérifiant les cas de test:

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

Il ne passera pas le dernier cas de test en raison de problèmes d'arrondi, mais comme il 18446744073709551615n'y a pas un entier dans CJam (c'est un gros entier ), nous sommes toujours bons, non?

Sinon, le code suivant (et légèrement plus long) corrigera ces erreurs:

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

Ce n'est plus la solution la plus courte, mais faaast .

Comment ça fonctionne

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

Je crois que c'est l'entrée la plus courte de toute langue qui n'a pas été conçue pour le golf.

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

Il nomme une fonction savec paramètre aet renvoie un moins le premier nombre dont le carré est supérieur à a. Fonctionne incroyablement lentement (O (sqrt n), peut-être?).

Golfscript, 17 caractères

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

Je pouvais nommer ma fonction comme je le souhaitais, mais j'ai décidé de ne pas la nommer du tout. Ajoutez deux caractères pour le nommer, ajoutez trois pour le nommer et ne le laissez pas sur la pile, soustrayez un caractère si la fourniture d'un programme complet est OK.

Cette abomination ne s'exécute pas en temps logarithmique dans la valeur de l'entrée, pas en temps O (sqrt n), il faut un temps linéaire de coqueluche pour produire le résultat. Cela prend aussi beaucoup d'espace. Absolument horrible. Mais ... c'est du code-golf.

L'algorithme est:

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

Pyth , 14 caractères

DsbR;fgb*TTL'b

Fournit une fonction nommée, s, qui calcule la racine carrée en filtrant la liste de 0 à n pour le carré étant plus grand que l'entrée, puis imprime le dernier de ces nombres. N'utilise aucune exponentiation ou flotteur.

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

Exemple d'utilisation:

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]

Rétine (sans compétition - La langue est plus récente que le défi), 43

En travaillant sur cette réponse , il m'est venu à l'esprit qu'une méthode similaire peut être utilisée pour calculer les racines carrées entières en utilisant la rétine:

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

1+

Cela repose sur le fait que les carrés parfaits peuvent être exprimés par 1+3+5+7+..., et par corollaire que le nombre de termes dans cette expression est la racine carrée.

Essayez-le en ligne. (Première ligne ajoutée pour permettre l'exécution de plusieurs tests.)

Évidemment, en raison de la conversion décimale en unaire, cela ne fonctionnera que pour des entrées relativement petites.

Perl, 133 caractères

Pas le plus court de loin, mais utilise un algorithme chiffre par chiffre pour gérer n'importe quelle entrée de taille et s'exécute en temps O (log n). Convertit librement entre des nombres sous forme de chaînes et des nombres sous forme de nombres. Étant donné que le plus grand produit possible est la racine jusqu'à présent avec le carré d'un seul chiffre, il devrait être capable de prendre la racine carrée de 120 bits ou plus sur un système 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}

Décompressé, c'est-à-dire:

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)

Il calcule la racine carrée en utilisant une méthode à point fixe. Il converge en 36 étapes maximum (pour 2 ^ 64-1 comme argument) et vérifie ensuite s'il s'agit de la plus basse des racines entières «possibles». Comme il utilise toujours 36 itérations, il a un temps d'exécution de O (1) = P

L'argument est supposé être 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

Octave:

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 caractères

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)

L'approche récursive naturelle. Compte les racines carrées potentielles jusqu'à ce que leur carré soit trop élevé, puis diminue de 1. Utilisez Stackless Python si vous craignez de dépasser la profondeur de la pile.

L' and/oridiome est équivalent à l'opérateur ternaire comme

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

Edit: je peux au lieu obtenir 25 caractères en exploitant la règle « vous pouvez utiliser *, /, +, -et exponentiation (par exemple, **ou ^si elle est un opérateur intégré dans votre langue de choix, mais seulement exponentiation des pouvoirs au moins 1). " (Edit: Apparemment, Dennis a déjà trouvé et exploité cette astuce.)

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

J'utilise l'opérateur //de division entière de Python 3 pour arrondir. Malheureusement, je passe beaucoup de caractères pour que le cas n=0ne donne pas une division par 0 erreur. Sinon, je pourrais faire 18 caractères

lambda n:n**1.5//n 

Les règles ne disaient pas non plus que la fonction devait être nommée (selon la façon dont vous interprétez "Vous pouvez nommer votre fonction comme vous voulez."), Mais si c'est le cas, ce sont deux autres caractères.

C99 (58 caractères)

Ceci est un exemple de réponse que je ne considérerais pas comme une bonne, même si elle est intéressante pour moi du point de vue du code de golf car elle est tellement perverse, et je pensais juste que ce serait amusant de jeter dans le mélange:

Original: 64 caractères

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

La raison pour laquelle celui-ci est terrible est qu'il s'exécute en temps O (√n) plutôt qu'en temps O (log (n)). (Où n est la valeur d'entrée.)

Modifier: 63 caractères

Changer le r-1to --ret le joindre à return:

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

Modifier: 62 caractères

Déplacement de l'incrément de boucle à l'intérieur de la partie conditionnelle de la boucle (remarque: cela a un comportement non garanti car l'ordre des opérations par rapport à l'opérateur de pré-incrémentation est spécifique au compilateur):

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

Modifier: 60 caractères

Ajout d'un typedefpour masquer uint64_t(crédit à l'utilisateur technosaurus pour cette suggestion).

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

Modifier: 58 caractères

Maintenant, le deuxième paramètre doit être passé à 0 lors de l'invocation de la fonction, par exemple, r(n,0)au lieu de simplement r(n). Ok, pour la vie de moi, à ce stade, je ne vois pas comment comprimer cela plus loin ... n'importe qui?

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

Golfscript - 14 caractères

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

Trouvez le plus petit nombre iinférieur à l'entrée npour laquelle n < i*i. Retour i - 1.

C'est à dire [0..n-1].first(i => n < i*i) - 1

Explication pour ceux qui ne connaissent pas également Golfscript, pour un exemple d'appel avec entrée 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 octets

Ce n'est pas le code le plus court du monde, mais il s'exécute en O (log n) et sur des nombres de taille arbitraire:

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)

Cela fait une recherche binaire de la plage [0..n] pour trouver la meilleure approximation inférieure à sqrt (n). Voici une version non golfée:

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

Edit: enregistré deux octets en remplaçant les clauses "sinon" par "0 <1" comme une version plus courte de "True", et quelques autres en insérant g * g.

De plus, si vous êtes satisfait de O (sqrt (n)), vous pouvez simplement faire

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

pour 35 personnages, mais qu'est-ce que c'est amusant?

Edit 2: Je viens de réaliser que puisque les paires sont triées par ordre de dictionnaire, au lieu de faire min2Cycle. carte fst, je peux juste faire fst. min2Cycle. Dans le code golfed, cela se traduit par le remplacement de f $ map fst par fst $ f, économisant 4 octets supplémentaires.

Edit 3: sauvé six octets supplémentaires grâce à proudhaskeller!

JavaScript 91 88 86: optimisé pour la vitesse

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: non optimisé pour la vitesse

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

Voici un JSFiddle: http://jsfiddle.net/rmadhuram/1Lnjuo4k/

C 95 97

Modifier Typedef, suggéré par @Michaelangelo

Cela devrait être plus ou moins une implémentation simple de l'algorithme Heron. La seule bizarrerie réside dans le calcul du débordement d'entier moyen évitant: a = (m + n) / 2 ne fonctionne pas pour les nombres 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

Comme il s'agit d'un code-golf (et je suis horrible avec les mathématiques), et que l'exécution n'est qu'une suggestion, j'ai fait l'approche naïve qui s'exécute en temps linéaire:

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

( test sur dotnetfiddle )

Bien sûr, c'est terriblement lent pour les entrées plus importantes.

Clojure - 51 ou 55 octets

Vérifie tous les nombres de n à 0, donnant le premier où x^2 <= n. Le temps d'exécution estO(n - sqrt n)

Anonyme:

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

Nommé:

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

Exemple:

(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 octets ou 38 caractères

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

Essayez-le ici.

Cobra - 62

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

Lot - 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 caractères, O (log n)

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

cette solution implémente la méthode newton-raphson, bien qu'elle recherche des entiers au lieu de flottants. wiki: http://en.wikipedia.org/wiki/Newton%27s_method

la complexité semble concerner O (log n), mais y en a-t-il une preuve? veuillez répondre dans les commentaires.

J (10)

Très, très, très inspiré par la réponse de @Dennis :

<.@%~^&1.5

Et un peu plus long, mais avec de meilleures performances (je suppose):

<.@(-:&.^.)

floor(halve under log)

Pour exécuter, des pièces en retrait sont entrées:

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

APL - 12 caractères, 19 octets

{⌊(⍵*1.5)÷⍵}

exemple d'utilisation:

{⌊(⍵*1.5)÷⍵}17

renvoie 4

Vecteur de test

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

Retour

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

Essayez en ligne

Un grand merci à : l'utilisateur "ssdecontrol" pour l'algorithme

C99 (108 caractères)

Voici ma propre solution en C99, qui est adaptée d'un algorithme dans un article sur Wikipedia . Je suis sûr qu'il doit être possible de faire bien mieux que cela dans d'autres langues.

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

Partiellement golfé:

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

Non golfé:

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 (pour se conformer à l'exigence de nombres 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))

Implémentation de l' algorithme de Heron of Alexandria ...

Powershell (52) Limité à Int32 (-2.147.483.648 à 2.147.483.647)

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

Je crie sur Powershell en ce moment en essayant de faire fonctionner le dernier cas de test, mais peu importe ce que je fais, Powershell finit par utiliser la variable de pipeline $ _ en tant qu'Int32, et je ne trouve pas de moyen de le contourner pour le moment.

Je vais donc limiter ma réponse pour l'instant. Si je peux trouver une meilleure façon de gérer les uint64, je les modifierai. (Le dernier cas de test est trop gros pour le type Int64 normal de Powershell, au fait!)

Voici quelques cas de test (avec un peu de sortie supplémentaire, j'ai utilisé pour suivre le temps)

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

Je ne connais pas mes O (), mais cela semble être un saut assez dramatique.

Mise en garde: en 2011, R n'avait pas de support intégré pour les entiers 64 bits comme je l'avais supposé. Ces réponses peuvent être invalides sur cette technicité, mais là encore, R a beaucoup changé au cours des 3 dernières années.

R, 85

En utilisant la méthode 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)}

qui converge quadratique. +2 caractères pour affecter la fonction à une variable pour l'analyse comparative:

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

Force brute:

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

Et le même contrôle:

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

L' astuce d'exponentiation bon marché / brillant :

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

qui se trouve également être très rapide (bien que pas aussi rapide que le intégré):

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

Traduction de ma soumission. Lent mais correct. O (√n). Testé sous OS X (64 bits).

dc, 50 octets

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

Espacé et expliqué:

               # 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 136 octets

Mon premier essai au code golf. Il semble que ce soit le plus court en C qui réponde à l'exigence «efficace», car il s'exécute dans le O(log n)temps, en utilisant uniquement l'addition et les décalages de bits. Bien que je sois sûr qu'il pourrait être encore plus court ...

Cela devrait fonctionner très bien pour les valeurs entières plus grandes aussi longtemps que la a=32pièce est remplacée par 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 sans global)

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

Il utilise des variables globales comme paramètre et renvoie une valeur pour économiser de l'espace.

Pas de version globale:

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