Chapter 21: Factors and Polynomials
In this chapter we look at the built-in functions p:, q: and p.
21.1 Primes and Factors
The built-in function monadic q: computes the prime factors of a given number.
The number 0 is not in the domain of q: The number 1 is in the domain of q:, but is regarded as having no factors, that is, its list of factors is empty.
For large numbers, the value can be given as an extended integer to avoid a domain error.
A prime number is the one and only member of its list of factors. Hence a test for primality can readily be written as the hook: member-of-its-factors
Any positive integer can be written as the product of powers of successive primes. Some of the powers will be zero. For example we have:
9 = (2^0) * (3^2) * (5^0) * (7^0) 1
The list of powers, here 0 2 0 0 ... can be generated with dyadic q:. The left argument x specifies how many powers we choose to generate.
Giving a left argument of "infinity" (_) means that the number of powers generated is just enough, in which case the last will be non-zero.
There is a built-in function, monadic p: (lowercase p colon) which generates prime numbers. For example (p: 17) is the 18th prime.
On my computer the largest prime which can be so generated is between p: 2^26 and p: 2^27.
If x is a variable, then an expression in conventional notation such as
a + bx + cx2 + dx3 + ...
is said to be a polynomial in x. If we write C for the list of coefficients a,b,c,d ... and assign a value to x, then the polynomial expression can be written in J in the form +/ C * x ^ i. # C
The dyadic verb p. allows us to abbreviate this expression to C p. x,
The scheme is that, for a list of coefficients C:
C p. x means +/ C * x ^ i. # C
A polynomial function is conveniently written in the form C&p.
This form has a number of advantages: compact to write, efficient to evaluate and (as we will see) easy to differentiate.
Given a list of coefficients C, we can compute the roots of the polynomial function C&p. by applying monadic p. to C.
We see that the result Z is a boxed structure, of the form M;R, that is, multiplier M followed by list-of-roots R. We expect to see that p applied to each root in R gives zero.
The significance of the multiplier M is as follows. If we write r,s,t... for the list of roots R,
'r s' =: R
then M is such that the polynomial C p. x can be written equivalently as
M * (x-r)*(x-s) 3
or more compactly as
M * */x-R 3
We saw that monadic p., given coefficients C computes multiplier-and-roots M;R. Furthermore, given M;R then monadic p. computes coefficients C
21.2.3 Dyadic p. Revisited
We saw above that the left argument of p. can be a list of coefficents, with the scheme
C p. x is +/ C * x ^ i. #c
The left argument of p. can also be of the form multiplier;list-of-roots. In this way we can generate a polynomial function with specified roots. Suppose the roots are to be 2 3
The scheme is that
(M;R) p. x means M * */ x - R
When M;R is p. C then we expect (M;R) p. x to be the same as C p. x
Where there are many zero coefficients in a polynomial, it may be more convenient to write functions in the "multinomial" form, that is, omitting terms with zero coefficents and instead specifying a list of coefficient-exponent pairs. Here is an example. With the polynomial _1 0 1 & p., the nonzero coefficents are the first and third, _1 1, and the corresponding exponents are 0 2. We form the pairs thus:
Now the pairs can be supplied as boxed left argument to p. We expect the results to be the same as for the original polynomial.
With the multinomial form, exponents are not limited to non-negative integers. For example, with exponents and coefficients given by:
E =: 0.5 _1 2j3 C =: 1 1 1
then the multinomial form of the function is:
f =: (< C,.E) & p.
and for comparison, an equivalent function:
g =: 3 : '+/ C * y. ^ E'
This is the end of Chapter 21.
Table of Contents
Copyright © Roger Stokes 2001. This material may be freely reproduced, provided that this copyright notice, including this provision, is also reproduced.
last updated 09 Jan 2001