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

17 Answers 17

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\$
  • \$\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\$ – Olivier Grégoire Oct 27 '17 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\$ – Jonathan Allan Oct 27 '17 at 18:30
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\$
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\$
  • \$\begingroup\$ This doesn't appear to handle the specification: Your output must be rounded to at least the nearest hundredth \$\endgroup\$ – Ayb4btu Oct 27 '17 at 21:04
  • 2
    \$\begingroup\$ Well, it is rounded to lower than the nearest hundredth, so it's totally valid. \$\endgroup\$ – Olivier Grégoire Oct 27 '17 at 21:48
  • \$\begingroup\$ Ah, I see, my misunderstanding. \$\endgroup\$ – Ayb4btu Oct 27 '17 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\$
  • \$\begingroup\$ -2 bytes: s+(x-s*s)/s/2 to (x+s*s)/s/2 \$\endgroup\$ – JungHwan Min Oct 26 '17 at 19:31
  • \$\begingroup\$ -2 bytes using a function \$\endgroup\$ – HyperNeutrino Oct 26 '17 at 19:41
  • \$\begingroup\$ @HyperNeutrino I only get -1 byte \$\endgroup\$ – ovs Oct 26 '17 at 19:46
  • \$\begingroup\$ Oh sorry I accidentally deleted a character after testing and then counted the bytes after :P yeah just -1 \$\endgroup\$ – HyperNeutrino Oct 26 '17 at 19:53
  • \$\begingroup\$ Can you not omit +.0 and replace /s/2 with /2./s, saving two bytes? \$\endgroup\$ – Jonathan Frech Oct 26 '17 at 21:47
3
\$\begingroup\$

MATL, 12 9 bytes

X^kGy/+2/

Try it online!

| improve this answer | |
\$\endgroup\$
3
\$\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\$
3
\$\begingroup\$

APL (Dyalog), 20 16 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$
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\$
  • 1
    \$\begingroup\$ 47 bytes; edit: Thank you, but credit @JungHwanMin for finding that. \$\endgroup\$ – Stan Strum Oct 26 '17 at 19:50
  • \$\begingroup\$ 34 bytes \$\endgroup\$ – Olivier Grégoire Oct 27 '17 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\$
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\$
  • 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 '17 at 19:17
  • \$\begingroup\$ 'AWK' puns are fun :) \$\endgroup\$ – Robert Benson Oct 28 '17 at 13:19
  • \$\begingroup\$ instead of sqrt($1) you can use $1^.5 \$\endgroup\$ – Cabbie407 Oct 29 '17 at 22:42
  • \$\begingroup\$ Thanks @Cabbie407 don't know why I didn't think of that. \$\endgroup\$ – Robert Benson Oct 30 '17 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 '17 at 0:18
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\$
  • \$\begingroup\$ Wow. I've never been able to comprehend how people golf in Windows Powershell \$\endgroup\$ – Stan Strum Oct 26 '17 at 20:13
  • \$\begingroup\$ @StanStrum You're not alone, lol. :D \$\endgroup\$ – AdmBorkBork Oct 26 '17 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\$
  • \$\begingroup\$ I think you want actual division, rather than ÷ \$\endgroup\$ – H.PWiz Oct 26 '17 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 '17 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\$
  • \$\begingroup\$ Just saw this and it was a good minute until I realised it’s not Pyth. Great answer. \$\endgroup\$ – Stan Strum Dec 25 '17 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 '17 at 17:51
  • \$\begingroup\$ Is ToS top-of-stack... and if so, what’s SoS? \$\endgroup\$ – Stan Strum Dec 25 '17 at 17:53
  • \$\begingroup\$ ToS is top of stack, and SoS is second on stack \$\endgroup\$ – mudkip201 Dec 25 '17 at 17:54
  • \$\begingroup\$ Nice, I’ll see if I can delve into this language; I like it! \$\endgroup\$ – Stan Strum Dec 25 '17 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\$
  • \$\begingroup\$ shouldn't that be floor instead of ceil? \$\endgroup\$ – mudkip201 Dec 25 '17 at 15:56
  • \$\begingroup\$ @mudkip201 Updated, thanks \$\endgroup\$ – ovs Dec 25 '17 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\$

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.