Integer square root of integer [closed]

Question

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!

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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]

Answer 5

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.

Answer 6

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

Answer 7

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

Answer 8

Ruby — 36 characters

s=->n{g=n;g=(g+n/g)/2 while g*g>n;g}

Answer 9

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.

Answer 10

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

Answer 11

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 

Answer 12

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!

Answer 13

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/

Answer 14

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

Answer 15

C# 64 62 55

Since this is a code-golf (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.

Answer 16

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)

Answer 17

Befunge 93 - 48 Bytes or 38 Characters

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

Try it over here.

Answer 18

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%

Answer 19

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.

Answer 20

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

Answer 21

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

Answer 22

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

Answer 23

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

Answer 24

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.

Answer 25

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

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

Answer 27

dc, 50 bytes

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

Spaced out and explained:

               # 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

Answer 28

C, 139 137 136 bytes

My first try at code golf. It looks like it's the shortest in C that fits the "efficient" requirement, as it runs in O(log n) time, using only addition and bit shifts. Though I'm sure it could be shorter yet...

It should work just fine for larger integer values too as long as the a=32 part is changed to 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;}

Answer 29

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

Answer 30

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