[system] / trunk / pg / macros / PGpolynomialmacros.pl Repository: Repository Listing bbplugincoursesdistsnplrochestersystemwww

# View of /trunk/pg/macros/PGpolynomialmacros.pl

Wed Jun 11 02:43:42 2003 UTC (16 years, 8 months ago) by apizer
File size: 7720 byte(s)
```Fixed error concerning variable \$string.
Cleaned up how polynomials are displayed.

Arnie
```

```    1
2 ##########################################################
3 ##  This file is PGpolynomialmacros.pl                  ##
4 ##  It contains rountines used to create and manipulate ##
5 ##  polynomials for WeBWorK                             ##
6 ##                                                      ##
7 ##  Copyright 2002 Mark Schmitt                         ##
8 ##  Version 1.1.2                                       ##
9 ##########################################################
10
11 ##  In the current version, there is no attempt to verify that correct arrays are being passed to the routines.
12 ##  This ought to be changed in the next incarnation.
13 ##  It is assumed that arrays passed to the routines have no leading zeros, and represent the coefficients of
14 ##  a polynomial written in standard form using place-holding zeros.
15 ##  This means \$array[0] is the leading coefficient of the polynomial and \$array[\$#array] is the constant term.
16 ##
17 ##  The routines were written based on the needs of my Honors Algebra 2 course.  The following algorithms have been
18 ##  coded:
19 ##      Polynomial Multiplication
20 ##      Polynomial Long Division
21 ##      Polynomial Synthetic Division (mainly as a support routine for checking bounds on roots)
22 ##      Finding the least positive integral upper bounds for roots
23 ##      Finding the greatest negative integral lower bounds for roots
24 ##      Descartes' Rule of Signs for the maximum number of positive and negative roots
25 ##      Stringification : converting an array of coefficients into a properly formatted polynomial string
27 ##      Polynomial Subtraction
28
29
30 ##
31 ## ValidPoly
32 ##
33 sub ValidPoly {
34     my \$xref = @_;
35     if (\${\$xref}[0] != 0) {return 1;}
36     else {return 0;}
37 }
38
40     my (\$xref,\$yref) = @_;
41     @local_x = @{\$xref};
42     @local_y = @{\$yref};
43     if (\$#local_x < \$#local_y) {
44     while (\$#local_x < \$#local_y) {unshift @local_x, 0;}
45     }
46     elsif (\$#local_y < \$#local_x) {
47     while (\$#local_y < \$#local_x) {unshift @local_y, 0;}
48     }
49     foreach \$i (0..\$#local_x) {
50         \$sum[\$i] = \$local_x[\$i] + \$local_y[\$i];
51     }
52     return @sum;
53 }
54
55 sub PolySub{
56     my (\$xref,\$yref) = @_;
57     @local_x = @{\$xref};
58     @local_y = @{\$yref};
59     if (\$#local_x < \$#local_y) {
60         while (\$#local_x < \$#local_y) {unshift @local_x, 0;}
61     }
62     elsif (\$#local_y < \$#local_x) {
63     while (\$#local_y < \$#local_x) {unshift @local_y, 0;}
64     }
65     foreach \$i (0..\$#local_x) {
66         \$diff[\$i] = \$local_x[\$i] - \$local_y[\$i];
67     }
68     return @diff;
69 }
70
71 ##
72 ## @newPoly = PolyMult(~~@coefficientArray1,~~@coefficientArray2);
73 ##
74 ## accepts two arrays containing coefficients in descending order
75 ## returns an array with the coefficients of the product
76 ##
77
78 sub PolyMult{
79     my (\$xref,\$yref) = @_;
80     @local_x = @{\$xref};
81     @local_y = @{\$yref};
82     foreach \$i (0..\$#local_x + \$#local_y) {\$result[\$i] = 0;}
83     foreach \$i (0..\$#local_x) {
84         foreach \$j (0..\$#local_y) {
85            \$result[\$i+\$j] = \$result[\$i+\$j]+\$local_x[\$i]*\$local_y[\$j];
86         }
87     }
88     return @result;
89 }
90
91 ##
92 ## (@quotient,\$remainder) = SynDiv(~~@dividend,~~@divisor);
93 ##
94
95 sub SynDiv{
96     my (\$dividendref,\$divisorref)=@_;
97     my @dividend = @{\$dividendref};
98     my @divisor = @{\$divisorref};
99     my @quotient;
100     \$quotient[0] = \$dividend[0];
101     foreach \$i (1..\$#dividend) {
102         \$quotient[\$i] = \$dividend[\$i]-\$quotient[\$i-1]*\$divisor[1];
103     }
104     return @quotient;
105 }
106
107 ##
108 ##
109 ##
110 ##
111 ##
112
113 sub LongDiv{
114     my (\$dividendref,\$divisorref)=@_;
115     my @dividend = @{\$dividendref};
116     my @divisor = @{\$divisorref};
117     my @quotient; my @remainder;
118     foreach \$i (0..\$#dividend-\$#divisor) {
119       \$quotient[\$i] = \$dividend[\$i]/\$divisor[0];
120       foreach \$j (1..\$#divisor) {
121         \$dividend[\$i+\$j] = \$dividend[\$i+\$j] - \$quotient[\$i]*\$divisor[\$j];
122       }
123     }
124     foreach \$i (\$#dividend-\$#divisor+1..\$#dividend) {
125         \$remainder[\$i-(\$#dividend-\$#divisor+1)] = \$dividend[\$i];
126     }
127     return (\@quotient,\@remainder);
128 }
129
130
131
132 ##
133 ## \$upperBound = UpBound(~~@polynomial);
134 ##
135 ## accepts a reference to an array containing the coefficients, in descending
136 ##   order, of a polynomial.
137 ##
138 ## returns the lowest positive integral upper bound to the roots of the
139 ##   polynomial
140 ##
141
142 sub UpBound {
143     my \$polyref=\$_[0];
144     my @poly = @{\$polyref};
145     my \$bound = 0;
146     my \$test = 0;
147     while (\$test < @poly) {
148         \$bound++;
149         \$test=0;
150         @div = (1,-\$bound);
151         @result = &SynDiv(\@poly,\@div);
152         foreach \$i (0..\$#result) {
153            if (sgn(\$result[\$i])==sgn(\$result[0]) || \$result[\$i]==0) {
154                 \$test++;
155            }
156         }
157     }
158     return \$bound;
159 }
160
161
162 ##
163 ## \$lowerBound = LowBound(~~@polynomial);
164 ##
165 ## accepts a reference to an array containing the coefficients, in descending
166 ##   order, of a polynomial.
167 ##
168 ## returns the greatest negative integral lower bound to the roots of the
169 ##   polynomial
170 ##
171
172 sub LowBound {
173     my \$polyref=\$_[0];
174     my @poly = @{\$polyref};
175     my \$bound = 0;
176     my \$test = 0;
177     while (\$test == 0) {
178         \$test = 1; \$bound = \$bound-1;
179         @div = (1,-\$bound);
180         @res = &SynDiv(\@poly,\@div);
181         foreach \$i (1..int((\$#res -1)/2)) {
182             if (sgn(\$res[0])*sgn(\$res[2*\$i]) == -1) {
183             \$test = 0;}
184         }
185         foreach \$i (1..int(\$#res/2)) {
186             if (sgn(\$res[0])*sgn(\$res[2*\$i-1]) == 1) {
187             \$test = 0;}
188         }
189     }
190     return \$bound;
191 }
192
193
194
195
196 ##
197 ## \$string = PolyString(~~@coefficientArray,x);
198 ##
199 ## accepts an array containing the coefficients of a polynomial
200 ##   in descending order
201 ## returns a sting containing the polynomial with variable v
202 ## default variable is x
203 ##
204
205 sub PolyString{
206   my \$temp = \$_[0];
207   my @poly = @{\$temp};
208   my \$string = '';
209   foreach my \$i (0..\$#poly) {
210     my \$j = \$#poly-\$i;
211     if (\$j == \$#poly) {
212       if (\$poly[\$i] >0) {
213         if (\$poly[\$i]!=1){
214           \$string = \$string."\$poly[\$i] x^{\$j}";
215         }
216         else {\$string=\$string."x^{\$j}";}
217       }
218       elsif (\$poly[\$i] == 0) {}
219       elsif (\$poly[\$i] == -1) {\$string=\$string."-x^{\$j}";}
220       else {\$string = \$string."\$poly[\$i] x^{\$j}";}
221     }
222     elsif (\$j > 0 && \$j!=1) {
223       if (\$poly[\$i] >0) {
224         if (\$poly[\$i]!=1){
225           \$string = \$string."+\$poly[\$i] x^{\$j}";
226         }
227         else {\$string = \$string."+x^{\$j}";}}
228       elsif (\$poly[\$i] == 0) {}
229       elsif (\$poly[\$i] == -1) {\$string=\$string."-x^{\$j}";}
230       else {\$string = \$string."\$poly[\$i] x^{\$j}";}
231     }
232     elsif (\$j == 1) {
233       if (\$poly[\$i] > 0){
234           if (\$poly[\$i]!=1){
235           \$string = \$string."+\$poly[\$i] x";
236         }
237           else {\$string = \$string."+x";}
238         }
239       elsif (\$poly[\$i] == 0) {}
240       elsif (\$poly[\$i] == -1){\$string=\$string."-x";}
241       else {\$string=\$string."\$poly[\$i] x";}
242     }
243     else {
244       if (\$poly[\$i] > 0){
245           \$string = \$string."+\$poly[\$i] ";
246         }
247       elsif (\$poly[\$i] == 0) {}
248       else {\$string=\$string."\$poly[\$i] ";}
249     }
250   }
251   return \$string;
252 }
253
254
255 sub PolyFunc {
256     my \$temp = \$_[0];
257     my @poly = @{\$temp};
258     \$func = "";
259     foreach \$i (0..\$#poly) {
260         \$j = \$#poly-\$i;
261         if (\$poly[\$i] > 0) {\$func = \$func."+\$poly[\$i]*x**(\$j)";}
262         else {\$func = \$func."\$poly[\$i]*x**(\$j)";}
263     }
264     return \$func;
265 }
266
267 ##
268 ## (\$maxpos,\$maxneg) = Descartes(~~@poly);
269 ##
270 ## accepts an array containing the coefficients, in descending order, of a
271 ##  polynomial
272 ## returns the maximum number of positive and negative roots according to
273 ##  Descartes Rule of Signs
274 ##
275 ## IMPORTANT NOTE:  this function currently does not accept coefficients of
276 ##  zero.
277 ##
278
279 sub Descartes {
280     my \$temp = \$_[0];
281     my @poly = @{\$temp};
282     my \$pos = 0; my \$neg = 0;
283     foreach \$i (1..\$#poly) {
284         if (sgn(\$poly[\$i])*sgn(\$poly[\$i-1]) == -1) {\$pos++;}
285         elsif (sgn(\$poly[\$i])*sgn(\$poly[\$i-1]) == 1) {\$neg++;}
286     }
287     return (\$pos,\$neg);
288 }
289
290
291
292
293
294
295
296
297
298
299 1;
```