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

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

Mon Jun 11 18:16:40 2007 UTC (12 years, 7 months ago) by gage
File size: 8246 byte(s)
```Fixing docementation so that it can be read from the web.
```

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