>>  <<  Usr  Pri  JfC  LJ  Phr  Dic  Rel  Voc  !:  Help  Learning J

# 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 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,

 +/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.

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.

>>  <<  Usr  Pri  JfC  LJ  Phr  Dic  Rel  Voc  !:  Help  Learning J