Finding pi in pi with Perl

Here's a frivolous problem whose solution illustrates three features of Perl:

1. Arbitrary precision floating point
2. Lazy quantifiers in regular expressions
3. Returning the positions of matched groups.

Our problem is to look for the digits 3, 1, 4, and 1 in the decimal part of .

First, we get the first 100 digits of after the decimal as a string. (It turns out 100 is enough, but if it weren't we could try again with more digits.)

 use Math::BigFloat "bpi"; $x = substr bpi(101)->bstr(), 2;

This loads Perl's extended precision library Math::BigFloat, gets to 101 significant figures, converts the result to a string, then lops off the first two characters 3." at the beginning leaving 141592...".

Next, we want to search our string for a 3, followed by some number of digits, followed by a 1, followed by some number of digits, followed by a 4, followed by some number of digits, and finally another 1.

A naive way to search the string would be to use the regex /3.*1.*4.*1/. But the star operator is greedy: it matches as much as possible. So the .* after the 3 would match as many characters as possible before backtracking to look for a 1. But we'd like to find the first 1 after a 3 etc.

The solution is simple: add a ? after each star to make the match lazy rather than greedy. So the regular expression we want is

 /3.*?1.*?4.*?1/

This will tell us whether our string contains the pattern we're after, but we'd like to also know where the string contains the pattern. So we make each segment a captured group.

 /(3.*?)(1.*?)(4.*?)(1)/

Perl automatically populates an array @- with the positions of the matches, so it has the information we're looking for. Element 0 of the array is the position of the entire match, so it is redundant with element 1. The advantage of this bit of redundancy is that the starting position of group $1 is in the element with index 1, the starting position of $2 is at index 2, etc.

We use the shift operator to remove the redundant first element of the array. Since shift modifies its argument, we can't apply it directly to the constant array @-, so we apply it to a copy.

 if ($x =~ /(3.*?)(1.*?)(4.*?)(1)/) { @positions = @-; shift @positions; print "@positions\n"; }

This says that our pattern appears at positions 8, 36, 56, and 67. Note that these are array indices, and so they are zero-based. So if you count from 1, the first 3 appears in the 9th digit etc.

To verify that the digits at these indices are 3, 1, 4, and 1 respectively, we make the digits into an array, and slice the array by the positions found above.

 @digits = split(//, $x); print "@digits[@positions]\n";

This prints 3 1 4 1 as expected.

The post Finding pi in pi with Perl first appeared on John D. Cook.