# Reimplementing square root [duplicate]

Define a function, s, which takes a number and returns the square root.

No use of library functions, such as Java's Math.sqrt() or PHP's built in sqrt(), allowed.

• I think all solutions will be based on Newton approximation such as codemaestro.com/reviews/9 Commented Jan 28, 2011 at 0:56
• How do you feel about exp(0.5*log(x))? Commented Jan 28, 2011 at 2:07
• The problem with this puzzle is that it lacks specifications for input range and tolerated error, it's kinda boring if "keep on adding a small number until result is reached" method is allowed, it's the shortest in any language. Commented Jan 28, 2011 at 2:11
• @jtjacques: Er...yes it does. Try a couple of cases. Make sure that you use the same base for exponentiation and logarithm. Commented Jan 28, 2011 at 2:23
• @jtjacques: Base agreement is key, many languages use log for the base 10 logarithm, so you might try exp(0.5*ln(x)) to get the natural log or pow10(0.5*log(x)) or similar. Commented Jan 28, 2011 at 2:38

## Python - 11 chars

Technically not a library function :)

input()**.5


As a function it's 16 chars

f=lambda x:x**.5

• Smart, I like it. Commented Jan 28, 2011 at 1:25
• It's questionable whether this falls under a built-in function (it calls __pow__). But then even * is a built-in. Commented Jan 29, 2011 at 11:37
• Would have preferred it as a function, but I'll give you the accept for the ingenuity. Commented Jan 31, 2011 at 15:45
• @jtjacques What ingenuity? IMHO, this is the one the most obvious ways around the rules. Commented May 16, 2011 at 3:48
• I think the function has to be called 's', not 'f'. Commented Jul 8, 2015 at 17:56

## Python (13 chars)

f=.5.__rpow__

This is equivalent to f=lambda x:x**.5, but 3 bytes shorter.

## Python - 41 chars

Takes a while to run for large numbers :)

n=input()
i=0
while i*i<n:i+=1e-9
print i

• For me, it takes a while even for 2.
– user344
Commented Apr 30, 2014 at 13:44

## Java (163)

Implementing a double precision square root calculator by making use of the fast invert square root stuff from quake and a new constant for the 64bit floats. In java. Yay for verbosity.

public double i(double a){double b=a/2;long c=0x5fe6ec85e7de30daL-(Double.doubleToRawLongBits(a)>>1);a=Double.longBitsToDouble(c);return a*(1.5-b*a*a);};s=1/i(x);


## J, 6, 5

Using power:

^&0.5


Or, perhaps more mnemonically:

^&1r2


Using the slightly less "cheaty" method, exp(log(x)/2).

-:&.^.


Except since exp is the inverse of log, we simply "halve (-:) under (&.) log (^.)"

Not that normally a J programmer would not name a method this short; he'd simply embed in in a larger program.

s=(**0.5)


Similar to @gnibbler's Python solution.

Naive solution, accepts only positive integer inputs.

s n=foldr (\x a->x*x==n||a) False [1..]


• remove spaces? s n=foldr(\x a->x*x==n||a)False[1..] Commented Jan 28, 2011 at 3:51

LISP (66)

Using Babylonian method.

(defun s(A)
(do((x 1(*(+ x(/ A x)).5))(n 100(1- n)))((zerop n)x)))


## Python - 65

A simple solution using Newton's method.

def s(x):
t=1.0
while 1e-9<abs(x-t*t):t-=(t*t-x)/2/t
return t


C with some bad form and deprecated features:

s(int n,int g){return g*g-n?s(n,random()%n):g;}


If your compiler is enough of a liberal hippie, it should be possible to call s(n) and (eventually) receive the desired value.

• You can save 8 characters, and allow calling s(n) (at least in GCC), by changing s(int n,int g) to s(n,g). Commented Mar 18, 2011 at 4:20
• Save 2 more chars by changing random() to rand(). Commented Jun 14, 2011 at 14:36
def sqrt_newton(x):
f,g,w,d=lambda a:a*a-x,lambda a:2.0*a,x/2.0,1e-4
while abs(f(w))>d:w-=(f(w)/2.0/w)
return w


reduced version of https://gist.github.com/713104

• And the size is ... Commented Nov 8, 2011 at 5:35
return 1.f/InvSqrt(x);


InvSqrt of course courtesy of Quake.

What, you mean you wanted an accurate result?

• Well to the limit of the return type, and also one which does not use a library. Commented Jan 28, 2011 at 1:08

## C++ (61)

Uses Heron's Method:

f64 s(f64*x,u64 n=9){*x=(x[1]/*x+*x)/2;return n?s(x,--n):*x;}


Recursion, pointers, optional arguments, and ternary operators FTW!

Usage:

f64 x[2] = {12.0, 12.0};
std::cout << s(x);


## C++ (35)

f64 s(f64 x){return exp(log(x)/2);}


I promise I didn't use sqrt()!

## ActionScript3 (53)

Using Newton's method. (Hooray 4 IEEE 754)

function s(b,d=2){return b==d*d?d:s(b,d-(d*d-b)/2/d)}


I know I'm TOO late but I just wanted to write something I did :(

# GolfScript - 21

It uses the Babylonian method and works only with integers. According to my tests, it's good for up to 56 digits.

{1{.2$\/+2/}99*\;}:s;  Usage: 1000 s -> 31 I think this is the shortest solution so far that doesn't call some kind of power function or external library. # k (17 chars) Iterative (implementation of Babylonian method): {{.5*y+x%y}[x]/x}  Iterates until two successive values are equal Example: sqrt[1234] = {{0.5*y+x%y}[x]/x}1234 1b  Also the mandatory xexp[;0.5] for 10. # Python, 44 def s(x):t=1.;exec"t=(t+x/t)/2;"*99;return t  Tested with: for x in [0, (3+5**0.5)/2, 1000, 10**5, 10**11]: print x, '->', s(x)  Output: 0 -> 1.57772181044e-30 2.61803398875 -> 1.61803398875 1000 -> 31.6227766017 100000 -> 316.227766017 100000000000 -> 316227.766017  # Python, 50 49 In case you like recursion: s=lambda x,t=1.,r=99:r and s(x,t/2+x/t/2,r-1)or t  Same testing code, same output. Mathematica 27 f@x_:=Nest[(#+x/#)/2&,1.,9]  ## Golf-Basic 84, 9 characters iAdA^.5  As a function, 15 characters: iA:Return A^.5  ## JavaScript, 36 (or 14 without the function) function s(n){return Math.pow(n,.5)}  AWK, 8 1,$0^=.5


Following solution can handle all values except 0

AWK, 6

$0^=.5  # Befunge 98 - 18 &00pv 0*::<+1vj!g0  This program takes an input number from the user, and ends by pushing the integer square root on the stack (note that you said square root, but didn't specify whether floating point was necessary). Here is a function (well, closest thing to one) (requiring free access to cell 00) (15 chars): 00p::*00g!jv1+  In these I expect the byte to be squared is in the current cell. It needs 8 cells to the right empty and it will have answers in the 4 cells starting from where the number was. These are: 1. integer result 2. a alternative result (would be the same or one higher if those multiplied is closer to the argument) 3. remainder 4. flag for negative remainder # Extended BrainFuck: 310 >+4>15+4<[>>+<+<[->[->->>+<<]>[-<+>>]<+<<]>[-]>[-]3<[->+>>+3<]>[-<+>]4>[-<+3<+4>]<<[->-[>+>>]>[+[-<+>]>+>>]5<]3>[-3<+3>]<[->>+>+3<]<[->+4>+5<]>+[>>[-<]<[>]<-]3>+<[[-]>[-]>[-4<+4>]5<+<+4>]>[->[-]<[-3<+3>]]3<[->+<]<<[->>+4<->>]<+<[-[+3>[-]>>[-]4<-]>[-5>+4<]<]>[->]<<]<[-]5>[-4<+<+5>]>>[-6<+6>]<[-3<+3>]<<[-<<+>>]  It turns into the following: # BrainFuck: 390 (the same as above run through the compiler) >+>>>>+++++++++++++++<<<<[>>+<+<[->[->->>+<<]>[-<+>>]<+<<]>[-]>[-]<<<[->+>>+<<<]>[-<+>]>>>>[-<+<<<+>>>>]<<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>>>[-<<<+>>>]<[->>+>+<<<]<[->+>>>>+<<<<<]>+[>>[-<]<[>]<-]>>>+<[[-]>[-]>[-<<<<+>>>>]<<<<<+<+>>>>]>[->[-]<[-<<<+>>>]]<<<[->+<]<<[->>+<<<<->>]<+<[-[+>>>[-]>>[-]<<<<-]>[->>>>>+<<<<]<]>[->]<<]<[-]>>>>>[-<<<<+<+>>>>>]>>[-<<<<<<+>>>>>>]<[-<<<+>>>]<<[-<<+>>]  It's Newtons method starting at guess 16 and goes downwards. It stops when the last iteration didn't make a different integer result. This is actualy from the sqrt macro of EBF since I use it to implement print-string operator |. Here's the part from EBF source ungolfed: ; sqrt ^0 uses 9 cells that need to be empty ; will be fuzzy after calling because of divmod ; returns ^0 result ; ^1 same as ^0 or it increased by 1. typically will ^2*^3 be closerto the requested argument than ^2*^2 ; ^2 remainder ; ^3 indicates if remainder is negative {sqrt check for wrong usage !diff:diff :in:guess:temp:cur:div:mod:res:indicator @in$guess+     ;initial guess is 16, but
$mod 15+ ; its in mod and incremented (rounded up)$guess(     ; worst case is 1 with 5 iterations
$cur+$temp+
$guess(-$temp[->-$mod+$cur]>[@cur-$temp+$div]$cur+)$temp(-)$cur(-)$in(-$guess+$cur+)
$guess(-$in+)
$mod(-$div+$guess+)$cur &roundivmod ; remainder wil now be in mod
$mod(-$res+)
$cur(-$mod+$guess-)$temp+
$guess[-[+$div(-)$res(-)$temp-]>[-@temp$indicator+$cur]$temp]>[-@temp>] )$in(-)
$mod(-$guess+$in+)$indicator(-$guess+)$res(-$cur+)$div(-$temp+)$in
!indicator!res!mod!div!cur!temp!guess!in
}

;; helper macros
; roundivmod uses divmod and puts the rounded result in ^0 and indication of rounded in ^1
; and a remainder (which ^1 is an indication is either reduction or inrement) in ^2
{roundivmod
&divmod @cur
; *0|n-rem|rem|res|
>>>(-<<<+)
<(->>+>+) make double copy of remainder
; res|n-rem|0|0|rem|rem
<(->+>>>>+)
; res|0|n-rem|0|rem|rem|n-rem
>+[>>[-<]<[>]<-]
>>>+<(
[-]>[-]
>(-<<<<+)
<<<<<+<+
)
>(-
>[-]
<(-<<<+)
)
end divide
}

; this does the divmod. compiler is fuzzy after so caller must fix position to calling
{divmod[->-[>+>>]>[+[-<+>]>+>>]<<<<<]}


Java: 74 characters

I'm leaving the square root as an exact answer because I don't enjoy approximations :)

enum A{;public static void main(String[]a){System.out.println('√'+a[0]);}}


or

enum A {

;public static void main(String[] a) {
System.out.println('√' + a[0]);
}
}


# JavaScript, 121

No, it doesn't even come close, but it is more optimal than other solutions and doesn't use Math.pow with fractions.

s=n=>{for(var c=Math.pow(10,(''+Math.floor(n)).length),v=0,l;(l=v*v<n),c>1e-10;l!=v*v<n?c/=10:0)v*v<n?v+=c:v-=c;return v}

• You're missing the function name there. Should be something like function s(n).
– user344
Commented Apr 30, 2014 at 10:41
• @nyuszika7h: It’s a function literal.
– Ry-
Commented Apr 30, 2014 at 14:28
• But you would need to assign that to a variable (which is the same "penalty" as using my previous suggestion). I don't see Python solutions like lambda x: ... either, I see solutions like f=lambda x: ....
– user344
Commented Apr 30, 2014 at 14:30
• @nyuszika7h: Their loss. This code is a function.
– Ry-
Commented Apr 30, 2014 at 14:30
• Also, sorry if it came off as being rude, I didn't mean to be.
– user344
Commented Apr 30, 2014 at 14:46

## F# (12)

It seems like cheating since other languages has similar solutions. But it works.

let s n=n**0.5


# Julia (9) characters

f(x) = x^.5


### Scala 78 chars:

type D=Double
def q(x:D,g:D=9):D=if(math.abs(g*g-x)<.001)g else q(x,(g+x/g)/2)


invocation:

scala> q(12345)
res36: D = 111.10805572305925


# Postscript 94 89

Babylonian method. Iterates until successive values are equal.

s{dup 2 div{2 copy div 1 index add .5 mul
2 copy eq{exit}if exch pop}loop pop exch pop}def


Commented:

/s{
dup 2 div  % S x
{  % S x
2 copy div  % S x S/x
1 index add .5 mul  % S x (S/x+x)/2
2 copy eq { exit } if  % S x (S/x+x)/2
exch pop  % S (S/x+x)/2:->x
}loop
pop exch pop
}def
`