Ch 21: Factors and Polynomials

| # 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.
`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 + 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`,
`+/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 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.

NEXT
Table of Contents
Index

Copyright © Roger Stokes 2003. This material may be freely reproduced, provided that this copyright notice is also reproduced.

last updated 30 May 2003