Help / Learning / Ch 21: Factors and Polynomials

From J Wiki
Jump to navigation Jump to search


>> << Pri JfC LJ Phr Dic Voc !: Rel NuVoc 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   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.

NEXT
Table of Contents
Index

The examples in this chapter were executed using J version 701. This chapter last updated 29 Jul 2012
Copyright © Roger Stokes 2012. This material may be freely reproduced, provided that this copyright notice is also reproduced.

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

Retrieved from "https://code.jsoftware.com/mediawiki/index.php?title=Help/Learning/Ch_21:_Factors_and_Polynomials&oldid=40380"