>>  <<  Ndx  Usr  Pri  JfC  LJ  Phr  Dic  Rel  Voc  !:  wd  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 &nbsp; 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
3 715827883 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


The examples in this chapter were executed using J version 601-o-beta. This chapter last updated 23 Jun 2006 .
Copyright © Roger Stokes 2006. This material may be freely reproduced, provided that this copyright notice is also reproduced.


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