10
\$\begingroup\$

Inspired by this video by tecmath.

An approximation of the square root of any number x can be found by taking the integer square root s (i.e. the largest integer such that s * s ≤ x) and then calculating s + (x - s^2) / (2 * s). Let us call this approximation S(x). (Note: this is equivalent to applying one step of the Newton-Raphson method).

Though this does have quirk, where S(n^2 - 1) will always be √(n^2), but generally it will be very accurate. In some larger cases, this can have a >99.99% accuracy.

Input and Output

You will take one number in any convienent format.

Examples

Format: Input -> Output

2 -> 1.50 5 -> 2.25 15 -> 4.00 19 -> 4.37 // actually 4.37 + 1/200 27 -> 5.20 39 -> 6.25 47 -> 6.91 // actually 6.91 + 1/300 57 -> 7.57 // actually 7.57 + 1/700 2612 -> 51.10 // actually 51.10 + 2/255 643545345 -> 25368.19 // actually 25,368.19 + 250,000,000/45,113,102,859 35235234236 -> 187710.50 // actually 187,710.50 + 500,000,000/77,374,278,481

Specifications

  • Your output must be rounded to at least the nearest hundredth (ie. if the answer is 47.2851, you may output 47.29)

  • Your output does not have to have following zeros and a decimal point if the answer is a whole number (ie. 125.00 can be outputted as 125 and 125.0, too)

  • You do not have to support any numbers below 1.

  • You do not have to support non-integer inputs. (ie. 1.52 etc...)

Rules

Standard Loopholes are forbidden.

This is a , so shortest answer in bytes wins.

Improve this question
\$\endgroup\$
10
  • \$\begingroup\$ Sandbox \$\endgroup\$ Commented Oct 26, 2017 at 19:06
  • 3
    \$\begingroup\$ Note: s + (x - s^2) / (2 * s) == (x + s^2) / (2 * s) \$\endgroup\$ Commented Oct 26, 2017 at 19:31
  • \$\begingroup\$ My solutions: Pyth, 25 bytes; 14 bytes \$\endgroup\$ Commented Oct 26, 2017 at 20:31
  • \$\begingroup\$ Does it need to be accurate to at least 2 digits? \$\endgroup\$ Commented Oct 27, 2017 at 1:01
  • \$\begingroup\$ @totallyhuman Yes. 47.2851 can be represented as 47.28, but no more inaccurate. \$\endgroup\$ Commented Oct 27, 2017 at 1:05

19 Answers 19

Reset to default
4
\$\begingroup\$

Haskell, 34 bytes

f x=last[s+x/s|s<-[1..x],s*s<=x]/2

Try it online!

Explanation in imperative pseudocode:

results=[] foreach s in [1..x]: if s*s<=x: results.append(s+x/s) return results[end]/2
Improve this answer
\$\endgroup\$
0
4
\$\begingroup\$

Java (OpenJDK 8), 32 bytes

n->(n/(n=(int)Math.sqrt(n))+n)/2

Try it online!

Explanations

The code is equivalent to this:

double approx_sqrt(double x) { double s = (int)Math.sqrt(x); // assign the root integer to s return (x / s + s) / 2 }

The maths behind:

s + (x - s²) / (2 * s) = (2 * s² + x - s²) / (2 * s) = (x + s²) / (2 * s) = (x + s²) / s / 2 = ((x + s²) / s) / 2 = (x / s + s² / s) / 2 = (x / s + s) / 2
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ This doesn't appear to handle the specification: Your output must be rounded to at least the nearest hundredth \$\endgroup\$ Commented Oct 27, 2017 at 21:04
  • 2
    \$\begingroup\$ Well, it is rounded to lower than the nearest hundredth, so it's totally valid. \$\endgroup\$ Commented Oct 27, 2017 at 21:48
  • \$\begingroup\$ Ah, I see, my misunderstanding. \$\endgroup\$ Commented Oct 27, 2017 at 21:51
4
\$\begingroup\$

Python 2, 47 ... 36 bytes

-3 bytes thanks to @JungHwanMin
-1 byte thanks to @HyperNeutrino
-2 bytes thanks to @JonathanFrech
-3 bytes thanks to @OlivierGrégoire

def f(x):s=int(x**.5);print(x/s+s)/2

Try it online!

Improve this answer
\$\endgroup\$
7
  • \$\begingroup\$ -2 bytes: s+(x-s*s)/s/2 to (x+s*s)/s/2 \$\endgroup\$ Commented Oct 26, 2017 at 19:31
  • \$\begingroup\$ -2 bytes using a function \$\endgroup\$ Commented Oct 26, 2017 at 19:41
  • \$\begingroup\$ @HyperNeutrino I only get -1 byte \$\endgroup\$ Commented Oct 26, 2017 at 19:46
  • \$\begingroup\$ Oh sorry I accidentally deleted a character after testing and then counted the bytes after :P yeah just -1 \$\endgroup\$ Commented Oct 26, 2017 at 19:53
  • \$\begingroup\$ Can you not omit +.0 and replace /s/2 with /2./s, saving two bytes? \$\endgroup\$ Commented Oct 26, 2017 at 21:47
4
\$\begingroup\$

R, 43 bytes 29 bytes

x=scan() (x/(s=x^.5%/%1)+s)/2

Thanks to @Giuseppe for the new equation and help in golfing of 12 bytes with the integer division solution. By swapping out the function call for scan, I golfed another couple bytes.

Try it online!

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 35 bytes; more generally, you can use the "header" field of TIO and put a f <- to assign the function. But still, nice solution, make sure you read Tips for golfing in R when you get a chance! \$\endgroup\$ Commented Oct 27, 2017 at 18:36
  • 1
    \$\begingroup\$ 31 bytes using Oliver Gregoire's formula \$\endgroup\$ Commented Oct 27, 2017 at 18:40
3
\$\begingroup\$

MATL, 12 9 bytes

X^kGy/+2/

Try it online!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

APL (Dyalog), 20 16 bytes

{.5×s+⍵÷s←⌊⍵*.5}

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Jelly,  8  7 bytes

-1 byte thanks to Olivier Grégoire's simplified mathematical formula - see their Java answer.

÷ƽ+ƽH

Try it online!

How?

÷ƽ+ƽH - Link: number, n ƽ - integer square root of n -> s ÷ - divide -> n / s ƽ - integer square root of n -> s + - add -> n / s + s H - halve -> (n / s + s) / 2
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ 7 bytes: ÷ƽ+ƽH First time trying to use Jelly so I might be wrong. I wish I knew how to store ƽ, though, to not repeat it. That might save another byte. \$\endgroup\$ Commented Oct 27, 2017 at 13:10
  • \$\begingroup\$ Thanks @OlivierGrégoire! ƽɓ÷⁹+H would not recalculate the integer root, but it's also 7. ɓ starts a new dyadic chain with swapped arguments and then ⁹ refers to that chain's right argument (i.e. the result of ƽ). ƽɓ÷+⁹H would work here too. \$\endgroup\$ Commented Oct 27, 2017 at 18:30
2
\$\begingroup\$

JavaScript (ES7), 22 bytes

x=>(s=x**.5|0)/2+x/s/2

We don't really need an intermediate variable, so this can actually be rewritten as:

x=>x/(x=x**.5|0)/2+x/2

Test cases

let f = x=>x/(x=x**.5|0)/2+x/2 console.log(f(2)) // 1.50 console.log(f(5)) // 2.25 console.log(f(15)) // 4.00 console.log(f(19)) // 4.37 console.log(f(27)) // 5.20 console.log(f(39)) // 6.25 console.log(f(47)) // 6.91 console.log(f(57)) // 7.57 console.log(f(2612)) // 51.10 console.log(f(643545345)) // 25368.19 console.log(f(35235234236)) // 187710.50

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

C, 34 bytes

Thanks to @Olivier Grégoire!

s; #define f(x)(x/(s=sqrt(x))+s)/2

Works only with float inputs.

Try it online!

C,  41   39  37 bytes

s; #define f(x).5/(s=sqrt(x))*(x+s*s)

Try it online!

C,  49   47   45  43 bytes

s;float f(x){return.5/(s=sqrt(x))*(x+s*s);}

Try it online!

Thanks to @JungHwan Min for saving two bytes!

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 47 bytes; edit: Thank you, but credit @JungHwanMin for finding that. \$\endgroup\$ Commented Oct 26, 2017 at 19:50
  • \$\begingroup\$ 34 bytes \$\endgroup\$ Commented Oct 27, 2017 at 8:43
2
\$\begingroup\$

Haskell, 40 bytes

Another one bytes the dust thanks to H.PWiz.

f n|s<-realToFrac$floor$sqrt n=s/2+n/s/2

Try it online!

Improve this answer
\$\endgroup\$
0
2
\$\begingroup\$

AWK, 47 44 38 bytes

{s=int($1^.5);printf"%.2f",$1/2/s+s/2}

Try it online!

NOTE: The TIO like has 2 extra bytes for \n to make the output prettier. :)

It feels like cheating a bit to use sqrt to find the square root, so here is a version with a few more bytes that doesn't.

{for(;++s*s<=$1;);s--;printf("%.3f\n",s+($1-s*s)/(2*s))}

Try it online!

Improve this answer
\$\endgroup\$
6
  • 1
    \$\begingroup\$ well you could say this is AWKward. I’ll show myself out. edit: originally I planned for the question to shun using sqrt, but there’s too many answers and I’ll get tort if I change it so my original idea works. \$\endgroup\$ Commented Oct 27, 2017 at 19:17
  • \$\begingroup\$ 'AWK' puns are fun :) \$\endgroup\$ Commented Oct 28, 2017 at 13:19
  • \$\begingroup\$ instead of sqrt($1) you can use $1^.5 \$\endgroup\$ Commented Oct 29, 2017 at 22:42
  • \$\begingroup\$ Thanks @Cabbie407 don't know why I didn't think of that. \$\endgroup\$ Commented Oct 30, 2017 at 13:52
  • 1
    \$\begingroup\$ You're welcome. Some other things: you don't need the \n to get the output, the printf in awk doesn't need parentheses and the formula can be shortened to s/2+$1/s/2, which results in {s=int($1^.5);printf"%.2f",s/2+$1/s/2}. Sorry if this comment seems rude. \$\endgroup\$ Commented Oct 31, 2017 at 0:18
2
\$\begingroup\$

Vyxal, 8 bytes

:√I:‟/+½

Try it Online!

For n=2

: # Dup -> [2,2] √ # Square root -> [2,√2] I # Round -> [2,1] : # Dup -> [2,1,1] ‟ # Rotate stack right -> [1,2,1] / # Divide -> [1,2] + # Add -> 3 ½ # Halve -> 1.5
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 9 bytes

DtïD.Á/+;

Try it online!

Port of my Vyxal answer

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Racket, 92 bytes

Thanks to @JungHwan Min for the tip in the comment section

(λ(x)(let([s(integer-sqrt x)])(~r(exact->inexact(/(+ x(* s s))(* 2 s)))#:precision'(= 2))))

Try it online!

Ungolfed

(define(fun x) (let ([square (integer-sqrt x)]) (~r (exact->inexact (/ (+ x (* square square)) (* 2 square))) #:precision'(= 2))))
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

PowerShell, 54 bytes

param($x)($x+($s=(1..$x|?{$_*$_-le$x})[-1])*$s)/(2*$s)

Try it online! or Verify some test cases

Takes input $x and then does exactly what is requested. The |? part finds the maximal integer that, when squared, is -less-than-or-equal to the input $x, then we perform the required calculations. Output is implicit.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Wow. I've never been able to comprehend how people golf in Windows Powershell \$\endgroup\$ Commented Oct 26, 2017 at 20:13
  • \$\begingroup\$ @StanStrum You're not alone, lol. :D \$\endgroup\$ Commented Oct 26, 2017 at 20:24
1
\$\begingroup\$

Husk, 9 bytes

½Ṡ§+K/(⌊√

Try it online!

There is still something ugly in this answer, but I can't seem to find a shorter solution.

Explanation

I'm implementing one step of Newton's algorithm (which is indeed equivalent to the one proposed in this question)

½Ṡ§+K/(⌊√ §+K/ A function which takes two numbers s and x, and returns s+x/s Ṡ Call this function with the input as second argument and (⌊√ the floor of the square-root of the input as first argument ½ Halve the final result
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ I think you want actual division, rather than ÷ \$\endgroup\$ Commented Oct 26, 2017 at 23:24
  • \$\begingroup\$ @H.PWiz whoops, I do, thank you. That was a remain from an experiment to find other solutions \$\endgroup\$ Commented Oct 26, 2017 at 23:29
1
\$\begingroup\$

Pyt, 11 10 bytes

←Đ√⌊Đ↔⇹/+₂

Explanation

code explanation stack ← get input [input] Đ duplicate ToS [input,input] √⌊ calculate s [input,s] Đ duplicate ToS [input,s,s] ↔ reverse stack [s,s,input] ⇹ swap ToS and SoS [s,input,s] / divide [s,input/s] + add [s+input/s] ₂ halve [(s+input/s)/2] implicit print
Improve this answer
\$\endgroup\$
11
  • \$\begingroup\$ Just saw this and it was a good minute until I realised it’s not Pyth. Great answer. \$\endgroup\$ Commented Dec 25, 2017 at 17:47
  • \$\begingroup\$ Yeah, it's a little language I've been thinking about for a while and just decided to actually make. \$\endgroup\$ Commented Dec 25, 2017 at 17:51
  • \$\begingroup\$ Is ToS top-of-stack... and if so, what’s SoS? \$\endgroup\$ Commented Dec 25, 2017 at 17:53
  • \$\begingroup\$ ToS is top of stack, and SoS is second on stack \$\endgroup\$ Commented Dec 25, 2017 at 17:54
  • \$\begingroup\$ Nice, I’ll see if I can delve into this language; I like it! \$\endgroup\$ Commented Dec 25, 2017 at 17:55
1
\$\begingroup\$

Milky Way, 17 14 bytes

-3 bytes by using Olivier Grégoire's formula

^^':2;g:>/+2/!

Try it online!

Explanation

code explanation stack layout ^^ clear preinitialized stack [] ': push input and duplicate it [input, input] 2; push 2 and swap ToS and SoS [input, 2, input] g nth root [input, s=floor(sqrt(input))] : duplicate ToS [input, s, s] > rotate stack right [s, input, s] / divide [s, input/s] + add [s+input/s] 2/ divide by 2 [(s+input/s)/2] ! output => (s+input/s)/2
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ shouldn't that be floor instead of ceil? \$\endgroup\$ Commented Dec 25, 2017 at 15:56
  • \$\begingroup\$ @mudkip201 Updated, thanks \$\endgroup\$ Commented Dec 25, 2017 at 22:28
0
\$\begingroup\$

C# (.NET Core), 39 bytes

v=>(v/(v=(int)System.Math.Sqrt(v))+v)/2

Try it online!

A C# version of Olivier Grégoire's Java answer.

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.