/usr/share/yacas/scripts/univar.rep/sparse.ys is in yacas 1.3.6-2+b1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 | // SparceUniVariate(variable,termlist) implements an internal representation
// for univariate polynomials
// termlist is the list of terms in the form {exponent,coeficient}
RuleBase("SparseUniVar",{var,termlist});
300 # SparseUniVar(_var,_terms1) * SparseUniVar(_var,_terms2) <--
SparseUniVar(var, MultiplyTerms(terms1,terms2));
300 # SparseUniVar(_var,_terms1) + SparseUniVar(_var,_terms2) <--
SparseUniVar(var, AddTerms(terms1,terms2));
300 # SparseUniVar(_var,_terms1) - SparseUniVar(_var,_terms2) <--
SparseUniVar(var, SubstractTerms(terms1,terms2));
// Add a term into a termlist: this function assumes that
// 1) the list of terms is sorted in decreasing order of exponents
// 2) there are not two terms with the same exponent.
// 3) There is no term with cero coefficient
// This assumptions are preserved.
// The parameter begining tell us where to begin the search
// (it is used for increasing the efficency of the algorithms!)
// The function returns the position at which the new term is added plus 1.
// (to be used as begining for sucesive AddTerm calls
Function("AddTerm",{termlist,term,begining})
[
Local(l,i);
l := Length(termlist);
If(term[2]!=0,
[
i:=begining;
// Fix-me: search by using binary search ?
If (l>=1, While ((i<=l) And (term[1]<termlist[i][1])) i++);
If (i>l, [DestructiveAppend(termlist,term);i++;],
If (term[1]=termlist[i][1],
[ Local(nc);
nc:=termlist[i][2]+term[2];
If(nc!=0,DestructiveReplace(termlist,i,{term[1],nc}),
[DestructiveDelete(termlist,i);i--;]);
], DestructiveInsert(termlist,i,term))
);
]
);
i+1;
];
Function("AddTerms",{terms1,terms2})
[
Local(result,begining,t);
begining :=1;
ForEach (t,terms2)
begining :=AddTerm(terms1,t,begining);
terms1;
];
Function("SubstractTerms",{terms1,terms2})
[
Local(result,t);
begining :=1 ;
ForEach (t,terms2)
begining := AddTerm(terms1,{t[1],-t[2]},1);
terms1;
];
// Multiply a list of terms by a Single tem
Function("MultiplySingleTerm",{termlist,term})
[
Local(result,t);
result:={};
If(term[2]!=0,
ForEach (t,termlist)
DestructiveAppend(result,{t[1]+term[1],t[2]*term[2]}) );
result;
];
Function("MultiplyTerms",{terms1,terms2})
[
Local(result,t1,t2,begining);
result:={};
ForEach (t1,terms1)
[
begining :=1;
ForEach (t2,terms2)
begining := AddTerm(result,{t1[1]+t2[1],t1[2]*t2[2]},1);
];
result;
];
Function("ExpandSparseUniVar",{s})
[
Local(result,t,var,termlist);
result :=0;
var := s[1];
termlist := s[2];
ForEach (t,termlist)
[
Local(term);
term := NormalForm(t[2]*var^t[1]);
result := result + term;
];
result;
];
// Implements the division of polynomials!
Function("DivTermList",{a,b})
[
Local(q,nq,t,c,begining);
q := {};
// a[1][1] is the degree of a, b[1][1] is the degree of b
While ((a!={}) And a[1][1]>=b[1][1])
[
begining := 1;
If(InVerboseMode(),Echo("degree=",a[1][1]));
nq := {a[1][1]-b[1][1],a[1][2]/b[1][2]}; // a new term of the quotient
DestructiveAppend(q,nq);
// We compute a:= a - nq* b
ForEach (t,b)
begining := AddTerm(a,{t[1]+nq[1],-t[2]*nq[2]},begining);
];
// a is the rest at the end
q;
];
|