JS sqrt function using arithmetic operators
Here is some nice function I've made that calculates a square root of a number:
k=>(f=>f(f))(f=>x=>x==(y=(x+k/x)/2)?x:f(f)(y))(1)
At first look this function is completely cryptic, however it produces exactly the same results for positive numbers as Math.sqrt() function. Let's take a closer look and find out how does it work.
To make our job easier lets do some formatting:
k => (f => f(f)) (f => x => x == (y = (x + k/x)/2) ? x : f(f)(y) )(1)
We've separated our code in two parts - the first part is an arrow function that we will dissect later, and the second part, where some arithmetic arrow function gets an argument 1. Let's check the second part because it looks simplier.
Babylonian method
Our function looks like this:
(f => x => x == (y = (x + k/x)/2) ? x : f(f)(y) )(1)
Function gets two arguments - f and x. We call f at the 4th line and we can figure out that f is a function. Let's ignore f for now. We have a second argument x which has initial value 1 and we calculate y which is equal to
$y = \frac{x + k/x}{2}$This is a Babylonian method of computing square root. The idea is simple. Let's do some simple transformations:
$y = \frac{x + k/x}{2} = \frac{x^2 + k}{2x}$Let's think about what (x2 + k)/2 is. It's an average between our x squared and our number k. So, we can think about y as approximation of square root of k.
Imagine that we are trying to guess the value of square root of k and our guess is that x. If we guessed right and the number x is equal to the square root of k then x2 will be equal to k. In other words, y will be equal to x and to square root of k. But when we guessed wrong and x is not equal to the square root of k then y will be something between x and square root of k. The logic is that the average between our guess and the real square root is closer to the real square root than our guess.Then we can use y as the new guess, or the new value of x to get a better approximation. We just need to repeat calculations until y is equal to x. You can define Babylonian method as:
$x_0 = 1, x_{n+1} = \frac{x_n + k/x_n}{2}$
It's easier to undersand Babylonian with an example. Let's find sqrt(12). At first iteration x is 1 and y will be equal to (1 + 12/1)/2 = 6.5. At second iteration we have x equal to 6.5 and y = (6.5 + 12/6.5)/2 which is about 4.17. Next iteration, x is equal to 4.17, y will be (4.17 + 12/4.17)/2 or about 3.523. At next iteration y will be equal to about 3.464 and we can see that it is not very far from our previous average which is 3.523.
We can see that our calculation slowly comes to the point where x and y are equal. We can continue if we need a better precision but we can easily figure out that if number k is not perfect square then it's square root is irrational (there's a proof for that) and it will never converge. That's why we have to stop recursion at some moment. Help comes from the fact that numbers in JavaScript have finite precision and not really irrational. It means that our algorithm will eventually generate equal x and y.
Fixed point combinator
Now that we know how Babylonian method works we need to understand how exactly we repeat calculations. The next part of our job is more complicated. We need to decipher that strange line f => f(f). As we know, functions can be passed as the argument to other functions. Here we pass some function f as an argument and we call that function f, and provide f itself as an argument to itself. Sounds weird? Let's find out why we want to do something so strange.
Take a look on the line f => x =>. If you are familiar with the concept of currying then you can figure out what happens here. Currying is a process of transforming the function with several arguments into several functions with one argument each. Let's take a look on the example.
const foo = (x => y => x + y) const bar = foo(2) foo(2)(3) == bar(3) // Both expressions return 5
At first line we created a function that uses currying. It's clearer what happens there if you rewrite it as
const foo = (x => (y => x + y))
Function bar will partially apply 2 to function foo. It will return a new function that already has one argument applied (partially applied function). At third line you can see how you can use both these functions. Some languages like Haskell support currying by design. JavaScript supports currying via chain of arrow functions or with help of .bind() method.
Now what happens if we use currying in combination with our f => f(f) function? Our Babylonian function's arguments look like f => x =>. So, the whole function f=>x=>x==(y=(x+k/x)/2)?x:f(f)(y) is partially applied to itself as the argument f and then it calls itself using itself as the first argument. Then it only has to receive an argument x.
So, to summarize, we use function f => f(f) to partially apply a Babylonian function to itself. In other words, our Babylonian function gets itself as the first argument and then it calls itself passing itself as the first argument. Yes, this is recursion, and we made it without specifying a name for a function.
Usually, when you need a recursion you name it and then call it using that name. Here's a simple recursive factorial function:
const fact = (n => n == 0 ? 1 : n * fact(n - 1) )
Our f => f(f) allows us to use recursion by partially applying a function to itself. This construction is called fixed-point combinator and can be used to create recursion in lambda functions. Let's rewrite our factorial example using fixed-point combinator.
(f => f(f)) (f => n => n == 0 ? 1 : n * f(f)(n - 1) )
Now we know what f => f(f) does and we can go back to our sqrt function. We now understand how Babylonian function recursively calls itself and calculates yn+1 until yn+1 is equal to yn.
Fixed-point combinator is useful in languages that allow to create lambda functions. It's also necessary in systems like lambda calculus because there's no other way to create recursion there. It provides formal definition for recursions in functional languages and it allows to create a recursion in languages that don't support it by design.
Here are some definitions of fix in Haskell:
-- recursive fix f = f(fix f) -- using let fix f = let x = f x in x -- point-free fix = id >>= (. fix)
The second definition can be found in Data.Function as well as in Control.Monad.Fix.
P. S. You can add a condition to our sqrt function if you want to handle negative values and NaN's the same way how Math.sqrt does it:
k=>isNaN(k)||k<0?NaN:(f=>f(f))(f=>x=>x==(y=(x+k/x)/2)?x:f(f)(y))(1)