You’re being irrational… No, wait… That’s π and e…

So, in my last post I said I was going to tackle pushing the limits of JavaScript and create non-native functions that can derive the values of two irrational numbers: π and e. I also said I was going to use similar methods to derive these values. I plan to follow through on this promise…

So let’s take a look at what I reckon would be the harder of the two: the derivation of π.

π – the number… not the tasty baked good.

So, when it came to doing this, I did a little research into the various formulae that have been used to calculate π. I came across this little tidbit from Madhava of Sangamagrama:

This is an infinite series that rapidly converges to the value of π, and Madhava was from the 14th century… And using the square root of 12… Who would have thought of this back then..?

If you recall from two posts ago I had created a square root function, so this part is easy… I’ve also dealt with cumulative sums before in my previous post with the derivations of the non-native sine and cosine functions, and I’ve also created an integer power function as well. So technically, we have all the ingredients to make some delicious “π” (pun intended)…

So let’s take a look at building this up. Let’s grab the two main functions we need to make this happen, the square root function and the power functions:

p=(x,y)=>y–?x*p(x,y):1;

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

These two functions were discussed in previous posts. The integer power function p(x,y) raises a positive integer, x, to the power of another positive integer, y. Whereas the square root function r(x), takes a number, x, and runs Newton’s Method of Approximation for square roots until zero underflow is reached in order to provide the square root.

Using these two functions we’ll put together a pi() function that uses these two and one other function (the cumulative sum function) that we’ll create right now:

P=k=>~k?P(~-k)+1/p(-3,k)/(k-~k):0;

Those who have followed my blog well enough will have recognized that this is a recursive function. This loops through from k down to zero and with each iteration added the equivalent of (-3-k)/(2k+1). Because the integer power function works only with positive powers of y, a simple reciprocal equates to the negative power of y. As this P() function converges quite quickly, you only need 100 iterations before JavaScript’s zero underflow kicks in, P(99), which will give us 100 iterations (0-99) should give us that without breaking a sweat. After that it’s simply a case of multiplying the result with the square root of 12:

pi=()=>r(12)*P(99)

The results will surprise you:

pi() gives 3.141592653589794

Math.PI gives 3.141592653589793

Which is more accurate? According to WolframAlpha, the sequence after the 97 goes 93238… And while JavaScript’s native value wins this round, you have to admit, that’s pretty reasonable accuracy just using recursive functions and standard operators… Now let’s turn out focus to the other guy…

e – the number… I’ve got nothing to compare this against, so let’s just get on with it…

Okay, this is far simpler… e is defined as the cumulative sum of the reciprocals of all natural integer factorials from zero and above… In other words:

It’s interesting to note that as 0! and 1! are both equal to 1, the first two terms of this series make up about 73.5% of the total value of e… Just thought I’d randomly share that bit of trivia there…

Anyhow… If we create a similar cumulative function called e() which adds the reciprocal of reach natural integer factorial, borrowing our factorial function from my post a few weeks ago:

e=k=>~k?e(~-k)+1/f(k):0;

…we then have our function… 100 iterations would once again be sufficient to get to our value within acceptable accuracy… Put to the test:

e(99) gives 2.7182818284590455

Math.E() gives 2.718281828459045

WolframAlpha shows e as continuing after the 2845 with 904523, so apart from that last digit in the return value from our function, it’s practically identical and with a surprising amount of accuracy!

So there we have it… We’ve succeeded in deriving two irrational numbers using a few fundamental functions through basic operators, recursion and fat arrow functions.

My next post will focus on something we touched a little earlier on – JavaScript obfuscation; in this case a challenge set by a fellow code golfer to test me… Goodness knows why… But we’ll take a look in my next post. Until then, stay quirky!

Advertisements

Getting to the root of the problem… Square root that is…

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”.

I like this process as it can be readily replicated in JavaScript. Bear in mind first, that my initial draft of the function below is just that, an initial draft. We will be taking a look at its evolution in this post to something more compact.

z=(x,y)=>

((y=y||x)*y-x)/(2*y)>1e-15?

z(x,y-(y*y-x)/(2*y)):y

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.

Given the upper bound limits within JavaScript, my testing has shown that this starts losing cohesion at about z(1E140), i.e. the square root of 1 followed by 140 zeroes… We should potentially see an answer of “1e+70”, but what we do end up getting is 9.999999999999999e+69. Given the limit of available decimal places this ain’t bad, but what are the chances that you’ll be playing with numbers that large? By comparison, with reference to MarketWatch.com, as of September 15, this year, the US national debt stands at just over 20 trillion (20E+12) dollars [source], but I digress.

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:

z=(x,y=x)=>

(y=(y*y-x)/(2*y))>1e-15?

z(x,y-(y*y-x)/(2*y)):y

Notice now we have two instances of (y*y-x)/(2*y), so let’s introduce a new variable k which will act as a marker, taking on x as a default and also take advantage of the fact that if you reduce a number small enough in JavaScript that it will coerce that number to zero… This is a phenomenon that’s known as zero underflow. This is where the number gets so small the JavaScript compiler throws up its hands and goes “You know what? That’s close enough to zero for me, I’m gonna call it zero” and runs with it… As a result, you get this:

z=(x,y=k=x)=>

(k/=2)?z(x,y-(y*y-x)/(2*y)):y

We’re using a divisor of 2 here so we can get as many iterations as possible and it also links nicely with our divisor in our second parameter in the recursed call. We can narrow this further. Let’s take a look at that second parameter in the recursive call: y-(y*y-x)/(2*y). A bit messy, but some simple algebra and a little JavaScript shortcutting can shorten this up.

y-(y*y-x)/(2*y)

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:

y/2+x/2/y

Which can then be thrust back into our function:

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

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.

We’ll be taking advantage of this function in a later post where we use this to derive another alternate version of another JavaScript method. More on that later. Next post will be used to focus on the derivation of the three main trigonometric functions in a similar fashion as above.

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!

Unary and Negation Operators Part 2 – Numbers and Booleans

Hi again! Now, last I spoke (er… wrote) I had been going ad nauseum regarding the affects of unary and negation operators on strings. Today, I’ll be focusing my efforts with regards to these same operators but on a few of the remaining objects on the list: booleans and numbers… The others I’ll handle in future posts.

So, Unary and Negation Operators (which I’ll call UNOs for short) yield interesting results when combined with other JavaScript object types. We dealt with strings and the effects of UNOs on them in my last post; so as numbers will be relatively simple I’ll just blitz through this part…

+5 == 5
-5 == -5
-(-5) == 5

Well… Surprise, surprise… The plus and minus do the exact expected thing one would expect in standard mathematics…

The only exception to this is --5. --5 actually won’t evaluate as the -- operator is reserved for pre-decrement and post-decrement of variables, and not numbers… For the negation of a negative number parentheses need to be used, as per my last example.

And that’s UNOs with numbers… I told you it’d be quick…

Now we get to the interesting parts. Let’s start with booleans…

+false == 0
+true == 1


Okay, to understand why coercing false to a number results in zero, and why true is coerced to 1, I need to get into truthy and falsy values… Truthy and falsy values have the following traits:

  • Truthy values will coerce to true when converted to a Boolean. Examples of truthy values are all natural numbers both positive and negative (excluding zero), and non-empty strings, and all empty and non-empty arrays and objects. Basically any value that has definition, is not null, or zero, or empty qualifies as a truthy value (…and empty objects and arrays, I wish someone can explain this to me… That’s just plain weird). True as well counts as a truthy value.
  • Falsy values will coerce to false when converted to a Boolean. Examples of falsy values are zero, empty strings; null, NaN (Not a Number) and undefined. Naturally, false also counts as a falsy value.

So how do you test whether a value is truthy or falsy? You know how they say “two wrongs don’t make a right”? JavaScript have taken this concept and twisted it on its head. JavaScript’s Logical NOT operator (!) converts true to false and vice versa… So combining two of them you have a falsy/truthy operator which is capable of taking any value and determining if it is truthy or falsy. !! spits out true for truthy values and false for falsy values. It really is that easy.

So where am I leading with this? If you’ve been programming for a while, you’ll have come across similar examples of truthy and falsy values at work, probably without you realizing it:

var x=10;
while(x){
   f(); x--;
}

The while loop and the for loop are notorious for abusing the concepts of truthy and falsy values. See that solitary x in our example here? As you will know while loops work off a condition being satisfied to continue running. When the condition is no longer met, the while loop terminates and the code moves on. With each iteration the value of x decreases until it reaches zero. Once it does, the while loop finally converts zero to false and terminates. Similarly, you may have seen the following:

while(true) 

or

while(1)

Both statements mean the same thing… So, it would make sense that true and 1 are considered equivalent to one another logically. In fact, if you were to evaluate !!1 you would naturally get true, and evaluating +true will give you 1. Similarly, because zero is a falsy value you could conclude that !!0 would give you false, and therefore +false would give you 0.

And you’d be right…

Because 0 and 1 are falsy and truthy respectively they can technically be used as shortcuts for false and true respectively. While technically any number or truthy value could be used as a substitute for true, 1 is the simplest and quickest way. This little trick of using 0 and 1 as substitutes for false and true is often used in code golf (which I will cover in a later post) to conserve character usage. Basically, you’re saving 4 and 3 characters respectively.

So as a result:

+false == 0

and

+true == 1

In my next post, I will be addressing arrays and objects and how they react with UNOs. Stay tuned.

Unary and Negation Operators Part 1 – Strings

In my most recent post, I mentioned the various objects that exist in JavaScript, and the operators most commonly responsible for coercing one object type into another.

In this post, I’ll be focusing on the Unary Operator (+) and the Negation Operator ()

+"5" == +(5) == 5

In the above example we see the unary operator acting upon the “5” string resulting in said string being coerced into a number, naturally, the number 5.

Let’s take a look at the process as it happens:

  1. The unary operator upon first encountering the string, checks the nature of the string. In this case, it’s a string which is numeric by nature.
  2. Next, the unary operator coerces the string into its respective number. Note in this case, I’ve placed the 5 in parentheses to show that the 5 has still yet to be further acted upon. This will come into importance in later examples.
  3. Finally the unary operator acts upon the numeric 5 and coerces further with its secondary function, acting as a positive on the numeric 5 we have already coerced from the string. The final result is an unsigned (and thus naturally positive) 5.

Let’s go a step further, now this time with the Negation Operator, the sign.

-"5" == -(5) == -5

In this example we see the negation operator acting upon the “5” string resulting in said string being coerced into a number, in this case, the number -5.

So let’s see what happens this time around:

  1. The negation operator upon first encountering the string, checks the nature of the string. As with the previous example, it’s a string which is numeric by nature.
  2. Next, the negation operator coerces the string into its respective number. Note as with the previous example, I’ve also placed the 5 in parentheses to show that the 5 has still yet to be further acted upon.
  3. Finally the negation operator acts upon the numeric 5 and coerces further with its secondary function, acting as a negator on the numeric 5 we have already coerced from the string. The final result is -5.

If we were to have used the string “-5” instead in these two examples we would get -5 and 5 respectively. Why? Let’s take a quick look.

+"-5" == +(-5) == -5

-“-5” == -(-5) == +5 == 5

So, once the -5 is “cast out” (the supposed technical term for the conversion of one object type into another) from the string, the unary or negation operator performs the respective mathematical operation on the -5 to convert it to -5 or 5 respectively.

So, where does that leave us? Sure, we can cast out numbers until we’re blue in the face. But what about other kinds of strings, what about arrays, objects, dates, booleans? Could we cast out a number from a function?

The answer is yestechnically. What if we had a string that had a combination of letters and numbers, or starting with a number, or numbers at the end, or no numbers at all? Would an empty string cast out?

I’ve taken the liberty of doing these for you. I’ve shown the result after the “//” in each example. Let’s start with strings:

+"7 monkeys" // NaN

NaN means “Not a Number”, even though typeof(+”7 monkeys”) yields “number”, so apparently “Not a Number” is still a number…? Generally +x should for all intensive purposes yield “number”, but because “7 monkeys” or any similar string cannot be completely coerced into a number, Not a Number results. Strangely though, parseInt(“7 monkeys”) and parseFloat(“7 monkeys”) both yield 7. I will talk about these functions in a later post.

-"7 Monkeys" // also yields NaN
+"3+3" // NaN

The above example threw me at first, after all, with +”3+3″ one would think the unary operator would evaluate the string and return 6… Not so. Unary and Negation operators DO NOT evaluate the contents of a string, in fact they don’t evaluate anything. Unary and Negation operators will only do the following:

  • A unary or negation operator will first coerce the object used against the operator to a number based on the content of the object.
  • If the unary operator is used, the system will then work out the resulting number based on standard mathematical rules based on placing a positive sign in front of it.
  • If the negation operator is used, the system will then work out the resulting number based on standard mathematical rules based on placing a negative sign in front of it.
  • Unary and Negation operators will work only on strings that are formatted as recognized numbers within JavaScript.

Note that last point… For a string to be correctly coerced to a number, the initial string has to be formatted like a JavaScript number.

Generally a JavaScript number is formatted in one of three ways:

  • ±A (where A represents a series of integers (containing 1 or more digits)
  • ±A.B (where A and B represent two series of integers (containing 1 or more digits) on either side of the decimal point
  • ±A.Be±C (where A, B and C represent three series of integers (containing 1 or more digits), and e (or E) represents the 10C exponential function. Technically this will be the same as ±A.B × 10±C. So, for example, 7.56e3 = 7.56 × 103 = 7.56 × 1000 = 7560, and 4.2e-2 = 4.2 × 10-2 = 4.2 × 0.01 = 0.042.

One exception to the rule is that a number in JavaScript can be represented with a decimal point but nothing following it. So, +”7.” will coerce into 7, and +”7.e2″ will coerce to 700. but +”7.e2.3″ will render out as a Syntax Error due to the fact that the exponential needs to be an integer, and not in this case, 2.3.

+”foo” // NaN

In the conversion of a string to a number, if the number does not match the conventional JavaScript number formats I mentioned earlier, the only other alternative is for it to render out as Not a Number (NaN).

I will provide further insight into these operators and their interactions with other JavaScript object types in my next post.