Last post I promised that my next few posts would kick it up a notch. I won’t let you down…
One thing I like to do to push the limits of my programming knowledge and think outside the box is to create functions that replicate native methods, without using native methods or reserved words to achieve the goal; so strictly operators only.
I’ve taken a rather bold example for my first example here, the calculation of a square root of a number.
The calculation of square roots has been done time and time again over the centuries. One of the well known methods for calculating a square root is called “Newton’s Method”, and its usage extends to the derivation of roots for any polynomial.
The function that governs square root calculation using Newton’s Method is:
f(x+1) = f(x) – (f(x)² – A)/(2 × f(x))
Where f(x) is the previous term, f(x+1) is the new term, and A is the original number being square-rooted. This is a recursive process, starting with f(0) = A. Once you start plugging in the values, getting your next term and plugging that in, over and over, you’ll find that the value of f(x+1) converges slowly to the square root of A. With each iteration, the value of (f(x)² – A)/(2 × f(x)) gets smaller and smaller until it reaches zero. Put simply, this expression is our “error factor”.
So what have we done here? Let’s go through step-by-step.
Firstly, this function takes two parameters, with the initial function being called with one parameter, for example, z(37) to get the square root of 37. The reason behind using two parameters is during subsequent iterations of the function it calls two parameters, x, the value of the original number being passed, and y, a number getting closer to the square root of x with each iteration.
Recursion is one of the only few ways to perform this algorithm because you’re essentially performing the same process over and over until a certain amount of acceptable accuracy is reached. Depending on the value of x passed through one could potentially get a “Maximum Call Stack Size Exceeded” error from all the nested loops caused by said recursion.
Remember when I mentioned that the value of f(0) was A, our initial parameter being passed when starting the Newton’s Method algorithm? This is being implemented in the initial part of our function as (y=y||x). This ensures that when we kick off the first iteration of z, that we have a value for y to play with by defaulting to our original number, and taking on the available value of y in subsequent iterations.
Next, as it can be seen, we’re using a ternary operator here, this is the ?: operator. Ternary operators are pretty damn cool in my opinion. They’re basically a shortcut way of expressing an if-then-else statement. They take on the form _condition?_if_true:_if_false. If condition _condition is met, then the statement _if_true prevails, else the statement _if_false prevails. For example, with age>=18?”Can vote”:”Cannot vote” if the age passed is 18 or over, the returned value is “Can vote”, otherwise the returned value becomes “Cannot vote”.
In this case we’re comparing the value of ((y=y||x)*y-x)/(2*y) with 1e-15, or 0.000000000000001… Tiny number. So we’re simply seeing how low our error factor is. Bear in mind, I had actually been using this to determine z(37) when I was initially testing this, so an error of 1e-15 seemed like a good idea at the time especially considering I compared it to the value of Math.sqrt(37). I then later realized I needed to reduce it down to practically zero, but we’ll address that later in this post.
If the ternary condition is true, i.e. the error factor is still to large to be deemed acceptable, the function runs another iteration of itself, but passes x as well as y minus the error factor, thereby getting closer to the original answer, and thereby reducing the error factor closer to zero. If the error factor is deemed sufficiently low, it returns the value of y, our square root.
Let’s reduce it further… As ES6 allows parameters to take on defaults we can shift the default short circuit of (y=y||x) and place it within the parameter component of our function. Now it becomes:
Let’s rewrite this in algebraic form for ease of manipulation…
y – (y² – x)/2y
Let’s expand this, remembering that if you’re subtracting a negative, you’re actually adding a positive…
2y²/2y – y²/2y + x/2y
Which narrows down to:
y²/2y + x/2y
Which, in turn, narrows down to:
y/2 + x/2y
Which can also be expressed as:
Which can then be thrust back into our function:
Pretty sleek if you ask me… As you can see, this has taken away our need for an accuracy check as each iteration will persist until we hit that zero underflow I talked about earlier, which by that stage y will have reached a close enough value to the square root of x.
One final caveat here, this function doesn’t take into account negative numbers, +Infinity, NaN (not a number) values or any number that’s ridiculously high that is close to +Infinity. I’ll revisit tidying this function up later on.
Before I sign off for today, I wanted to thank a fellow code golfer, Arnauld, for his insight of taking advantage of zero underflow to golf this down; it was much appreciated.
Until the next post!