# Integer square root of integer

Problem:

In your choice of language, write the shortest function that returns the floor of the square root of an unsigned 64-bit integer.

Test cases:

Your function must work correctly for all inputs, but here are a few which help illustrate the idea:

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

Rules:

1. You can name your function anything you like. (Unnamed, anonymous, or lambda functions are fine, as long as they are somehow callable.)
2. Character count is what matters most in this challenge, but runtime is also important. I'm sure you could scan upwards iteratively for the answer in O(√n) time with a very small character count, but O(log(n)) time would really be better (that is, assuming an input value of n, not a bit-length of n).
3. You will probably want to implement the function using purely integer and/or boolean artithmetic. However, if you really want to use floating-point calculations, then that is fine so long as you call no library functions. So, simply saying `return (n>0)?(uint32_t)sqrtl(n):-1;` in C is off limits even though it would produce the correct result. If you're using floating-point arithmetic, you may use `*`, `/`, `+`, `-`, and exponentiation (e.g., `**` or `^` if it's a built-in operator in your language of choice, but only exponentiation of powers not less than 1). This restriction is to prevent "cheating" by calling `sqrt()` or a variant or raising a value to the ½ power.
4. If you're using floating-point operations (see #3), you aren't required that the return type be integer; only that that the return value is an integer, e.g., floor(sqrt(n)), and be able to hold any unsigned 32-bit value.
5. If you're using C/C++, you may assume the existence of unsigned 64-bit and 32-bit integer types, e.g., `uint64_t` and `uint32_t` as defined in `stdint.h`. Otherwise, just make sure your integer type is capable of holding any 64-bit unsigned integer.
6. If your langauge does not support 64-bit integers (for example, Brainfuck apparently only has 8-bit integer support), then do your best with that and state the limitation in your answer title. That said, if you can figure out how to encode a 64-bit integer and correctly obtain the square root of it using 8-bit primitive arithmetic, then more power to you!
7. Have fun and get creative!
-
"but O(log₄(n)) time would really be better." - how much better? Is there a bonus? Is that a hard requirement? Is it essentially a separate challenge? Is that just a nice idea that doesn't really affect the scoring? – Jan Dvorak Jul 26 '14 at 20:34
Normally one uses the size of the input rather than the input value to derive algorithmic complexity. In that sense the increment-and-retry algorithm is exponential in speed. – Jan Dvorak Jul 26 '14 at 20:50
Umm... `O(log_2 n) === O(log_4 n)`. `log_4(n) = log_2(n) / log_2(2) = log_2(n) / 2` – Jan Dvorak Jul 26 '14 at 20:50
Does 2/4 count? – Milo Jul 27 '14 at 1:02
Most floating-point data types don't have the precision needed for this task anyway. 53 significant bits isn't enough for the whole input range. – user2357112 Jul 27 '14 at 2:32

# CJam, 17 (or 10) bytes

``````{_1.5#\/i}
``````

Try it online by verifying the test cases:

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

It won't pass the last test case because of rounding issues, but since `18446744073709551615` isn't an Integer in CJam (it's a Big Integer), we're still good, right?

If not, the following (and slightly longer) code will correct those errors:

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

Not the shortest solution anymore, but faaast.

### How it works

``````__    " 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. ";
``````
-
Hahaha! oops, ok, you got me on a technicality there. I should have said no fractional powers. But your code does indeed obey the stated rules, so I'm upvoting it. :) – Todd Lehman Jul 27 '14 at 0:30
Does CJam have arbitrary-precision decimals, to cover the whole input range? – isaacg Jul 27 '14 at 3:16
Also, nice hack of using NaN -> 0 on cast to int. – isaacg Jul 27 '14 at 3:28
+1 for exploiting the rules as written. – R.. Jul 27 '14 at 23:27
Neat idea, it can also be represented in J in the exact same character count: `<.@%~^&1.5`. Can I post this as an separate answer (since it's basically an exact port of yours)? – ɐɔıʇǝɥʇuʎs Sep 1 '14 at 19:49

I believe that this is the shortest entry from any language that wasn't designed for golfing.

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

It names a function `s` with parameter `a` and returns one minus the first number whose square is greater than `a`. Runs incredibly slowly (O(sqrt n), maybe?).

-
Wouldn't a list index (`[...]!!0`) be shorter than head? – isaacg Jul 28 '14 at 6:39
@isaacg Yes, it would. Thanks :-) – Zaq Jul 28 '14 at 15:35

### Golfscript, 17 characters

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

I could name my function any way I liked, but I decided not to name it at all. Add two characters to name it, add three to name it and not leave it on the stack, subtract one character if providing a full program is OK.

This abomination runs not in logaritmic time in the value of the input, not in O(sqrt n) time, it takes a whooping linear amount of time to produce the result. It also takes that much space. Absolutely horrendous. But... this is code-golf.

The algorithm is:

``````n => [0..n].filter(x => x*x < n+1).length - 1
``````
-
I love it!! Nice work! That is beautifully perverse. – Todd Lehman Jul 26 '14 at 21:10

# Pyth, 14 characters

``````DsbR;fgb*TTL'b
``````

Provides a named function, s, which calculates the square root by filtering the list from 0 to n for the square being larger than the input, then prints the last such number. Uses no exponentiation or floats.

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

Example usage:

``````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-competing - Language is newer than the challenge), 43

While working on this answer, it occurred to me that a similar method can be used to calculate integer square roots using retina:

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

1+
``````

This relies on the fact that perfect squares may be expressed as `1+3+5+7+...`, and by corollary that the number of terms in this expression is the square root.

Try it online. (First line added to allow multiple testcases to be run.)

Obviously due to the decimal to unary conversion, this will only work for relatively small inputs.

-
(Language is newer than the challenge) – mbomb007 Jun 13 at 21:44
@mbomb007 Fair enough - Headline edited. This answer is definitely in the "because it can be done" category, and not meant to compete in the challenge in any meaningful way. – Digital Trauma Jun 13 at 21:50
– mbomb007 Jun 14 at 16:17

## Perl, 133 characters

Not the shortest by far, but uses a digit-by-digit algorithm to handle any size input, and runs in O(log n) time. Converts freely between numbers-as-strings and numbers-as-numbers. Since the largest possible product is the root-so-far with the square of a single digit, it should be able to take the square root of up to 120-bit or so numbers on a 64-bit system.

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

Decompressed, that is:

``````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;
}
``````
-
Nice! I was wondering when someone would post a Perl answer. BTW, does it work to say `if length%2` instead of `if(length)%2`? That would shave off 1 character. Also, would it work to say `\$y=\$z,\$d=\$_ if` instead of `(\$y,\$d)=(\$z,\$_)if`? I think that would shave off 3 more characters. – Todd Lehman Jul 27 '14 at 22:45
And this is getting a bit perverse, but I think you can shave off 1 more yet by rewriting the `for` loop as: `\$a<(\$z=\$_*(20*\$r+\$_))or\$y=\$z,\$d=\$_ for(1..9);` – Todd Lehman Jul 27 '14 at 23:02
The first suggestion doesn't work (it tries to take the length of a hash named `%2`), but the others are valid. I'll work them in. – hobbs Jul 28 '14 at 1:26
@ToddLehman postfix `for` doesn't need parentheses; adding that to your suggestions nets me 6 characters total. Thanks! – hobbs Jul 28 '14 at 1:32

# Matlab (56) / Octave (55)

It works out the square root by using a fixed point method. It converges in maximal 36 steps (for 2^64-1 as argument) and then checks if it is the lower one of the 'possible' integer roots. As it always uses 36 iterations it has a runtime of O(1) =P

The argument is assumed to be 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
``````
-
This is a new method to me, and it happens to be pretty cool. +1 – Seeq Jul 28 '14 at 7:34
It is basically the en.wikipedia.org/wiki/… which is one of the earliest known numerical methods that is estimated to be around 3700 years old. It can be justified by the en.wikipedia.org/wiki/Banach_fixed-point_theorem which has a surprisingly easy proof, it's really nice=) – flawr Jul 28 '14 at 11:13

### Ruby — 36 characters

``````s=->n{g=n;g=(g+n/g)/2 while g*g>n;g}
``````
-
Nicely done! What is the worst-case execution time? – Todd Lehman Jul 29 '14 at 19:06
What about in the event that g*g < n and the answer is still not close to the value desired? Won't the script just stop? – WallyWest Jul 30 '14 at 6:49
@ToddLehman I honestly don't know. :-/ This is the Babylonian method. Here's what appears to be a good proof of the average complexity. The initial guess of the number itself is pretty bad, but I'd need to sit down and really grok that proof to understand the worst case. Will give it a go when I have some more free time. :-) – O-I Aug 2 '14 at 22:53
@WallyWest My understanding is that the `while` loop terminates precisely when g converges to floor(√n) which is the desired value. Do you see any case where this would not be true? – O-I Aug 2 '14 at 23:24

# Python (39)

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

The natural recursive approach. Counts up potential square roots until their square is too high, then goes down by 1. Use Stackless Python if you're worried about exceeding the stack depth.

The `and/or` idiom is equivalent to the ternary operator as

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

Edit: I can instead get 25 chars by exploiting the rule "you may use `*`, `/`, `+`, `-`, and exponentiation (e.g., `**` or `^` if it's a built-in operator in your language of choice, but only exponentiation of powers not less than 1)." (Edit: Apparently Dennis already found and exploited this trick.)

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

I use the integer division operator `//` of Python 3 to round down. Unfortunately, I spend a lot of characters for the case `n=0` not to give a division by 0 error. If not for it, I could do 18 chars

``````lambda n:n**1.5//n
``````

The rules also didn't say the function had to be named (depending how you interpret "You can name your function anything you like."), but if it does, that's two more characters.

-
— Thanks, I'll clarify that. It only has to be a function. It doesn't have to be named. So, lambda functions are fine. I would have mentioned this from the start if I'd thought of it. I was thinking too much in terms of C when I posted the question. – Todd Lehman Jul 27 '14 at 4:33

## C99 (58 characters)

This is an example of an answer I would not consider to be a good one, although it's interesting to me from a code golf point of view because it's so perverse, and I just thought it would be fun to throw into the mix:

Original: 64 characters

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

The reason this one is terrible is that it runs in O(√n) time rather than O(log(n)) time. (Where n is the input value.)

Edit: 63 characters

Changing the `r-1` to `--r` and abutting it to `return`:

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

Edit: 62 characters

Moving the loop increment to inside the conditional portion of the loop (note: this has unguaranteed behavior because the order of operations with respect to the preincrement operator is compiler-specific):

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

Edit: 60 characters

Adding a `typedef` to hide `uint64_t` (credit to user technosaurus for this suggestion).

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

Edit: 58 characters

Now requiring second parameter being passed as 0 in invocation of the function, e.g., `r(n,0)` instead of just `r(n)`. Ok, for the life of me, at this point I can't see how to compress this any further...anyone?

``````typedef uint64_t Z;Z r(Z n,Z r){for(;n/++r/r;);return--r;}
``````
-
If you are willing to call it C++ and decrement rather than increment you would be able to shave off a couple of characters: `uint64_t s(uint64_t n){for(uint64_t r=n;--n>r/n;);return n;}`. – Fors Jul 27 '14 at 0:29
@Fors — Nice approach! Unfortunately, won't that cause a divide-by-zero for input of 1? Also, what will it do for an input of 0? Because `--n` when `n==0` would be –1, and these are unsigned values, so –1 would be 2⁶⁴–1. – Todd Lehman Jul 27 '14 at 0:45
`#define Z uint64_t` ... or typedef will save a couple – technosaurus Jul 28 '14 at 6:08
@technosaurus — Ah yes, that saves 2. Thank you. :-) – Todd Lehman Jul 28 '14 at 6:33
The expression `n/++r/r` has undefined behavior.... – aschepler Jul 29 '14 at 21:45

## Golfscript - 14 character

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

Find the smallest number `i` less than the input `n` for which `n < i*i`. Return `i - 1`.

I.e. `[0..n-1].first(i => n < i*i) - 1`

Explanation for those who don't know Golfscript as well, for sample call with 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
``````
-
Ooh, that's 3 characters shorter than the previous best Golfscript answer. Nice work! – Todd Lehman Jul 30 '14 at 1:30
Fixing this to give the correct answer for input `1` probably takes two chars. – Peter Taylor Sep 3 '14 at 13:57

Not the shortest code in the world, but it does run in O(log n), and on arbitrary-sized numbers:

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

This does a binary search of the range [0..n] to find the best lower approximation to sqrt(n). Here is an 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
``````

Edit: Saved two bytes by replacing the "otherwise" clauses with "0<1" as a shorter version of "True", and a few more by inlining g*g.

Also, if you are happy with O(sqrt(n)) you could simply do

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

for 35 characters, but what fun is that?

Edit 2: I just realized that since pairs are sorted by dictionary order, instead of doing min2Cycle . map fst, I can just do fst . min2Cycle. In the golfed code, that translates to replacing f\$map fst with fst\$f, saving 4 more bytes.

Edit 3: Saved six more bytes thanks to proudhaskeller!

-
you can replace (div x 2 + rem x 2) with div(x+1)2, at your "half" function – proud haskeller Jul 30 '14 at 4:31
Thanks, that got it down to a nice even number! – Matt Noonan Jul 30 '14 at 22:53
I actually have a solution of my own which has 49 characters, and solves in O(log n), but i only have 2 upvotes ;-(. I don't understand why – proud haskeller Jul 31 '14 at 6:08

JavaScript 91 88 86: Optimized for speed

``````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 optimized for speed

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

-
Welcome to PPCG! You can use <s>91</s> <s>88</s> for strikethrough. I tried making the edit but you were editing at the same time so I'll let you do it. – Rainbolt Aug 8 '14 at 18:02
Thanks @Rainbolt. I made the edit. – Rajkumar Madhuram Aug 8 '14 at 18:03
Or you could do it in 41 characters like this: `function s(n){for(a=1;++a*a<n;);return a}` – Rhubarb Custard Sep 1 '14 at 21:24

# C 95 97

Edit Typedef, suggested by @Michaelangelo

This should be more or less a straightforward implementation of Heron algorithm. The only quirk is in computing the average avoiding integer overflow: a=(m+n)/2 does not work for biiiig numbers.

``````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;
}
``````
-
Nice work with the overflow avoidance —— not only for correctly doing it, but taking care to think about it in the first place and test it. Definitely appreciated. – Todd Lehman Jul 27 '14 at 19:25
BTW, it's funny how expensive division can be on some CPUs. Even though this algorithm executes in roughly half as many steps as the abacus algorithm, it has a runtime that's about 5 times slower than the abacus algorithm when I benchmark it on my Core i7 CPU, which doesn't like doing division. Anyway, but runtime isn't important here — only size. :) So nice work!!! – Todd Lehman Jul 27 '14 at 19:29

# C# 6462 55

Since this is a (and I'm terrible with maths), and runtime is merely a suggestion, I've done the naive approach that runs in linear time:

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

Of course, it's terribly slow for larger inputs.

-
You might be able to shave off a character by changing `return i-1` to `return--i`? – Todd Lehman Jul 27 '14 at 18:39
In the expression `i*i<=a`, is that guaranteed to be integer arithmetic of the usual type? (I'm not familiar with C#.) If so, and if C# allows implicit integer conversion to boolean like C does, then you might be able to save one more character by changing that to `a/i/i`. – Todd Lehman Jul 27 '14 at 18:41
@ToddLehman That actually happens to be fixed-point arithmetic (`Decimal`, higher max value and precision), to avoid the overflow since the multiplication result could potentially go one step past `UInt64.MaxValue`. But C# doesn't have implicit conversions to Boolean anyway. I should be able to change the `return` though, thanks. I'll do it when I get back to a computer. – Bob Jul 27 '14 at 22:47

## Clojure - 51 or 55 bytes

Checks all numbers from n to 0, giving the first one where `x^2 <= n`. Runtime is `O(n - sqrt n)`

Unnamed:

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

Named:

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

Example:

``````(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 or 38 Characters

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

Try it over here.

-
Ok, that is just cool. Nice work! I entered 17, clicked Creep and then Run, and it came up with 4! :) – Todd Lehman Jul 27 '14 at 0:29

## 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;
}
``````
-
Suggestion: No need for `a`, use `n`. – edc65 Jul 27 '14 at 8:28
Ah yes. Thank you. In my original version, I was maintaining `n` so that just before returning I could make the assertion (not shown) that r^2 <= n < (r+1)^2. With that assertion omitted, it's longer necessary to keep `n` intact. – Todd Lehman Jul 27 '14 at 10:50
@edc65 — Thanks again for pointing that out. I updated my code to reflect that, as well as added a couple other golf tricks. Also added the original assertions and made n `const` in the ungolfed version. – Todd Lehman Jul 27 '14 at 18:21

# 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 characters, O(log n)

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

this solution implements the newton-raphson method, although it searches integers instead of floats. wiki: http://en.wikipedia.org/wiki/Newton%27s_method

-

# J (10)

Very, very, very inspired by the answer of @Dennis:

``````<.@%~^&1.5
``````

And a slightly longer, but with better performance (I suspect):

``````<.@(-:&.^.)
``````

`floor(halve under log)`

To execute, indented parts are input:

``````   f=:<.@%~^&1.5
f 0 8 12 16
0 2 3 4
g=:<.@(-:&.^.)
g 0 8 12 16
0 2 3 4
``````
-
How do you execute this for a given integer? – Dennis Sep 1 '14 at 20:23
@Dennis See answer – ɐɔıʇǝɥʇuʎs Sep 1 '14 at 20:26

# 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

-
Welcome to PPCG! We normally score APL as one byte per character. Unless the challenge specifies it, there is no need to count in UTF-8. Any existing encoding is fine, and there is an old APL codepage from back in the day which uses a single byte for each character. The fact that APL predates ASCII is a bad reason to penalise it for using non-ASCII characters. ;) (That said, this rather old challenge seems to score by characters anyway.) – Martin Ender Jun 13 at 22:08
@MartinEnder Thanks for the warm welcome and tips :) – QuantumKarl Jun 14 at 12:27
`0``1`! Using Dyalog APL, you can set `⎕DIV←1` (which many use as default) to obtain the correct result. – Adám Jun 16 at 10:59

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

-
Nice! Does this work for all unsigned 64-bit integer inputs? – Todd Lehman Jul 29 '14 at 4:55
Try as I might this only seems to work up to 32-bit... Much to my disappointment... – WallyWest Jul 29 '14 at 6:32
Surely the last |0 truncates any value to 32 bit. Using Math.floor instead? – edc65 Jul 29 '14 at 18:54
@edc65 You're right actually, seems `|0` affects up to 32-bit whereas `Math.floor` is more effective at 64-bit... I've updated my code, having to take an extra 8 characters in order to do so... – WallyWest Jul 29 '14 at 23:27
@edc65 I've just had a thought... would ~~x work in 64-bit? – WallyWest Dec 4 '14 at 22:52

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

``````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).

-

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;}
``````
-
I don't think using global variables is legal. At least tell how long it would be legitimately and provide a legitimate version – proud haskeller Jul 30 '14 at 14:29
@proud haskeller Why would global variables be forbidden ? – mantal Jul 30 '14 at 14:43
@mantal because you must provide a runnable program/method. – Marciano.Andrade Sep 3 '14 at 16:25
@Marciano.Andrade the code is gave is runnable. – mantal Sep 4 '14 at 8:43

## 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;
}
``````
-
Nice! How about `x+=(d<0)-0.5;` ... saves 5 more characters? – Todd Lehman Jul 30 '14 at 19:34
BTW, this isn't (but should be) in the form of a function, as mentioned in the problem statement. (Okay, technically, yeah, `main` is a function, but it's not callable from inside a program like an `f(y)` would be.) – Todd Lehman Jul 30 '14 at 19:39
I think you can omit the innermost pair of parentheses and write `while((d=x*x-y)>0.5)` instead of `while((d=(x*x-y))>0.5)`. Saves 2 more characters. :) – Todd Lehman Jul 30 '14 at 19:39
Every 0.5 can be changed to .5 – TuukkaX Jun 20 at 10:07

# Forth, 43

``````: f -1 begin 1+ 2dup dup * - 0< until 1- ;
``````

O(√n)

-

## GolfScript (15 chars)

Pick any one of

``````{):x,{.*x<},,(}
{:x,{).*x>!},,}
{.,\{1\$)/<}+,,}
{,.,{1\$)/<}+,,}
``````

I've followed the other GolfScript answers in interpreting "You can name your function anything you like" as meaning "You may leave a block which does the job on the stack". These are currently the shortest GolfScript answers which correctly handle inputs `0` and `1`.

Online demo

-
Yup, that sounds good! A block on the stack is fair game. As long as it's callable. Nice work! – Todd Lehman Sep 3 '14 at 20:30