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.

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

19 Answers 19

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
\$\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
\$\endgroup\$
3
  • \$\begingroup\$ This doesn't appear to handle the specification: Your output must be rounded to at least the nearest hundredth \$\endgroup\$
    – Ayb4btu
    Oct 27, 2017 at 21:04
  • 2
    \$\begingroup\$ Well, it is rounded to lower than the nearest hundredth, so it's totally valid. \$\endgroup\$ Oct 27, 2017 at 21:48
  • \$\begingroup\$ Ah, I see, my misunderstanding. \$\endgroup\$
    – Ayb4btu
    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!

\$\endgroup\$
7
  • \$\begingroup\$ -2 bytes: s+(x-s*s)/s/2 to (x+s*s)/s/2 \$\endgroup\$ Oct 26, 2017 at 19:31
  • \$\begingroup\$ -2 bytes using a function \$\endgroup\$
    – hyper-neutrino
    Oct 26, 2017 at 19:41
  • \$\begingroup\$ @HyperNeutrino I only get -1 byte \$\endgroup\$
    – ovs
    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\$
    – hyper-neutrino
    Oct 26, 2017 at 19:53
  • \$\begingroup\$ Can you not omit +.0 and replace /s/2 with /2./s, saving two bytes? \$\endgroup\$ 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!

\$\endgroup\$
2
3
\$\begingroup\$

MATL, 12 9 bytes

X^kGy/+2/

Try it online!

\$\endgroup\$
3
\$\begingroup\$

APL (Dyalog), 20 16 bytes

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

Try it online!

\$\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
\$\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\$ 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\$ 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

\$\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!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 47 bytes; edit: Thank you, but credit @JungHwanMin for finding that. \$\endgroup\$
    – Stan Strum
    Oct 26, 2017 at 19:50
  • \$\begingroup\$ 34 bytes \$\endgroup\$ 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!

\$\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!

\$\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\$
    – Stan Strum
    Oct 27, 2017 at 19:17
  • \$\begingroup\$ 'AWK' puns are fun :) \$\endgroup\$ Oct 28, 2017 at 13:19
  • \$\begingroup\$ instead of sqrt($1) you can use $1^.5 \$\endgroup\$
    – Cabbie407
    Oct 29, 2017 at 22:42
  • \$\begingroup\$ Thanks @Cabbie407 don't know why I didn't think of that. \$\endgroup\$ 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\$
    – Cabbie407
    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
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 9 bytes

DtïD.Á/+;

Try it online!

Port of my Vyxal 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))))
\$\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.

\$\endgroup\$
2
  • \$\begingroup\$ Wow. I've never been able to comprehend how people golf in Windows Powershell \$\endgroup\$
    – Stan Strum
    Oct 26, 2017 at 20:13
  • \$\begingroup\$ @StanStrum You're not alone, lol. :D \$\endgroup\$ 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
\$\endgroup\$
2
  • \$\begingroup\$ I think you want actual division, rather than ÷ \$\endgroup\$
    – H.PWiz
    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\$
    – Leo
    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
\$\endgroup\$
11
  • \$\begingroup\$ Just saw this and it was a good minute until I realised it’s not Pyth. Great answer. \$\endgroup\$
    – Stan Strum
    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\$
    – mudkip201
    Dec 25, 2017 at 17:51
  • \$\begingroup\$ Is ToS top-of-stack... and if so, what’s SoS? \$\endgroup\$
    – Stan Strum
    Dec 25, 2017 at 17:53
  • \$\begingroup\$ ToS is top of stack, and SoS is second on stack \$\endgroup\$
    – mudkip201
    Dec 25, 2017 at 17:54
  • \$\begingroup\$ Nice, I’ll see if I can delve into this language; I like it! \$\endgroup\$
    – Stan Strum
    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
\$\endgroup\$
2
  • \$\begingroup\$ shouldn't that be floor instead of ceil? \$\endgroup\$
    – mudkip201
    Dec 25, 2017 at 15:56
  • \$\begingroup\$ @mudkip201 Updated, thanks \$\endgroup\$
    – ovs
    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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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