$SPAD/src/input fr.input

Timothy Daly December 3, 2016

Abstract

Contents

2

1 License

— license —

--Copyright The Numerical Algorithms Group Limited 1991.

———-

— * —

)set break resume
)spool fr.output
)set message test on
)set message auto off
)clear all
--S 1 of 55
(x,y,z,w): FR INT
--R
--R                                                                   Type: Void
--E 1

———-

Automatic coercion of integers to factored integers — * —

--S 2 of 55
x := 2**8 * 78**7 * 111**3 * 74534
--R
--R
--R         16 10  7  3
--R   (2)  2  3  13 37 83 449
--R                                                      Type: Factored(Integer)
--E 2
--S 3 of 55
y := 2**4 * 45**3 * 162**6 * 774325
--R
--R
--R         10 30 5
--R   (3)  2  3  5 47 659
--R                                                      Type: Factored(Integer)
--E 3

———-

Computation of 50!

— * —

--S 4 of 55
z1 := factorial 50
--R
--R
--R   (4)  30414093201713378043612608166064768844377641568960512000000000000
--R                                                        Type: PositiveInteger
--E 4
--S 5 of 55
z := z1 :: (FR INT)
--R
--R
--R         47 22 12 8  4  3  2  2  2
--R   (5)  2  3  5  7 11 13 17 19 23 29 31 37 41 43 47
--R                                                      Type: Factored(Integer)
--E 5

———-

Examine the structure if a factor — * —

--S 6 of 55
nthFactor(z,1)
--R
--R
--R   (6)  2
--R                                                        Type: PositiveInteger
--E 6
--S 7 of 55
nthFlag(z,1)
--R
--R
--R   (7)  "prime"
--R                                                     Type: Union("prime",...)
--E 7
--S 8 of 55
nthExponent(z,1)
--R
--R
--R   (8)  47
--R                                                        Type: PositiveInteger
--E 8

———-

Extract the factors in another form — * —

--S 9 of 55
factorList z
--R
--R
--R   (9)
--R   [[flg= "prime",fctr= 2,xpnt= 47], [flg= "prime",fctr= 3,xpnt= 22],
--R    [flg= "prime",fctr= 5,xpnt= 12], [flg= "prime",fctr= 7,xpnt= 8],
--R    [flg= "prime",fctr= 11,xpnt= 4], [flg= "prime",fctr= 13,xpnt= 3],
--R    [flg= "prime",fctr= 17,xpnt= 2], [flg= "prime",fctr= 19,xpnt= 2],
--R    [flg= "prime",fctr= 23,xpnt= 2], [flg= "prime",fctr= 29,xpnt= 1],
--R    [flg= "prime",fctr= 31,xpnt= 1], [flg= "prime",fctr= 37,xpnt= 1],
--R    [flg= "prime",fctr= 41,xpnt= 1], [flg= "prime",fctr= 43,xpnt= 1],
--R    [flg= "prime",fctr= 47,xpnt= 1]]
--IType: List(Record(flg: Union("nil","sqfr","irred","prime"),...
--E 9

———-

Construct an object that has the factors to multiplicity one — * —

--S 10 of 55
r:=reduce(*,[(nthFactor(z,i) :: (FR INT)) for i in 1..(numberOfFactors z)])
--R
--R
--R   (10)  2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
--R                                                      Type: Factored(Integer)
--E 10

———-

Some arithmetic — * —

--S 11 of 55
exquo(z,r)
--R
--R
--R          46 21 11 7  3  2
--R   (11)  2  3  5  7 11 13 17 19 23
--R                                           Type: Union(Factored(Integer),...)
--E 11
--S 12 of 55
x*y
--R
--R
--R          26 40 5  7  3
--R   (12)  2  3  5 13 37 47 83 449 659
--R                                                      Type: Factored(Integer)

--E 12
--S 13 of 55
y*x
--R
--R
--R          26 40 5  7  3
--R   (13)  2  3  5 13 37 47 83 449 659
--R                                                      Type: Factored(Integer)
--E 13
--S 14 of 55
(x*y = y*x) :: BOOLEAN
--R
--R
--R   (14)  true
--R                                                                Type: Boolean
--E 14
--S 15 of 55
gcd(x,z)
--R
--R
--R          16 10  3
--R   (15)  2  3  13 37
--R                                                      Type: Factored(Integer)
--E 15
--S 16 of 55
x+y
--R
--R
--R          10 10
--R   (16)  2  3  1109 3557 2007307818601
--R                                                      Type: Factored(Integer)
--E 16

———-

This is how you multiply the terms together — * —

--S 17 of 55
expand(x+y)
--R
--R
--R   (17)  478786494447911114328204288
--R                                                        Type: PositiveInteger
--E 17

———-

Now look at quotients — * —

--S 18 of 55
f := x/y
--R
--R
--R          6  7  3
--R         2 13 37 83 449
--R   (18)  --------------
--R            20 5
--R           3  5 47 659
--R                                            Type: Fraction(Factored(Integer))
--E 18
--S 19 of 55
g := (x ** 9) / y
--R
--R
--R          134 60  63  27  9   9
--R         2   3  13  37  83 449
--R   (19)  ----------------------
--R                 5
--R                5 47 659
--R                                            Type: Fraction(Factored(Integer))
--E 19
--S 20 of 55
f * g
--R
--R
--R          140 40  70  30  10   10
--R         2   3  13  37  83  449
--R   (20)  ------------------------
--R                 10  2   2
--R                5  47 659
--R                                            Type: Fraction(Factored(Integer))
--E 20
--S 21 of 55
(f * g) / (g * primeFactor(2,200))
--R
--R
--R             7  3
--R           13 37 83 449
--R   (21)  ---------------
--R          194 20 5
--R         2   3  5 47 659
--R                                            Type: Fraction(Factored(Integer))

--E 21
--S 22 of 55
(f * g) / (g * primeFactor(2,200)) * z
--R
--R
--R          2 7 8  4  10  2  2  2        4
--R         3 5 7 11 13  17 19 23 29 31 37 41 43 83 449
--R   (22)  -------------------------------------------
--R                            147
--R                           2   659
--R                                            Type: Fraction(Factored(Integer))
--E 22

———-

Manipulation of factored polynomials — * —

)clear all
--S 23 of 55
(u,v,w): FR POLY INT
--R
--R                                                                   Type: Void
--E 23

———-

Coercion to FR POLY INT involves factoring — * —

--S 24 of 55
u := (x**4 - y**4) :: POLY INT
--R
--R
--R                          2    2
--R   (2)  - (y - x)(y + x)(y  + x )
--R                                          Type: Factored(Polynomial(Integer))
--E 24

———-

PrimeFactor creates factors that are asserted to be prime — * —

--S 25 of 55
v := primeFactor(x-y,2) * primeFactor(x+y,2) * primeFactor(x**2 + y**2,1)
--R
--R
--R               2       2  2    2

--R   (3)  (y - x) (y + x) (y  + x )
--R                                          Type: Factored(Polynomial(Integer))
--E 25
--S 26 of 55
w := factor(x**2 + 2*x*y + 2*x + 2*y + y**2 + 1) * primeFactor(x-y,2)
--R
--R
--R               2           2
--R   (4)  (y - x) (y + x + 1)
--R                                          Type: Factored(Polynomial(Integer))
--E 26
--S 27 of 55
unit w
--R
--R
--R   (5)  1
--R                                                    Type: Polynomial(Integer)
--E 27

———-

Some ways of looking at the components of an elements of FR P I — * —

--S 28 of 55
l := factorList u
--R
--R
--R   (6)
--R   [[flg= "prime",fctr= y - x,xpnt= 1], [flg= "prime",fctr= y + x,xpnt= 1],
--R                         2    2
--R    [flg= "prime",fctr= y  + x ,xpnt= 1]]
--IType: List(Record(flg: Union("nil","sqfr","irred","prime"),...
--E 28
--S 29 of 55
factorList v
--R
--R
--R   (7)
--R   [[flg= "prime",fctr= y - x,xpnt= 2], [flg= "prime",fctr= y + x,xpnt= 2],
--R                         2    2
--R    [flg= "prime",fctr= y  + x ,xpnt= 1]]
--IType: List(Record(flg: Union("nil","sqfr","irred","prime"),...
--E 29
--S 30 of 55
factorList w

--R
--R
--R   (8)
--R   [[flg= "prime",fctr= y - x,xpnt= 2],[flg= "prime",fctr= y + x + 1,xpnt= 2]]
--IType: List(Record(flg: Union("nil","sqfr","irred","prime"),...
--E 30
--S 31 of 55
l.1.fctr
--R
--R
--R   (9)  y - x
--R                                                    Type: Polynomial(Integer)
--E 31
--S 32 of 55
l.1.xpnt
--R
--R
--R   (10)  1
--R                                                        Type: PositiveInteger
--E 32
--S 33 of 55
nthFactor(u,1)
--R
--R
--R   (11)  y - x
--R                                                    Type: Polynomial(Integer)
--E 33
--S 34 of 55
nthFactor(u,2)
--R
--R
--R   (12)  y + x
--R                                                    Type: Polynomial(Integer)
--E 34
--S 35 of 55
nthFactor(u,3)
--R
--R
--R          2    2
--R   (13)  y  + x
--R                                                    Type: Polynomial(Integer)
--E 35
--S 36 of 55
nthExponent(u,3)

--R
--R
--R   (14)  1
--R                                                        Type: PositiveInteger
--E 36
--S 37 of 55
nthFlag(u,3)
--R
--R
--R   (15)  "prime"
--R                                                     Type: Union("prime",...)
--E 37
--S 38 of 55
nthFactor(u,4)
--R
--R
--R   (16)  1
--R                                                    Type: Polynomial(Integer)
--E 38

———-

This computes a factored object that is similar to v except that each factor occurs with multiplicity 1

— * —

--S 39 of 55
s:=reduce(*,[(nthFactor(v,i) :: FR POLY INT) for i in 1..(numberOfFactors v)])
--R
--R
--R                         2    2
--R   (17)  (y - x)(y + x)(y  + x )
--R                                          Type: Factored(Polynomial(Integer))
--E 39

———-

Some arithmetic — * —

--S 40 of 55
exquo(v,s)
--R
--R
--R   (18)  (y - x)(y + x)
--R                               Type: Union(Factored(Polynomial(Integer)),...)
--E 40
--S 41 of 55

gcd(u,v)
--R
--R
--R                         2    2
--R   (19)  (y - x)(y + x)(y  + x )
--R                                          Type: Factored(Polynomial(Integer))
--E 41
--S 42 of 55
u + v
--R
--R
--R                         2    2       2    2
--R   (20)  (y - x)(y + x)(y  - x  - 1)(y  + x )
--R                                          Type: Factored(Polynomial(Integer))
--E 42
--S 43 of 55
lcm(v,w)
--R
--R
--R                2       2           2  2    2
--R   (21)  (y - x) (y + x) (y + x + 1) (y  + x )
--R                                          Type: Factored(Polynomial(Integer))
--E 43
--S 44 of 55
u * v * w
--R
--R
--R                  5       3           2  2    2 2
--R   (22)  - (y - x) (y + x) (y + x + 1) (y  + x )
--R                                          Type: Factored(Polynomial(Integer))
--E 44

———-

The function expand multiplies the factors together — * —

--S 45 of 55
expand(u * v * w)
--R
--R
--R   (23)
--R        14     13      2           12      2       11       4     3  10
--R     - y   - 2y   + (3x  + 2x - 1)y   + (4x  + 2x)y   + (- x  - 4x )y
--R   +
--R        4     3  9        6     5     4  8        6     5  7      8     7  6
--R     (2x  - 2x )y  + (- 5x  - 2x  + 3x )y  + (- 8x  - 4x )y  + (5x  + 8x )y

--R   +
--R        8     7  5     10     9     8  4      10     9  3        12     11  2
--R     (2x  + 4x )y  + (x   - 2x  - 3x )y  + (4x   + 2x )y  + (- 3x   - 4x  )y
--R   +
--R          12     11      14     13    12
--R     (- 2x   - 2x  )y + x   + 2x   + x
--R                                                    Type: Polynomial(Integer)
--E 45

———-

Some quotients — * —

--S 46 of 55
u/w
--R
--R
--R                      2    2
--R             (y + x)(y  + x )
--R   (24)  - -------------------
--R                             2
--R           (y - x)(y + x + 1)
--R                                Type: Fraction(Factored(Polynomial(Integer)))
--E 46
--S 47 of 55
w/(u*v)
--R
--R
--R                             2
--R                  (y + x + 1)
--R   (25)  - -------------------------
--R                         3  2    2 2
--R           (y - x)(y + x) (y  + x )
--R                                Type: Fraction(Factored(Polynomial(Integer)))
--E 47

———-

The form %%(-1) is the last result, %%(-2) is the one before that — * —

--S 48 of 55
w/(u*v) * u/w
--R
--R
--R                     1
--R   (26)  -------------------------
--R                2       2  2    2
--R         (y - x) (y + x) (y  + x )

--R                                Type: Fraction(Factored(Polynomial(Integer)))
--E 48
--S 49 of 55
w/(u*v) + u/w
--R
--R
--R   (27)
--R   -
--R           10       9     2 8      3 7      4 6      5 5       6      4
--R          y   + 4x y  + 9x y  + 16x y  + 22x y  + 24x y  + (22x  + 1)y
--R        +
--R              7           3      8     2            2
--R          (16x  + 4x + 4)y  + (9x  + 6x  + 12x + 6)y
--R        +
--R             9     3      2                10    4     3     2
--R          (4x  + 4x  + 12x  + 12x + 4)y + x   + x  + 4x  + 6x  + 4x + 1
--R     /
--R                      3           2  2    2 2
--R        (y - x)(y + x) (y + x + 1) (y  + x )
--R                                Type: Fraction(Factored(Polynomial(Integer)))
--E 49
--S 50 of 55
differentiate(w,x)
--R
--R
--R   (28)  - 2(2x + 1)(y - x)(y + x + 1)
--R                                          Type: Factored(Polynomial(Integer))
--E 50
--S 51 of 55
differentiate(w,y)
--R
--R
--R   (29)  2(y - x)(y + x + 1)(2y + 1)
--R                                          Type: Factored(Polynomial(Integer))
--E 51
--S 52 of 55
associates?(x,-x)
--R
--R
--R   (30)  true
--R                                                                Type: Boolean
--E 52
--S 53 of 55
characteristic()$FR POLY INT
--R

--R
--R   (31)  0
--R                                                     Type: NonNegativeInteger
--E 53
--S 54 of 55
1$FR POLY INT
--R
--R
--R   (32)  1
--R                                          Type: Factored(Polynomial(Integer))
--E 54
--S 55 of 55
0$FR POLY INT
--R
--R
--R   (33)  0
--R                                          Type: Factored(Polynomial(Integer))
--E 55
)spool
)lisp (bye)

———-

References^{[1] nothing}

16