Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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!
share|improve this question
4  
"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 at 20:34
3  
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 at 20:50
2  
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 at 20:50
1  
Does 2/4 count? –  Milo Jul 27 at 1:02
1  
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 at 2:32

28 Answers 28

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. ";
share|improve this answer
    
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 at 0:30
2  
Does CJam have arbitrary-precision decimals, to cover the whole input range? –  isaacg Jul 27 at 3:16
    
Also, nice hack of using NaN -> 0 on cast to int. –  isaacg Jul 27 at 3:28
    
+1 for exploiting the rules as written. –  R.. Jul 27 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 at 19:49

Haskell, 28 26

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

share|improve this answer
1  
Wouldn't a list index ([...]!!0) be shorter than head? –  isaacg Jul 28 at 6:39
    
@isaacg Yes, it would. Thanks :-) –  Zaq Jul 28 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
share|improve this answer
    
I love it!! Nice work! That is beautifully perverse. –  Todd Lehman Jul 26 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]
share|improve this answer

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);
        last; # Not in the golfed version, but makes things faster.
      } 
    } 
    $root .= $digit;
    $carry -= $product;
  } 
  return $root;
}
share|improve this answer
    
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 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 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 at 1:26
1  
@ToddLehman postfix for doesn't need parentheses; adding that to your suggestions nets me 6 characters total. Thanks! –  hobbs Jul 28 at 1:32

Ruby — 36 characters

s=->n{g=n;g=(g+n/g)/2 while g*g>n;g}
share|improve this answer
    
Nicely done! What is the worst-case execution time? –  Todd Lehman Jul 29 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 at 6:49
1  
@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 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 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.

share|improve this answer
    
— 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 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;}
share|improve this answer
    
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 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 at 0:45
1  
#define Z uint64_t ... or typedef will save a couple –  technosaurus Jul 28 at 6:08
    
@technosaurus — Ah yes, that saves 2. Thank you. :-) –  Todd Lehman Jul 28 at 6:33
1  
The expression n/++r/r has undefined behavior.... –  aschepler Jul 29 at 21:45

Haskell, 147 138 134 128 bytes

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!

share|improve this answer
1  
you can replace (div x 2 + rem x 2) with div(x+1)2, at your "half" function –  proud haskeller Jul 30 at 4:31
    
Thanks, that got it down to a nice even number! –  Matt Noonan Jul 30 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 at 6:08

C# 64 62 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;}

(test on dotnetfiddle)

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

share|improve this answer
1  
You might be able to shave off a character by changing return i-1 to return--i? –  Todd Lehman Jul 27 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 at 18:41
1  
@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 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)
share|improve this answer

Befunge 93 - 48 Bytes or 38 Characters

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

Try it over here.

share|improve this answer
1  
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 at 0:29

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
share|improve this answer
    
This is a new method to me, and it happens to be pretty cool. +1 –  Sieg Jul 28 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 at 11:13

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;
}
share|improve this answer
1  
Suggestion: No need for a, use n. –  edc65 Jul 27 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 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 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%
share|improve this answer

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 
share|improve this answer
    
Ooh, that's 3 characters shorter than the previous best Golfscript answer. Nice work! –  Todd Lehman Jul 30 at 1:30
    
Fixing this to give the correct answer for input 1 probably takes two chars. –  Peter Taylor Sep 3 at 13:57

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

the complexity seems to be about O(log n), but is there a proof of it? please answer in the comments.

share|improve this answer

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}

Here is a JSFiddle: http://jsfiddle.net/rmadhuram/1Lnjuo4k/

share|improve this answer
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 at 18:02
1  
Thanks @Rainbolt. I made the edit. –  Rajkumar Madhuram Aug 8 at 18:03
1  
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 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;
}
share|improve this answer
    
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 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 at 19:29

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

share|improve this answer
    
Nice! Does this work for all unsigned 64-bit integer inputs? –  Todd Lehman Jul 29 at 4:55
    
Try as I might this only seems to work up to 32-bit... Much to my disappointment... –  WallyWest Jul 29 at 6:32
    
Surely the last |0 truncates any value to 32 bit. Using Math.floor instead? –  edc65 Jul 29 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 at 23:27

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.

share|improve this answer

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

The cheap/brilliant exponentiation trick:

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
share|improve this answer

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
share|improve this answer
    
How do you execute this for a given integer? –  Dennis Sep 1 at 20:23
1  
@Dennis See answer –  ɐɔıʇǝɥʇuʎs Sep 1 at 20:26

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

share|improve this answer

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;}
share|improve this answer
1  
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 at 14:29
    
@proud haskeller Why would global variables be forbidden ? –  mantal Jul 30 at 14:43
    
@mantal because you must provide a runnable program/method. –  Marciano.Andrade Sep 3 at 16:25
    
@Marciano.Andrade the code is gave is runnable. –  mantal Sep 4 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;
}
share|improve this answer
    
Nice! How about x+=(d<0)-0.5; ... saves 5 more characters? –  Todd Lehman Jul 30 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 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 at 19:39

Forth, 43

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

O(√n)

share|improve this answer

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.