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.

q: 6	q: 8	q: 17 * 31	q: 1 + 2^30
2 3	2 2 2	17 31	5 5 13 41 61 1321

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.

q: 0	q: 1	# q: 1
error		0

For large numbers, the value can be given as an extended integer to avoid a domain error.

q: 1 + 2^31	q: 1 + 2^31x
error	3 715827883

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

pr =: e. q:	pr 8	pr 17	pr 1
e. q:	0	1	0

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.

4 q: 9	3 q: 9	2 q: 9	1 q: 9	6 q: 9
0 2 0 0	0 2 0	0 2	0	0 2 0 0 0 0

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.

_ q: 9	_ q: 17 * 31
0 2	0 0 0 0 0 0 1 0 0 0 1

There is a built-in function, monadic p: (lowercase p colon) which generates prime numbers. For example (p: 17) is the 18th prime.

p: 0 1 2 3 4 5 6	p: 17
2 3 5 7 11 13 17	61

On my computer the largest prime which can be so generated is between p: 2^26 and p: 2^27.

p: 2^26	p: 2^27	p: 2^27x
1339484207	error	error

21.2 Polynomials

21.2.1 Coefficients

If x is a variable, then an expression in conventional notation such as

a + bx + cx² + dx³ + ...

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

C =: _1 0 1	x=:2
_1 0 1	2

C	#C	i.#C	x	x^i.#C	C*x^i.#C	+/C*x^i.# C
_1 0 1	3	0 1 2	2	1 2 4	_1 0 4	3

The dyadic verb p. allows us to abbreviate this expression to C p. x,

+/C*x^i.# C	C p. x
3	3

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.

p =: _1 0 1 & p.	p 0 1 2
_1 0 1&p.	_1 0 3

This form has a number of advantages: compact to write, efficient to evaluate and (as we will see) easy to differentiate.

21.2.2 Roots

Given a list of coefficients C, we can compute the roots of the polynomial function C&p. by applying monadic p. to C.

C	p =: C & p.	Z =: p. C
_1 0 1	_1 0 1&p.	+-+----+ |1|1 _1| +-+----+

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.

'M R' =: Z	R	p R
+-+----+ |1|1 _1| +-+----+	1 _1	0 0

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

C	MR =: p. C	p. MR
_1 0 1	+-+----+ |1|1 _1| +-+----+	_1 0 1

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

p =: (1; 2 3) & p.	p 2 3
(1;2 3)&p.	0 0

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

C	MR=: p.C	MR p. x	C p. x
_1 0 1	+-+----+ |1|1 _1| +-+----+	3	3

21.2.4 Multinomials

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:

coeffs =: _1 1	exps=: 0 2	pairs =: coeffs ,. exps
_1 1	0 2	_1 0 1 2

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.

x	pairs	(< pairs) p. x	_1 0 1 p. x
2	_1 0 1 2	3	3

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'
   

We see

x=: 2	f x	g x
2	_0.0337641j3.49362	_0.0337641j3.49362

This is the end of Chapter 21.