Sun May 31 11:44:05 MDT 1998 aquarius% reduce REDUCE 3.6, 15-Jul-95, patched to 15 Apr 96 ... 1: % ----------[ R e d u c e ]---------- % ---------- Initialization ---------- on time; Time: 0 ms % ---------- Algebra ---------- % One would think that the simplification 2 2^n => 2^(n + 1) would happen % automatically or at least easily ... on combineexpt; Time: 0 ms 2*2^n; n 2*2 Time: 0 ms % And how about 4 2^n => 2^(n + 2)? [Richard Fateman] 4*2^n; n 4*2 Time: 10 ms off combineexpt; Time: 0 ms % (-1)^[n (n + 1)] => 1 for integer n (-1)^(n*(n + 1)); 2 n + n ( - 1) Time: 0 ms % Also easy => 2 (3 x - 5) 6*x - 10; 2*(3*x - 5) Time: 10 ms % Univariate gcd: gcd(p1, p2) => 1, gcd(p1 q, p2 q) => q [Richard Liska] p1:= 64*x^34 - 21*x^47 - 126*x^8 - 46*x^5 - 16*x^60 - 81$ Time: 0 ms p2:= 72*x^60 - 25*x^25 - 19*x^23 - 22*x^39 - 83*x^52 + 54*x^10 + 81$ Time: 0 ms q:= 34*x^19 - 25*x^16 + 70*x^7 + 20*x^3 - 91*x - 86$ Time: 10 ms gcd(p1, p2); 1 Time: 3300 ms plus GC time: 70 ms gcd(p1*q, p2*q) - q; 0 Time: 5000 ms plus GC time: 150 ms % resultant(p1 q, p2 q) => 0 resultant(p1*q, p2*q, x); unable to allocate 8791b0 8751b0 ***** Heap space low Cont? (Y or N) ?y Time: 700 ms plus GC time: 580 ms % How about factorization? => p1 * p2 p1 * p2$ Time: 0 ms on factor; Time: 0 ms ws; 60 52 39 25 23 10 - (72*x - 83*x - 22*x - 25*x - 19*x + 54*x + 81) 60 47 34 8 5 *(16*x + 21*x - 64*x + 126*x + 46*x + 81) Time: 136040 ms plus GC time: 1170 ms off factor; Time: 0 ms clear p1, p2, q; Time: 0 ms % Multivariate gcd: gcd(p1, p2) => 1, gcd(p1 q, p2 q) => q p1:= 24*x*y^19*z^8 - 47*x^17*y^5*z^8 + 6*x^15*y^9*z^2 - 3*x^22 + 5$ Time: 10 ms p2:= 34*x^5*y^8*z^13 + 20*x^7*y^7*z^7 + 12*x^9*y^16*z^4 + 80*y^14*z$ Time: 0 ms q:= 11*x^12*y^7*z^13 - 23*x^2*y^8*z^10 + 47*x^17*y^5*z^8$ Time: 10 ms gcd(p1, p2); *** In 4322496: Unexpected tag 27 found at 111924 during gc ***** Segmentation Violation in conterror Cont? (Y or N) ?y Time: 8790 ms plus GC time: 2220 ms gcd(p1*q, p2*q) - q; CopyFromStack error in string, stackitem 16#6892D0 heaptag 16#E heapinf 16#4F6990A *** In 5270888: Unexpected tag 27 found at 5270876 during gc ***** CATASTROPHIC ERROR ***** ("gcdf failed" (plus (minus (times 141 (expt x 39) (expt 0 0) (expt 0 0))) ( minus (times 2209 (expt x 34) (expt y 10) (expt z 16))) (minus (times 33 ( expt x 34) (expt 0 0) (expt 0 0))) (times 282 (expt x 32) (expt y 14) (expt z 10)) (minus (times 517 (expt x 29) (expt y 12) (expt z 21))) (times 66 ( expt x 27) (expt y 16) (expt z 15)) (times 69 (expt x 24) (expt 0 0) (expt 0 0)) (times 1081 (expt x 19) (expt y 13) (expt z 18)) (times 1128 (expt x 18) ( expt y 24) (expt z 16)) (minus (times 138 (expt 0 0) (expt y 17) (expt z 12))) ( times 235 (expt 0 0) (expt 0 0) (expt 0 0)) (times 264 (expt x 13) (expt y 26) ( expt z 21)) (times 55 (expt 0 0) (expt 0 0) (expt 0 0)) (minus (times 552 ( expt x 3) (expt y 27) (expt z 18))) (minus (times 115 (expt 0 0) (expt 0 0) ( expt 0 0)))) (plus (times 564 (expt x 26) (expt y 21) (expt z 12)) (times 940 ( expt x 24) (expt y 12) (expt z 15)) (times 1598 (expt x 22) (expt y 13) ( expt z 21)) (times 3760 (expt 0 0) (expt 0 0) (expt 0 0) (expt z 9)) (times 880 (expt 0 0) (expt 0 0) (expt 0 0) (expt z 14)) (minus (times 1840 (expt 0 0) ( expt 0 0) (expt 0 0) (expt z 11))) (times 132 (expt x 21) (expt y 23) (expt z 17)) (times 220 (expt x 19) (expt y 14) (expt z 20)) (times 374 (expt x 17) ( expt y 15) (expt z 26)) (minus (times 276 (expt x 11) (expt y 24) (expt z 14))) (minus (times 460 (expt x 9) (expt y 15) (expt z 17))) (minus (times 782 ( expt x 7) (expt y 16) (expt z 23))))) ***** Please send output and input listing to A. C. Hearn Cont? (Y or N) ?y ***** Unknown function type `(x . 5)' Cont? (Y or N) ?y *** In 4322496: Unexpected tag 27 found at 111924 during gc unable to allocate 8791b0 8751b0 Segmentation Fault real 842.10 user 817.27 sys 15.44 ------------------------------------------------------------------------------- Sun May 31 12:39:15 MDT 1998 aquarius% reduce REDUCE 3.6, 15-Jul-95, patched to 15 Apr 96 ... 1: % ----------[ R e d u c e ]---------- % ---------- Initialization ---------- on time; Time: 0 ms % ---------- Algebra ---------- % Multivariate gcd: gcd(p1, p2) => 1, gcd(p1 q, p2 q) => q p1:= 24*x*y^19*z^8 - 47*x^17*y^5*z^8 + 6*x^15*y^9*z^2 - 3*x^22 + 5$ Time: 0 ms p2:= 34*x^5*y^8*z^13 + 20*x^7*y^7*z^7 + 12*x^9*y^16*z^4 + 80*y^14*z$ Time: 10 ms q:= 11*x^12*y^7*z^13 - 23*x^2*y^8*z^10 + 47*x^17*y^5*z^8$ Time: 0 ms % How about factorization? => p1 * p2 p1 * p2$ Time: 0 ms on factor; Time: 0 ms ws; 22 17 5 8 15 9 2 19 8 - 2*(3*x + 47*x *y *z - 6*x *y *z - 24*x*y *z - 5) 9 9 3 7 6 5 12 7 7 *(6*x *y *z + 10*x *z + 17*x *y*z + 40*y )*y *z Time: 5310 ms plus GC time: 120 ms off factor; Time: 0 ms clear p1, p2, q; Time: 0 ms % => x^n for n > 0 [Chris Hurlburt] gcd(2*x^(n + 4) - x^(n + 2), 4*x^(n + 1) + 3*x^n); n x Time: 0 ms % Resultants. If the resultant of two polynomials is zero, this implies they % have a common factor. See Keith O. Geddes, Stephen R. Czapor and George % Labahn, _Algorithms for Computer Algebra_, Kluwer Academic Publishers, 1992, % p. 286 => 0 resultant(3*x^4 + 3*x^3 + x^2 - x - 2, x^3 - 3*x^2 + x + 5, x); 0 Time: 70 ms % Numbers are nice, but symbols allow for variability---try some high school % algebra: rational simplification => (x - 2)/(x + 2) (x^2 - 4)/(x^2 + 4*x + 4); 2 x - 4 -------------- 2 x + 4*x + 4 Time: 10 ms on factor; Time: 0 ms ws; x - 2 ------- x + 2 Time: 0 ms off factor; Time: 0 ms % This example requires more sophistication => e^(x/2) - 1 {(e^x - 1)/(e^(x/2) + 1), (exp(x) - 1)/(exp(x/2) + 1)}; x e - 1 {----------, x/2 e + 1 x e - 1 ----------} x/2 e + 1 Time: 10 ms % Expand and factor polynomials (x + 1)^20; 20 19 18 17 16 15 14 13 x + 20*x + 190*x + 1140*x + 4845*x + 15504*x + 38760*x + 77520*x 12 11 10 9 8 7 + 125970*x + 167960*x + 184756*x + 167960*x + 125970*x + 77520*x 6 5 4 3 2 + 38760*x + 15504*x + 4845*x + 1140*x + 190*x + 20*x + 1 Time: 10 ms df(ws, x); 19 18 17 16 15 14 13 20*(x + 19*x + 171*x + 969*x + 3876*x + 11628*x + 27132*x 12 11 10 9 8 7 + 50388*x + 75582*x + 92378*x + 92378*x + 75582*x + 50388*x 6 5 4 3 2 + 27132*x + 11628*x + 3876*x + 969*x + 171*x + 19*x + 1) Time: 10 ms on factor; Time: 0 ms ws; 19 20*(x + 1) Time: 20 ms off factor; Time: 0 ms % Completely factor this polynomial, then try to multiply it back together! on fullroots; Time: 0 ms solve(x^3 + x^2 - 7 = 0, x); 9*sqrt(1295) atanh(--------------) 187*sqrt(3) 2*cosh(-----------------------) - 1 3 {x=-------------------------------------, 3 9*sqrt(1295) 9*sqrt(1295) atanh(--------------) atanh(--------------) 187*sqrt(3) 187*sqrt(3) x=( - cosh(-----------------------) + sqrt(3)*sinh(-----------------------)*i 3 3 - 1)/3, 9*sqrt(1295) 9*sqrt(1295) atanh(--------------) atanh(--------------) 187*sqrt(3) 187*sqrt(3) x=( - (cosh(-----------------------) + sqrt(3)*sinh(-----------------------)*i 3 3 + 1))/3} Time: 210 ms q:= expand_cases(ws); 9*sqrt(1295) atanh(--------------) 187*sqrt(3) 2*cosh(-----------------------) - 1 3 q := {x=-------------------------------------, 3 9*sqrt(1295) atanh(--------------) 187*sqrt(3) x=( - cosh(-----------------------) 3 9*sqrt(1295) atanh(--------------) 187*sqrt(3) + sqrt(3)*sinh(-----------------------)*i - 1)/3, 3 9*sqrt(1295) atanh(--------------) 187*sqrt(3) x=( - cosh(-----------------------) 3 9*sqrt(1295) atanh(--------------) 187*sqrt(3) - sqrt(3)*sinh(-----------------------)*i - 1)/3} 3 Time: 50 ms for i:=1:length(q) product lhs(part(q, i)) - rhs(part(q, i)); 9*sqrt(1295) 9*sqrt(1295) atanh(--------------) atanh(--------------) 187*sqrt(3) 3 187*sqrt(3) 2 ( - 2*cosh(-----------------------) - 9*cosh(-----------------------) *x 3 3 9*sqrt(1295) atanh(--------------) 187*sqrt(3) 2 - 3*cosh(-----------------------) 3 9*sqrt(1295) 9*sqrt(1295) atanh(--------------) atanh(--------------) 187*sqrt(3) 187*sqrt(3) 2 - 6*cosh(-----------------------)*sinh(-----------------------) 3 3 9*sqrt(1295) 9*sqrt(1295) atanh(--------------) atanh(--------------) 187*sqrt(3) 2 187*sqrt(3) 2 + 9*sinh(-----------------------) *x + 3*sinh(-----------------------) 3 3 3 2 + 27*x + 27*x + 9*x + 1)/27 Time: 110 ms on complex, rounded; *** Domain mode complex changed to complex-rounded Time: 0 ms ws; 3 2 x + x - 7.0 Time: 10 ms off complex, rounded; *** Domain mode complex-rounded changed to rounded Time: 0 ms clear q; Time: 0 ms off fullroots; Time: 0 ms x^100 - 1; 100 x - 1 Time: 10 ms on factor; Time: 0 ms ws; 40 30 20 10 20 15 10 5 (x - x + x - x + 1)*(x + x + x + x + 1) 20 15 10 5 8 6 4 2 4 3 2 *(x - x + x - x + 1)*(x - x + x - x + 1)*(x + x + x + x + 1) 4 3 2 2 *(x - x + x - x + 1)*(x + 1)*(x + 1)*(x - 1) Time: 10 ms off factor; Time: 0 ms % Factorization over the complex rationals % => (2 x + 3 i) (2 x - 3 i) (x + 1 + 4 i) (x + 1 - 4 i) 4*x^4 + 8*x^3 + 77*x^2 + 18*x + 153; 4 3 2 4*x + 8*x + 77*x + 18*x + 153 Time: 0 ms on complex, factor; Time: 0 ms ws; (2*x + 3*i)*(2*x - 3*i)*(x + 1 + 4*i)*(x + 1 - 4*i) Time: 40 ms off complex, factor; Time: 0 ms % Algebraic extensions load_package(arnum)$ Time: 10 ms defpoly(sqrt2^2 - 2); Time: 0 ms % => sqrt2 + 1 1/(sqrt2 - 1); sqrt2 + 1 Time: 10 ms % => (x^2 - 2 x - 3)/(x - sqrt2) = (x + 1) (x - 3)/(x - sqrt2) % [Richard Liska] (x^3 + (sqrt2 - 2)*x^2 - (2*sqrt2 + 3)*x - 3*sqrt2)/(x^2 - 2); 3 2 x + (sqrt2 - 2)*x - (2*sqrt2 + 3)*x - 3*sqrt2 ------------------------------------------------- 2 x - 2 Time: 0 ms on gcd, factor; Time: 0 ms ws; (x + 1)*(x - 3) ----------------- x - sqrt2 Time: 20 ms off gcd, factor; Time: 0 ms % Multiple algebraic extensions defpoly(sqrt3^2 - 3, cbrt2^3 - 2); *** Defining polynomial for primitive element: 4 2 a1 - 10*a1 + 1 *** Defining polynomial for primitive element: 12 10 9 8 6 5 4 3 a2 - 30*a2 - 8*a2 + 303*a2 - 1036*a2 - 1104*a2 + 663*a2 + 3488*a2 2 + 1290*a2 + 696*a2 - 3863 Time: 10630 ms plus GC time: 440 ms % => 2 cbrt2 + 8 sqrt3 + 18 cbrt2^2 + 12 cbrt2 sqrt3 + 9 (cbrt2 + sqrt3)^4; 63684 11 181034 10 1827661 9 11156781 8 - (----------*a2 + ----------*a2 - ----------*a2 - ----------*a2 13020775 13020775 13020775 26041550 514419 7 43537684 6 11946291 5 162194176 4 + --------*a2 + ----------*a2 - ----------*a2 - -----------*a2 420025 13020775 2604155 13020775 113909029 3 67614972 2 172241108 255761099 - -----------*a2 - ----------*a2 + -----------*a2 + -----------) 13020775 13020775 13020775 26041550 Time: 810 ms plus GC time: 40 ms % Factor polynomials over finite fields and field extensions p:= x^4 - 3*x^2 + 1; 4 2 p := x - 3*x + 1 Time: 0 ms on factor; Time: 0 ms p; 2 2 (x + x - 1)*(x - x - 1) Time: 40730 ms plus GC time: 1350 ms % => (x - 2)^2 (x + 2)^2 mod 5 setmod 5$ Time: 0 ms on modular; *** Domain mode arnum changed to modular Time: 0 ms p; 2 2 (x + 3) *(x + 2) Time: 0 ms off modular, factor; Time: 0 ms ws; 4 3 2 x + 10*x + 37*x + 60*x + 36 Time: 10 ms % => (x^2 + x + 1) (x^9 - x^8 + x^6 - x^5 + x^3 - x^2 + 1) mod 65537 % [Paul Zimmermann] setmod 65537$ Time: 0 ms on modular, factor; Time: 0 ms x^11 + x + 1; 9 8 6 5 3 2 2 (x + 65536*x + x + 65536*x + x + 65536*x + 1)*(x + x + 1) Time: 50 ms % => (x - phi) (x + phi) (x - phi + 1) (x + phi - 1) % where phi^2 - phi - 1 = 0 or phi = (1 +- sqrt(5))/2 off modular; Time: 0 ms clear p; Time: 0 ms (x - 2*y^2 + 3*z^3)^20$ Time: 10 ms on factor; Time: 0 ms ws; 2 3 20 (2*y - 3*z - x) Time: 0 ms off factor; Time: 0 ms (sin(x) - 2*cos(y)^2 + 3*tan(z)^3)^20$ Time: 80 ms on factor; Time: 10 ms ws; 2 3 20 (2*cos(y) - sin(x) - 3*tan(z) ) Time: 2960 ms plus GC time: 180 ms off factor; Time: 0 ms % expand[(1 - c^2)^5 (1 - s^2)^5 (c^2 + s^2)^10] => c^10 s^10 when % c^2 + s^2 = 1 [modification of a problem due to Richard Liska] q:= (1 - c^2)^5 * (1 - s^2)^5 * (c^2 + s^2)^10$ Time: 10 ms load_package(compact)$ Time: 30 ms compact(q, {c^2 + s^2 = 1}); 10 2 4 10 8 2 s *(10*c *s - s + 5*s - 5*s + 1) Time: 10 ms sub(c = sqrt(1 - s^2), ws); 10 10 8 6 4 2 s *( - s + 5*s - 10*s + 10*s - 5*s + 1) Time: 10 ms on factor; Time: 0 ms ws; 5 5 10 - (s + 1) *(s - 1) *s Time: 20 ms off factor; Time: 0 ms load_package(groebner)$ Time: 130 ms groebner({q, c^2 + s^2 - 1}); 2 2 {c + s - 1, 20 18 16 14 12 10 s - 5*s + 10*s - 10*s + 5*s - s } Time: 190 ms plus GC time: 50 ms on factor; Time: 0 ms ws; 2 2 5 5 10 {c + s - 1,(s + 1) *(s - 1) *s } Time: 30 ms off factor; Time: 0 ms clear q; Time: 0 ms % => (x + y) (x - y) mod 3 setmod 3$ Time: 0 ms on modular; Time: 0 ms 4*x^2 - 21*x*y + 20*y^2; 2 2 x + 2*y Time: 0 ms off modular; Time: 0 ms % => 1/4 (x + y) (2 x + y [-1 + i sqrt(3)]) (2 x + y [-1 - i sqrt(3)]) on complex; Time: 10 ms x^3 + y^3; 3 3 x + y Time: 0 ms off complex, factor; Time: 0 ms % Partial fraction decomposition => 3/(x + 2) - 2/(x + 1) + 2/(x + 1)^2 (x^2 + 2*x + 3)/(x^3 + 4*x^2 + 5*x + 2); 2 x + 2*x + 3 --------------------- 3 2 x + 4*x + 5*x + 2 Time: 0 ms pf(ws, x); 3 - 2 2 {-------,-------,--------------} x + 2 x + 1 2 x + 2*x + 1 Time: 80 ms on factor; Time: 0 ms ws; 3 - 2 2 {-------,-------,----------} x + 2 x + 1 2 (x + 1) Time: 10 ms off factor; Time: 0 ms % Noncommutative algebra: note that (A B C)^(-1) = C^(-1) B^(-1) A^(-1) % => A B C A C B - C^(-1) B^(-1) C B operator A, B, C; Time: 0 ms noncom A, B, C; Time: 0 ms (A()*B()*C() - (A()*B()*C())^(-1)) * A()*C()*B(); a()*b()*c()*a()*b()*c() - 1 Time: 10 ms % Jacobi's identity: [A, B, C] + [B, C, A] + [C, A, B] = 0 where [A, B, C] = % [A, [B, C]] and [A, B] = A B - B A is the commutator of A and B procedure comm2(A, B); A * B - B * A$ Time: 0 ms procedure comm3(A, B, C); comm2(A, comm2(B, C))$ Time: 0 ms comm2(A(), B()); a()*b() - b()*a() Time: 0 ms comm3(A(), B(), C()) + comm3(B(), C(), A()) + comm3(C(), A(), B()); 0 Time: 10 ms clear A, B, C, comm2, comm3; Time: 0 ms % ---------- Quit ---------- quit; Quitting real 87.20 user 64.07 sys 2.53