3
\$\begingroup\$

I have the following code which I've written to emulate Newton's method for deriving the square root of a number:

r=(x,y)=>
  (z=((y=y||x)*y-x)/(2*y)>1e-15)?
r(x,y-(y*y-x)/(2*y)):y

Where r(37) would result in 6.08276253029822 which is great given the limitations of my browser.

I'd like to golf this code further seeing there's some repetition here, not to mention, I'd also like to reduce my error limit (the 1e-15). This is the furthest I've gotten. Can anyone help? If possible I'd love to eliminate the need of the error limit without resulting in a "maximum stack call size exceeded" error...

This is for a blog post I'm working on JavaScript and alternatives to native methods. I'll give a special shout out on the blog post to the persons who can help me out.

Thanks in advance.

\$\endgroup\$
  • 1
    \$\begingroup\$ Which is more important, golfing it or reducing the error? \$\endgroup\$ – mbomb007 Oct 5 '17 at 20:58
  • 8
    \$\begingroup\$ Idk. Questions about golfing are ON-TOPIC. Someone voted to close, and I think they are wrong. \$\endgroup\$ – mbomb007 Oct 5 '17 at 21:11
  • 1
    \$\begingroup\$ @xnor, this is a tips question, not a challenge. \$\endgroup\$ – Shaggy Oct 5 '17 at 21:49
  • 5
    \$\begingroup\$ @WallyWest Right, but I can't give help to golf without knowing the challenge. Does anything stop you from just writing sqrt(n)? What accuracy is required? The code has a 1e-15 in it -- whether a byte could be saved as a 1e-9 depends on how precise the output must be. "I'd also like to reduce my error limit (the 1e-15)" further confuses it. \$\endgroup\$ – xnor Oct 5 '17 at 21:56
  • 2
    \$\begingroup\$ @WallyWest Also, it's not clear from the text that you are looking primarily for golfing help. Asking about eliminating the error limit and saying you'll use it for an explanation in a blog rather sounds like seeking programming advice separate from shortening code. \$\endgroup\$ – xnor Oct 5 '17 at 22:01
9
\$\begingroup\$

Golfed only, -23 bytes

ES6 supports default parameters.

Default function parameters allow formal parameters to be initialized with default values if no value or undefined is passed.

So, we can replace y=y||x with just r=>(x,y=x).

(y*y-x)/(2*y) can be rewritten as y/2-x/2/y. And since this expression appears twice in the code, we can assign it to a new variable z.

We get:

r=(x,y=x)=>(z=y/2-x/2/y)>1e-15?r(x,y-z):y

As suggested by ETHproductions in the comments, we now can save 2 more bytes by multiplying z by 2:

r=(x,y=x)=>(z=y-x/y)>2e-15?r(x,y-z/2):y

r=(x,y=x)=>(z=y-x/y)>2e-15?r(x,y-z/2):y

console.log(r(37))


Alternate version, -26 bytes

To save more bytes, another approach is to just iterate enough times rather than using a test on the result.

That could be done that way:

r=(x,y=k=x)=>(k/=2)?r(x,y/2+x/2/y):y

r=(x,y=k=x)=>(k/=2)?r(x,y/2+x/2/y):y

console.log(r(37))

We start with k = x and divide it by 2 at each iteration. No matter the initial value of x, we will eventually reach 0 because of arithmetic underflow.

The good thing about this method is that the number of iterations doesn't heavily rely on the value of x. For instance, we'll get 1142 iterations for x = 1020 and 1009 iterations for x = 10 -20. In both cases, we iterate far too many times than necessary, without exceeding the default maximum number of iterations of common browsers.

Some more notes:

  • The error is negligible for x > 10 -215 and quickly grows below this bound.
  • For the same byte count and less iterations, we can divide by 9 instead. In that case, a safe bound is x > 10 -124.
  • Unlike Math.sqrt(), this method does not return NaN for negative numbers or ±Infinity (and neither does the original code).
\$\endgroup\$
  • 2
    \$\begingroup\$ And then you can do r=(x,y=x)=>(z=y-x/y)>2e-15?r(x,y-z/2):y to save another two bytes, and perhaps adjust the 2e-15 to get more precision \$\endgroup\$ – ETHproductions Oct 5 '17 at 21:39
  • 1
    \$\begingroup\$ @ETHproductions Thanks! I thought about such an optimization for a second but overlooked it. \$\endgroup\$ – Arnauld Oct 5 '17 at 21:44
  • 1
    \$\begingroup\$ @Arnauld Nice abuse of arithmetic underflow... I had considered it in some of my previous attempts but wasn't sure on the implementation. This is perfect... Thanks! \$\endgroup\$ – WallyWest Oct 5 '17 at 22:10
  • 1
    \$\begingroup\$ @WallyWest Glad it helped! Some quick notes: 1) Performance-wise, the alternate version is, of course, very inefficient. 2) Unlike Math.sqrt(), these methods do not return NaN for negative numbers or +/-Infinity. \$\endgroup\$ – Arnauld Oct 5 '17 at 22:51
1
\$\begingroup\$

This is almost similar to "@Arnauld Alternate version" and has same bytes with that, but this can work in x < 1e-215

r=(x,y=k=9)=>k?r(x,(y+x/y)/2,k/=2):y
\$\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.