57005 or alive

Calculating e with Powershell

Feb 21, 2012 math powershell

Well, I missed posting this for \(e\) day (Feb 7), but better late than never, right?

Everyone’s favorite mathematical constant, \(e = 2.71828\ldots\) , can be expressed in a wide variety of ways.  One of the easier-to-implement and faster-converging representations is the basic reciprocal factorial series representation:

$$e = \sum_{k=0}^{\infty}\frac{1}{k!} = \frac{1}{0!} +\frac{1}{1!} + \frac{1}{2!} + \ldots$$

How can we calculate this in Powershell?  Let’s start with a straightforward implementation, utilizing a Factorial function.

function Factorial([int] $n)
   if($n -le 0){ 1 }
     $result = 1;
     1..$n |%{ $result *= $_}
$e = 0
0..17 |%{ $e += 1/(Factorial $_); $e }

This works well.  The output is a series of closer and closer approximations of \(e\) .  Due to the limitations of floating-point numbers, we don’t gain any more precision after the 18th iteration.

This code works, but can we make it shorter?  What kind of tricks can we utilize to condense the code?  Let’s first replace the Factorial function, since that requires lots of extra code to define.  All that Factorial does (ignoring the $n = 0 case for a moment) is take a sequence of products, of numbers from $n to 1.  Factorial 5 == 5*4*3*2*1.  How could we construct such a product more concisely?

We can create that product string by using the -join operator.

PS> 5..1 -join '*'

That’s really all we need, though, since we can tell Powershell to execute a string as if it were a piece of code by calling Invoke-Expression (alias iex).

PS> iex (5..1 -join '*')

Ta-da!  We have just kludged together a very small Factorial implementation.  It can’t handle the 0 case, but that’s OK, we can set $e = 1 to start with as a workaround, instead of $e = 0.  Combining everything on to a single line, our calculation now looks like

$e = 1; 1..17 |%{ $e += 1/(iex ($_..1 -join '*')); $e }

Wow, that’s a tiny line of code that does a lot.  I sent this one-liner to an internal Powershell users email list at work, thinking that I was very clever.  Of course, it is usually when one feels especially clever that someone even more clever speaks up.  It wasn’t long before this improved version was sent to the email list by someone else:

$e = 1;$d = 1; 1..17 |%{ $d *= $_; $e += 1/$d; $e }

Not only is that code shorter, it is more efficient!  Rather than calculating the entire factorial product at every iteration, this solution builds it up term by term and saves it in the $d variable.  Very nice.

Next, folks pointed out that in Powershell (like in many other languages), variable assignments can be made to return the value that was assigned, as well as do the actual assignment.  This allows us to strip the code down further:

$e = 1;$d = 1; 1..17 |%{ ($e += 1/($d *= $_)) }

Then it was mentioned that we can save a few characters by combining the initial assignment of $e and $d into a multiple-assignment expression:

$e = $d = 1; 1..17 |%{ ($e += 1/($d *= $_)) }

Although it doesn’t save characters, the $e and $d assignment can also be used to return the inital 1 value:

($e = $d = 1)..17 |%{ ($e += 1/($d *= $_)) }

That’s as far as we could condense it.  With this code, all of the math is done with data type System.Double, the .NET double-precision floating point type.  Our final result matches the value of [Math]::E, with 15 digits of precision.

If we want more precision, we can cheaply add a single ’d’ character, which forces all variables to be of type System.Decimal, a larger and more precise data type.  We can now run 27 iterations before an overflow error.  Stripping out all the whitespace, the final tiny calculation comes out to 34 characters of Powershell, giving us 29 digits of precision:

($e=$d=1d)..27|%{($e+=1/($d*=$_))} # 34 chars, the winner!

I haven’t seen a more concise implementation than this yet, though I have given it a shot.  Here are a few that came close:

for($i=$e=$d=1d){($e+=1/($d*=$i++))}       # 36 chars, doesn't stop even when overflows start happening
$i=$d=$e=1d;while($d*=$i++){($e+=1/$d)}    # 39 chars, stops once an overflow occurs
($d=$n=1d)..27|%{$n*=$_;($n++)/($d*=$_)}   # 40 chars
iex "$(($d=1d);1..27|%{$d*=$_;"+1d/$d"})"  # 41 chars, prints only the final value
$o=1d;10..0|%{($o=1+1/(2*$_+1/(1+1/$o)))}  # 41 chars

The last example is using a continued fraction representation of \(e\) rather than the reciprocal factorial.

If anyone can beat 34 chars, I would love to see it!