Chapter 21: Factors and Polynomials
In this chapter we look at the built-in functions:
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.
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 ..., for example,
C =: _1 0 1
and assign a value to x, for example,
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.
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 Multiplier and Roots
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
The examples in this chapter
were executed using J version 601-o-beta.
This chapter last updated 23 Jun 2006 .
Copyright © Roger Stokes 2006. This material may be freely reproduced, provided that this copyright notice is also reproduced.