PWC #170

Perl weekly challenge #170

In Perl weekly challenge #170, we are asked to complete two tasks in Perl 5 and/or Raku.

Challenge 1

Compute a primorial number primorial(n) P_n(n) = P(1)*P(2)*...*P(n) where P(i) is the i'th prime, e.g., P(1)=2, P(2)=3, ... Like a factorial, except multiplying primes in sequence rather than positive integers. The challenge requires listing the first 10 primorials.

I used the Math::Prime::Util::GMP library, which I had used earlier for Challenge #168, which included a compute-intensive task involving primes. For that challenge, this library gave speed and power rivaling optimized C code. It is a very impressive library. If I ever need to do serious work involving big prime numbers, Perl would be a top choice because of this.

The library has two different built-in functions directly calculating primorials. I would have just used one of them if I had read the meta-CPAN docs carefully enough (even if just for a code challenge, why write an interpreted home-made function when a very fast library function does the same thing much better). But I did not read the docs carefully enough, and just picked up the next_prime function. The function next_prime(x) finds the next prime number after integer x, e.g., next_prime(2) is 3.
 

It is a straightforward recursive solution, which defines P_n(0) as 1, and then computes P_n(n) recursively as P_n(n-1)*P(n). P(n) is in turn computed recursively as the next_prime to the (n-1)'th prime P(n-1). I write another recursive sub to compute the i'th prime P(i) (unnecessarily, because Math::Prime::Util::GMP has another built-in for this).
 
This is not modern Perl, and leans more to the pink-camel perl 4 style of doing things. Variables live on the stack with local (dynamic) scope and nth_prime is written as a nested sub assigned using a typeglob alias (not really necessary to nest it, but just to demonstrate this approach). I often like doing things this way, and a modern "best-practices" approach would not be materially better for this task. TIMTOWTDI, eh?

In Raku, I'm sure there are cool ways to do this task using lazily evaluated infinite sequences, among other weird cool things. I did not think too deeply about it though and just translated my Perl 5 code. My Raku script does demonstrate the use of Inline::Perl to call the Perl 5 Math::Prime::Util::GMP library (works flawlessly, no tweaking was needed).
 
 

Challenge 2

Challenge 2 asks us to write a program to compute a kronecker product of two matrices.  This is a very standard part of linear algebra and the Math::Matrix library has a built-in operator to do it.  The library is available in both Perl 5 and Raku versions.
 
For Raku, I just used the library operator. Here it is:
 
 
Math::Matrix (in both versions) implements a matrix as an array of arrays. In Perl 5, I was interested in trying to do it with the old approach of modelling a matrix as a hash (i,e., 2nd row and 3rd column of matrix A implemented as $A{'2,3'}). The bareword A{2,3} used to be allowed, but that's now deprecated and on the way out in Perl 7. 
 
To do this, I again used a non-modern early 90's style approach (why not, eh) using typeglobs combined with the "local" keyword (dynamic scope). 
 
To find C=kronecker (A,B) we return a matrix where each element a[ij] of A is replaced by a B-sized matrix made up of B scalar-multiplied element-wise by a[ij] or (A[i,j] .* B) in Matlab / Octave / Julia syntax.
 
I do this in two steps:
  1. A hash C_wip whose keys "i,j" are the same as those of A, and whose value for key "i,j" ia a stringified (':'-joined) list of the key-value pairs in B*a[i,j].
  2. A regular matrix C derived from C_wip where the keys are the usual "row number, column number"  for the kronecker product and the value is the scalar entry at that cell. I achieve this by splitting the stringified values in C_wip and inserting the keys using a regex.
Here is my Perl 5 solution.
 

 Julia

I also did the challenges in Julia, as a benchmark. For the kronecker product, Julia has a built-in function. For the primorial, I just translated my Perl 5 script. A mild quirk is that Julia's nextprime function treats nextprime(2) as 2 (not 3), so one has to do nextprime(x+1) to get the desired effect.
 
 
 
 

Someone else's solution (Wow!)

Not sure if it's kosher to comment on other people's solutions, but anyway this one-liner is amazing (from Philippe Bricout alias brxfork):

This is for the primorial. Here it is again: (accessed 24-6-2022)

perl -E 'while(@p < 10) { $_.="x";/^(.{2,})\1+$/ or push @p,($p[-1]//1)*length};say "@p"'
 
It took me a while to figure it out. What it does is write a growing string of x'es (could be any character repeated), as in xxxxxx....
 
This gets passed to the (very clever!) regex /^(.{2,})\1+$/ . The first capture ^(.{2,}) picks up any string of x'es repeated at least twice, such as "xx", "xxx", "xxxx" etc. 

The \1+$ proceeds to check if any of the captured matches ($1) is repeated throughout the rest of the string. If that is not true, then the length of the "xxxx.." string is a prime! Otherwise, it's not a prime.

(Consider for example "xxxxxxxxx" (9), which is  the pattern xxx repeated 3 times (3*3), and matches the regex: not a prime. The string "xxxxxxx" (7) on the other hand cannot be analyzed as any pattern "xx.." of two or more x'es repeated throughout the string (i.e. its length cannot be expressed as m*n, where both m and n are integers greater than 1, which means it's a prime (that's the definition).))

The rest of the one-liner multiplies a prime when found (regex failed) into the product of the previously found primes (last item in the return list p) and then pushes the answer into the return list p.

It runs in around 0.003s compared to around 0.02s for my try (I have some startup overhead due to the library call, but still.)

Comments

Popular posts from this blog

PWC 215

PWC 227

PWC 234