# 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