Number of Pi in file – Perl weekly challenge, week 4

A new challenge appears!

How much π in your script?

At first glance, part 1 of this challenge is pretty simple:

printf "%.16f",pi

Of course, I had to create the file using echo to avoid have a newline at the end. Look close and there’s a problem though.

$ perl6 ch-1.p6
3.1415926535897930

That’s almost but not quite 16 significant digits of pi. I’m keeping this as a first solution though, because IMHO it should be the answer.

Okay, time to break out the cynicallest solution for perl6:

pi.\        put

15 significant digits of π for 15 characters, including the line break 🤪.

Now let’s get serious. Number sequences were actually one of my favourite parts of Mathematics, and when the world presents me with an opportunity to strike a Calculating π shaped nail, I’m going to hit it with my convergent sequence hammer.

Isn’t that a bit far away from the original question?

Yeah, I doubt this was the challenge’s intention; I’m doing it anyway.

Interestingly enough, revisiting last week’s challenge brought up something about calculating π using Pascal’s Triangle; apparently since I was last doing things with Blaise Pascal’s work in high school, one Jonas Castillo Toloza discovered another place it exposed π – in the triangular numbers.

I implemented this in Perl6; it went something like this:

my $Ts := lazy gather loop (my $n = 1;;) {
  for 1, 1, -1, -1 -> $m {
    take ($m / ($n * ($n + 1) / 2));
    $n++;
  }
}

my $π = 2 + [+] $Ts[^$lim];

Which is functional, and if you try out a couple of different sizes of $lim you can see it converging; keeping in mind that Perl6’s pi is apparently accurate to the 15 digits it has:

> pi
3.141592653589793
> 2 + [+] $Ts[^2000]
3.1415921540896665
> 2 + [+] $Ts[^80000] # Jump of 40x, 3 digits closer
3.1415926532772707
> 2 + [+] $Ts[^160000] # 2x, one more digit
3.1415926535116068
> 2 + [+] $Ts[^320000] # 2x, closer but 11th digit is still wrong
3.141592653570272
> 2 + [+] $Ts[^640000] # 2x again, there we go
3.1415926535849534
> 2 + [+] $Ts[^2**20] # 1048576; many iterations
3.1415926535880487
> pi
3.141592653589793

… that’s a whole megasequence to still be accurate accurate to only 12 digits. That speed of convergence is effectively nonfunctional.

I’ve used a much faster algorithm in the past; The Euler Convergence Transformation, which is:

\frac{π}{2} = \sum_{k = 0}^{\infty} \frac{k!}{(2 k + 1)!!} = \sum_{k = 0}^{\infty} \frac{2^{k} k!^{2}}{(2 k + 1)!} = 1 + \frac{1}{3} (1 + \frac{2}{5} (1 + \frac{3}{7} (1 + \dots)))

(Where k!! is the odd-only factorial of k)

Now, we could implement the sequence discretely according to probably the second summation (this k!! seems a bit of a pain to implement), but if you squint a bit at the right hand sequence, it looks a bit like:

\frac{π}{2} = \sum_{k = 0}^{\infty} n_{k} where n_{0} = 1; n_{k} = n_{k - 1} \cdot \frac{k}{2 k + 1}

Which saves us some calculation as during a gather / take we already know what n_k-1 is. Throw it together, sum the results, multiply by two, and Bob’s yer uncle.

While we’re at it, we’ll use FatRats to be away with those pesky IEE754 floats and their imprecision.

Through some analysis I found that 608 iterations was enough to give me 177 correct significant digits, which is the final size of the script; that’s quite a lot better than 1M iterations to get 12…

Algorithmic Script Size

‘Enough tedious maths!’ you say, ‘tell us something about programming!’

Cool feature of Perl 6 – you can find the size of the current script using $?FILE.IO.s. To round out the script I used that (+ 1 for the decimal point) as the end of the substring of my calculated π.

See my solution at https://github.com/fjwhittle/perlweeklychallenge-club/blob/master/challenge-004/fjwhittle/perl6/ch-1.p6

Letters in words in list in … ?

Part 2 of the week 4 challenge starts with “You are given a file containing a list of words (case insensitive 1 word per line) and a list of letters” however doesn’t provide any such data. I have to admit I’m not a big fan of challenges with undefined data sets, although I can also certainly appreciate that providing data for testing is potentially not something challenge authors have time for. The challenge itself is fairly similar to an anagram generator I had a go at making for my own fun some time back (around the release of 6.c).

Finding data.

Hmm. Where would I find a list of words lying around waiting to be used?

$ time perl6 -e 'put + "/usr/share/dict/british-english".IO.lines.unique'
101921

real	0m0.593s
user	0m0.671s
sys	0m0.065s

Seems reasonable. Next step is to get a list of letters… Oh, let’s just use command line arguments.

One of my favourite things about Perl 6 is how easy it is to get arguments from the command line. I normally make my main script file unit sub MAIN();, which lets me treat it otherwise like a script. I can then use Pod to document the options as well.

#| Find words in a file that contain only the given letters
unit sub MAIN(
  Str $file #= file containing list of words
    where { given .IO { .r && ( .l || .f) or die "Cannot read from $_" }  } #= file containing list of words
  *@letters #= list of letters to search for
);

We’ll approach the problem using Bags and the subsets thereof. We use Bags instead of Sets to count duplicate letters.

We’ll comb through each of the gobbled arguments for letters, which will allow the user to enter words on the command line, so map the @letters array to lower-case, comb each argument for letters, flatten, and convert to a bag..

my $letter-bag := @letters.hyper.map(*.lc.comb(/ \w /)).flat.Bag;

.hyper makes the .map happen in parallel. Maybe not a huge deal for this step, however when now building a list of word bags out of a 102000 line file it makes the 30 second process take 10 (on my system – an old Athlon II. It doesn’t even have SSEv4, but it does have 4 cores).

my @words = $file.IO.lines.unique.hyper.grep(*.chars > 2)
                 .map: { .lc.comb(/ \w /).Bag => $_ };

Use of a pair here allows us to map a word bag to the unmodified word preserving order, punctuation, and case. It’s now a pretty simple task to find our words; we just grep the @words list for a key that’s a subset of or equal to the $letter-bag using the ⊆ operator, and print out the corresponding values.

$ perl6 ch-2.p6 /usr/share/dict/british-english hello dolly
Dell, Doe, Dole, Dolly, Dooley, Doyle, Eloy, Hell, Holley, Holly, Hood, Hoyle,
Hyde, Leo, Lloyd, Loyd, Lyell, Lyle, Odell, doll, dye, ell, he'd, he'll, held,
hello, hey, hod, hoe, hoed, hold, hole, holed, holy, hooey, led, lode, loll,
lolled, lye, ode, oho, old, oleo, yell, yodel

Looks good to me 😊. See the full solution at https://github.com/fjwhittle/perlweeklychallenge-club/blob/master/challenge-004/fjwhittle/perl6/ch-2.p6