Chapter 21: Factors and Polynomials
In this chapter we look at the built-in 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 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.
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:
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 + 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,
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. |
+-+----+
|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 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
| 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.
|