Fun with APL: Rational Zeros Theorem

I had the occasion today to revisit the Rational Zeros Theorem. It took me all of one minute to realize that this was a great thing to express with APL. Here's the core idea of the Theorem:

Given a polynomial with integer coefficients, the potential rational roots of the polynomial are of the form P / Q where P is a member of the factors of the coeffecient of the lowest degree term, and Q is a member of the factors of the coeffecient of the highest degree term, where P and Q can have either sign.

This actually turns out to be pretty easy to express. The idea is to have an expression which generates a two row, N column matrix of numerators (first row) and denominators (second row), given the coeffecients of P represented as a Vector. Let's get started.

First, let's work out an expression to get the highest degree and lowest degree terms. I'm going to assume that P is sorted from highest to lowest degree. Then we can get the first and last coefficients with the following expression:

⊃¨(⌽P)P 

So, the result of this expression will be a pair with the first element being the lowest degree coeffecient, and the second element being the highest degree coeffecient. Our set of possible numerators will come from the first element, and our possible denominators from the second element.

Next, let's factor these numbers. We do this first by getting the magnitude of the values, without the sign.

|⊃¨(⌽P)P 

Then we generate the intervals [1,N] for each of the numbers:

1+⍳¨|⊃¨(⌽P)P 

This gives us a pair where the first element is the interval for the low degree coeffecient (LDC) and the second element the interval for the high degree coeffecient (HDC). We are going to want to use both of these values in the future, so let's give them names. I'll give the name X to the coeffecients, and Y to the intervals.

Y←1+⍳¨|X←⊃¨(⌽P)P 

Now we can get the residue (remainder) of each of the numbers on the interval. When we have that, we can just look for the zeros in there, and this will tell use the numbers that divide our coeffecient. In the end we want a bitvector mask indicating what numbers in Y are factors.

0=X|⍨Y←1+⍳¨|X←⊃¨(⌽P)P 

Finally, we can use this mask to filter out the appropriate values, and then the rationals are just the outer product pairs of those values, with a little more manipulation we can put them into the shape that we want after we take the outer product of them. The final expression looks like this:

⍉↑,⊃∘.,/Y/⍨¨0=X|⍨Y←1+⍳¨|X←⊃¨(⌽P)P 

After this, we can do some standard reductions along the first axis with ÷ to get the real values of those fractions if we wanted to do so. Another outer product with 1 ¯1 on the real values would get the negative and positive versions of those values as well, giving us some test data that would could run to see which are the actual roots.