Chapter 21: Factors and PolynomialsIn this chapter we look at the built-in functions:
21.1 Primes and FactorsThe 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 a large number (greater than about 2^53), its value should be specified as an extended integer to ensure all its significant digits are supplied to q: ..
q: 1 + 2 ^ 53x 3 107 28059810762433A 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) 1The 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.
On my computer the largest prime which can be so generated is between p: 2^26 and p: 2^27.
21.2.1 CoefficientsIf 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 1and assign a value to x, for example,
x=:2then 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. # CA polynomial function is conveniently written in the form C&p.
21.2.2 RootsGiven 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' =: Rthen M is such that the polynomial C p. x can be written equivalently as
M * (x-r)*(x-s) 3or more compactly as
M * */x-R 3We 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 RootsWe saw above that the left argument of p. can be a list of coefficents, with the scheme
C p. x is +/ C * x ^ i. # CThe 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 - RWhen M;R is p. C then we expect (M;R) p. x to be the same as C p. x
21.2.4 MultinomialsWhere 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 1then the multinomial form of the function is:
f =: (< C,.E) & p.and for comparison, an equivalent function:
g =: 3 : '+/ C * y ^ E'We see
This is the end of Chapter 21.
Table of Contents
The examples in this chapter
were executed using J version j701/beta/2010-11-24/22:45.
This chapter last updated 22 Dec 2010
Copyright © Roger Stokes 2010. This material may be freely reproduced, provided that this copyright notice is also reproduced.