Chapter 21: Factors and Polynomials
In this chapter we look at the builtin functions:
 monadic q: which computes the prime factors of a number
 dyadic q: which represents a number as powers of primes
 monadic p: which generates prime numbers
 dyadic p. which evaluates polynomials
 monadic p. which finds roots of polynomials
21.1 Primes and Factors
The builtin 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.
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 28059810762433
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:
memberofitsfactors
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 nonzero.
_ q: 9 
_ q: 17 * 31 
0 2 
0 0 0 0 0 0 1 0 0 0 1 
There is a builtin 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^{2} + dx^{3} + ...
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,
x=:2
then the polynomial expression
can be written in J in the form +/ C * x ^ i. # C
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,
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 x 
_1 0 1&p. 
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. 
+++
11 _1
+++ 
We see that the result Z is a boxed structure,
of the form M;R, that is, multiplier M
followed by listofroots R.
We expect to see that p applied to
each root in R gives zero.
'M R' =: Z 
R 
p R 
+++
11 _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 * (xr)*(xs)
3
or more compactly as
M * */xR
3
We saw that monadic p., given coefficients C
computes multiplierandroots M;R. Furthermore,
given M;R then monadic p. computes coefficients C
C 
MR =: p. C 
p. MR 
_1 0 1 
+++
11 _1
+++ 
_1 0 1 
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;listofroots.
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 
+++
11 _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 coefficientexponent 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
nonnegative 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.
