Approximate My Squares

Question

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 code-golf, so shortest answer in bytes wins.

@totallyhuman Yes. 47.2851 can be represented as 47.28, but no more inaccurate. — Stan Strum
– Stan Strum, Commented Oct 27, 2017 at 1:05

Leo · Accepted Answer · 2017-10-27 00:28:19Z

4

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

answered Oct 27, 2017 at 0:28

Leo

12.9k1 gold badge33 silver badges63 bronze badges

Add a comment |

Olivier Grégoire · Accepted Answer · 2017-10-27 07:47:13Z

4

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

edited Oct 27, 2017 at 7:47

answered Oct 26, 2017 at 21:54

Olivier Grégoire

14.5k3 gold badges34 silver badges56 bronze badges

\$\begingroup\$ This doesn't appear to handle the specification: Your output must be rounded to at least the nearest hundredth \$\endgroup\$

Ayb4btu
– Ayb4btu

2017-10-27 21:04:13 +00:00
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\$

Olivier Grégoire
– Olivier Grégoire

2017-10-27 21:48:31 +00:00
Commented Oct 27, 2017 at 21:48
\$\begingroup\$ Ah, I see, my misunderstanding. \$\endgroup\$

Ayb4btu
– Ayb4btu

2017-10-27 21:51:23 +00:00
Commented Oct 27, 2017 at 21:51

Add a comment |

ovs · Accepted Answer · 2017-10-27 09:43:41Z

4

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!

edited Oct 27, 2017 at 9:43

answered Oct 26, 2017 at 19:22

ovs

61.3k3 gold badges50 silver badges164 bronze badges

\$\begingroup\$ -2 bytes: s+(x-s*s)/s/2 to (x+s*s)/s/2 \$\endgroup\$

JungHwan Min
– JungHwan Min

2017-10-26 19:31:52 +00:00
Commented Oct 26, 2017 at 19:31
\$\begingroup\$ -2 bytes using a function \$\endgroup\$

hyperneutrino
– hyperneutrino ♦

2017-10-26 19:41:09 +00:00
Commented Oct 26, 2017 at 19:41
\$\begingroup\$ @HyperNeutrino I only get -1 byte \$\endgroup\$

ovs
– ovs

2017-10-26 19:46:06 +00:00
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\$

hyperneutrino
– hyperneutrino ♦

2017-10-26 19:53:23 +00:00
Commented Oct 26, 2017 at 19:53
\$\begingroup\$ Can you not omit +.0 and replace /s/2 with /2./s, saving two bytes? \$\endgroup\$

Jonathan Frech
– Jonathan Frech

2017-10-26 21:47:26 +00:00
Commented Oct 26, 2017 at 21:47

| Show 2 more comments

Mark · Accepted Answer · 2017-10-30 12:27:28Z

4

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!

edited Oct 30, 2017 at 12:27

answered Oct 26, 2017 at 20:28

Mark

4312 silver badges5 bronze badges

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

Giuseppe
– Giuseppe

2017-10-27 18:36:29 +00:00
Commented Oct 27, 2017 at 18:36
1

\$\begingroup\$ 31 bytes using Oliver Gregoire's formula \$\endgroup\$

Giuseppe
– Giuseppe

2017-10-27 18:40:34 +00:00
Commented Oct 27, 2017 at 18:40

Add a comment |

Cinaski · Accepted Answer · 2017-10-27 09:54:26Z

3

MATL, 12 9 bytes

X^kGy/+2/

Try it online!

edited Oct 27, 2017 at 9:54

answered Oct 26, 2017 at 21:39

Cinaski

2,2781 gold badge9 silver badges17 bronze badges

Add a comment |

Uriel · Accepted Answer · 2017-12-25 16:28:22Z

3

APL (Dyalog), 20 16 bytes

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

Try it online!

edited Dec 25, 2017 at 16:28

answered Oct 26, 2017 at 20:11

Uriel

13.3k4 gold badges19 silver badges46 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Oct 26, 2017 at 19:38

Jonathan Allan

116k8 gold badges69 silver badges294 bronze badges

\$\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
– Olivier Grégoire

2017-10-27 13:10:42 +00:00
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\$

Jonathan Allan
– Jonathan Allan

2017-10-27 18:30:51 +00:00
Commented Oct 27, 2017 at 18:30

Add a comment |

Arnauld · Accepted Answer · 2017-10-27 09:48:06Z

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

Steadybox · Accepted Answer · 2017-10-27 15:53:13Z

2

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!

edited Oct 27, 2017 at 15:53

answered Oct 26, 2017 at 19:48

Steadybox

16.6k5 gold badges42 silver badges84 bronze badges

1

\$\begingroup\$ 47 bytes; edit: Thank you, but credit @JungHwanMin for finding that. \$\endgroup\$

Stan Strum
– Stan Strum

2017-10-26 19:50:01 +00:00
Commented Oct 26, 2017 at 19:50
\$\begingroup\$ 34 bytes \$\endgroup\$

Olivier Grégoire
– Olivier Grégoire

2017-10-27 08:43:57 +00:00
Commented Oct 27, 2017 at 8:43

Add a comment |

totallyhuman · Accepted Answer · 2017-10-28 02:28:58Z

2

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!

edited Oct 28, 2017 at 2:28

answered Oct 26, 2017 at 23:37

totallyhuman

17.4k3 gold badges34 silver badges89 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

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!

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Oct 27, 2017 at 16:33

Robert Benson

1,76711 silver badges13 bronze badges

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
– Stan Strum

2017-10-27 19:17:38 +00:00
Commented Oct 27, 2017 at 19:17
\$\begingroup\$ 'AWK' puns are fun :) \$\endgroup\$

Robert Benson
– Robert Benson

2017-10-28 13:19:43 +00:00
Commented Oct 28, 2017 at 13:19
\$\begingroup\$ instead of sqrt($1) you can use $1^.5 \$\endgroup\$

Cabbie407
– Cabbie407

2017-10-29 22:42:47 +00:00
Commented Oct 29, 2017 at 22:42
\$\begingroup\$ Thanks @Cabbie407 don't know why I didn't think of that. \$\endgroup\$

Robert Benson
– Robert Benson

2017-10-30 13:52:19 +00:00
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\$

Cabbie407
– Cabbie407

2017-10-31 00:18:38 +00:00
Commented Oct 31, 2017 at 0:18

| Show 1 more comment

avarice · Accepted Answer · 2021-07-11 11:32:34Z

2

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

answered Jul 11, 2021 at 11:32

avarice

12.5k1 gold badge22 silver badges52 bronze badges

Add a comment |

avarice · Accepted Answer · 2021-07-11 11:37:41Z

2

05AB1E, 9 bytes

DtïD.Á/+;

Try it online!

Port of my Vyxal answer

answered Jul 11, 2021 at 11:37

avarice

12.5k1 gold badge22 silver badges52 bronze badges

Add a comment |

Rodrigo Ruiz Murguía · Accepted Answer · 2017-10-26 19:55:08Z

1

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

answered Oct 26, 2017 at 19:55

Rodrigo Ruiz Murguía

814 bronze badges

Add a comment |

AdmBorkBork · Accepted Answer · 2017-10-26 20:08:23Z

1

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.

answered Oct 26, 2017 at 20:08

AdmBorkBork

43.8k5 gold badges109 silver badges291 bronze badges

\$\begingroup\$ Wow. I've never been able to comprehend how people golf in Windows Powershell \$\endgroup\$

Stan Strum
– Stan Strum

2017-10-26 20:13:20 +00:00
Commented Oct 26, 2017 at 20:13
\$\begingroup\$ @StanStrum You're not alone, lol. :D \$\endgroup\$

AdmBorkBork
– AdmBorkBork

2017-10-26 20:24:56 +00:00
Commented Oct 26, 2017 at 20:24

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Oct 26, 2017 at 23:17

Leo

12.9k1 gold badge33 silver badges63 bronze badges

\$\begingroup\$ I think you want actual division, rather than ÷ \$\endgroup\$

H.PWiz
– H.PWiz

2017-10-26 23:24:09 +00:00
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\$

Leo
– Leo

2017-10-26 23:29:07 +00:00
Commented Oct 26, 2017 at 23:29

Add a comment |

mudkip201 · Accepted Answer · 2017-12-25 22:40:49Z

1

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

edited Dec 25, 2017 at 22:40

answered Dec 25, 2017 at 15:58

mudkip201

9931 gold badge6 silver badges10 bronze badges

\$\begingroup\$ Just saw this and it was a good minute until I realised it’s not Pyth. Great answer. \$\endgroup\$

Stan Strum
– Stan Strum

2017-12-25 17:47:56 +00:00
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\$

mudkip201
– mudkip201

2017-12-25 17:51:42 +00:00
Commented Dec 25, 2017 at 17:51
\$\begingroup\$ Is ToS top-of-stack... and if so, what’s SoS? \$\endgroup\$

Stan Strum
– Stan Strum

2017-12-25 17:53:50 +00:00
Commented Dec 25, 2017 at 17:53
\$\begingroup\$ ToS is top of stack, and SoS is second on stack \$\endgroup\$

mudkip201
– mudkip201

2017-12-25 17:54:29 +00:00
Commented Dec 25, 2017 at 17:54
\$\begingroup\$ Nice, I’ll see if I can delve into this language; I like it! \$\endgroup\$

Stan Strum
– Stan Strum

2017-12-25 17:55:55 +00:00
Commented Dec 25, 2017 at 17:55

| Show 6 more comments

ovs · Accepted Answer · 2018-02-06 21:56:19Z

1

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

edited Feb 6, 2018 at 21:56

answered Oct 26, 2017 at 20:15

ovs

61.3k3 gold badges50 silver badges164 bronze badges

\$\begingroup\$ shouldn't that be floor instead of ceil? \$\endgroup\$

mudkip201
– mudkip201

2017-12-25 15:56:29 +00:00
Commented Dec 25, 2017 at 15:56
\$\begingroup\$ @mudkip201 Updated, thanks \$\endgroup\$

ovs
– ovs

2017-12-25 22:28:16 +00:00
Commented Dec 25, 2017 at 22:28

Add a comment |

Ayb4btu · Accepted Answer · 2017-10-27 23:48:49Z

0

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.

answered Oct 27, 2017 at 23:48

Ayb4btu

5711 gold badge4 silver badges7 bronze badges

Add a comment |

Stack Exchange Network

Approximate My Squares

Input and Output

Examples

Specifications

Rules

19 Answers 19

Haskell, 34 bytes

Java (OpenJDK 8), 32 bytes

Explanations

Python 2, 47 ... 36 bytes

R, 43 bytes 29 bytes

MATL, 12 9 bytes

APL (Dyalog), 20 16 bytes

Jelly, 8 7 bytes

How?

JavaScript (ES7), 22 bytes

Test cases

C, 34 bytes

C, 41 39 37 bytes

C, 49 47 45 43 bytes

Haskell, 40 bytes

AWK, 47 44 38 bytes

Vyxal, 8 bytes

05AB1E, 9 bytes

Racket, 92 bytes

PowerShell, 54 bytes

Husk, 9 bytes

Explanation

Pyt, 11 10 bytes

Explanation

Milky Way, 17 14 bytes

Explanation

C# (.NET Core), 39 bytes

Linked

Hot Network Questions

Approximate My Squares

Input and Output

Examples

Specifications

Rules

19 Answers 19

Haskell, 34 bytes

Java (OpenJDK 8), 32 bytes

Explanations

Python 2, 47 ... 36 bytes

R, 43 bytes 29 bytes

MATL, 12 9 bytes

APL (Dyalog), 20 16 bytes

Jelly, 8 7 bytes

How?

JavaScript (ES7), 22 bytes

Test cases

C, 34 bytes

C, 41 39 37 bytes

C, 49 47 45 43 bytes

Haskell, 40 bytes

AWK, 47 44 38 bytes

Vyxal, 8 bytes

05AB1E, 9 bytes

Racket, 92 bytes

PowerShell, 54 bytes

Husk, 9 bytes

Explanation

Pyt, 11 10 bytes

Explanation

Milky Way, 17 14 bytes

Explanation

C# (.NET Core), 39 bytes

Linked

Related

Hot Network Questions